This can be extended to create a random solution, just randomize the initial block. (This is similar to AbigailII's solution). Here @start is a N by N matrix whose entries are a random permutation of {1, .., N^2}.
my $n = shift  3;
my @start = do {
use List::Util 'shuffle';
my @perm = shuffle 1 .. $n*$n;
map {
my $row = $_;
[ map { $perm[$row * $n + $_] } 0 .. $n1 ]
} 0 .. $n1;
};
my @solution;
for my $x ( 0 .. $n*$n  1 ) {
for my $y ( 0 .. $n*$n  1 ) {
my $block_x = int ($x / $n);
my $block_y = int ($y / $n);
$solution[$x][$y] =
$start[ ($block_x + $y) % $n ][ ($block_y + $x) % $n ];
}
}
print join "" => map { "@$_\n" } @solution;
