I played around with part 1. An interesting problem, but it didn't feel like a a good one for golf.

"the intention is that entries should calculate the terms rather than simply embed them", you say, but when I looked at your part 1 code, I found plenty of embedded data. Disappointing.

Below is 14 lines of code that generates the desired 288 lines, starting only with the constraint definitions and "my $N=4;". It would, I believe, work as well for N=9 - if you were willing to wait. :)

The algorithm uses regular expressions and recursion both to generate the permutations and recognize the sudoku solutions. I put together a different, iterative version as well; that one didn't squash quite as small. If there's any interest I could post more readable versions of each.

#!/usr/bin/perl
use warnings; use strict;      
my $N=4;my $sqN=sqrt($N);my @d=1..$N;my @nsq=0..$N**2-1;my $o2n=join('
+',@d);
my (@perm,@sud,$p_regex,$s_regex,%cnstrnts,@extra,$i,$j,$p);
sub ro {int(shift()/$N)} sub col {shift()%$N}
sub yy {int(int(shift()/$N)/$sqN)} sub xx {int((shift()%$N)/$sqN)}
for $i (0..$N-1){$p_regex.='(?!'.join('|',map {'\\'.$_} 1..$i).')' if 
+$i>0;
$p_regex.='(\\d)'} $p_regex = qr($p_regex)o; for $i (@nsq){ my @cnflct
+s;
for $j (@nsq){next unless $i!=$j && (ro($i)==ro($j)||col($i)==col($j)|
+|
xx($i)==xx($j)&&yy($i)==yy($j)); push(@cnflcts, 1+$j)} $cnstrnts{$i}=\
+@cnflcts}
for $i (@nsq){$s_regex.='(?!'.join('|',map{'\\'.$_}@{$cnstrnts{$i}}).'
+)(\\d)'}
$s_regex=qr($s_regex)x; our ($br,$max,$regex,@ans)=(\@d,$N,$p_regex);
sub recur {my $st = shift; if (length($st)>=$max) {push(@ans,$st)
if $st=~$regex} else {recur($st.$_) for @$br}} recur(''); @perm=@ans;
($br,$max,$regex,@ans)=(\@perm,$N**2,$s_regex); recur($o2n); @sud=@ans
+; my @as;
for $p (@perm){eval("tr/$o2n/$p/"),push(@as,$_) for @sud} print "$_\n"
+ for @as;

# Generate strings representing sudoku puzzle solutions.  
# This could certainly be made shorter, but at about 1000 characters 
# it's already illegible enough for me.
#  N=4 : iterations = (N!)**(N-1) = 24**3 = 13824 ; runs in < 1 second
+.
#  N=9 : (9!)**8 = 362880**8 = 3e44, so a million/sec would take 1e31 
+years...

print "\n Number of sudokus found is " . scalar(@as) . ".\n\n"; # N=4 
+gives 288
[download]