Daniel's code

#!/usr/bin/perl

use strict;
use warnings;

use List::Util qw(shuffle);

my $board = "1234567894567891237891234562345678915" . 
            "6789123489123456734567891267891234591" .
            "2345678"; # valid board

# sequence:                       boards:
# 1) renumber                     9 
# 2) shuffle rows within blocks   6**3
# 3) flip on x axis?              2
# 4) transpose x for y
# 5) shuffle cols within blocks   6**3
# 6) transpose x for y?           2
# 7) flip on x axis?              2

# total count:                    3359232

my %renumber;

@renumber{1..9} = shuffle 1..9; 
$board =~ s/(.)/$renumber{$1}/g;

my @grid = unpack("A9 "x9, $board); 
@grid = map { [ split //, $_ ] } @grid;

@grid[0..2] = shuffle @grid[0..2];
@grid[3..5] = shuffle @grid[3..5];
@grid[6..8] = shuffle @grid[6..8];

@grid =   reverse(@grid)           if (rand > .5);
@grid = transpose(@grid);

@grid[0..2] = shuffle @grid[0..2];
@grid[3..5] = shuffle @grid[3..5];
@grid[6..8] = shuffle @grid[6..8];

@grid = transpose(@grid)           if (rand > .5);
@grid =   reverse(@grid)           if (rand > .5);

@grid = map { join '', @{$_} } @grid;
$board = join "\n", @grid; # join '' for same form as input
print $board;

sub flip {
    return @_[8,7,6,5,4,3,2,1,0];
}

sub transpose {

    my @AoA = @_;

    for my $x (0..8) {
        for my $y ($x+1..8) {
            ( $AoA[$x][$y], $AoA[$y][$x] ) = ( $AoA[$y][$x], $AoA[$x][$y] );
        }
    }

    return @AoA;
}