counting Sudoku _problems_

[hv at crypt.org]

Earlier I wrote:
:The recent sequences have all considered grids that could appear
:as the _answer_ to a Sudoku problem. Another interesting question
:is how many grids could appear as the _problem_, with the proviso
:that such a problem must lead to a unique solution.
[...]
:The 4 x 4 grid is also of interest, and as usual much more tractable -
:the worst case is a(8), and factoring out the obvious symmetries means
:that no more than 6 * C(16, 8) = 77220 positions need to be considered.

Given a(n) is the number of 4 x 4 fair sudoku problems with 'n' digits
given, we get (with n_2 = A107739(2) = 288):
  a(0) = 0
  a(1) = 0
  a(2) = 0
  a(3) = 0
  a(4) = 25728
  a(5) = 284160
  a(6) = 1041408
  a(7) = 2141184
  a(8) = 2961024
  a(9) = 2958336
  a(10) = 2204928
  a(11) = 1239552
  a(12) = 522624  = n_2 . C(16, 4) - (96 . 8 + 192 . 4)
  a(13) = 161280  = n_2 . C(16, 3)
  a(14) = 34560   = n_2 . C(16, 2)
  a(15) = 4608    = n_2 . C(16, 1)
  a(16) = 288     = n_2
.. which I have submitted via the webform.

Note that for 12 given digits, the 96 type 'A' grids each have 8 ways
of removing 4 digits that introduce ambiguity, while the 192 type 'B'
grids have 4 ways each. Using these same sets of 4 digits, it is easy
to show that a(3) = 0.

I have quite high confidence in these numbers, but I don't know how
to verify them for n in (4..11); suggestions (or confirmation) welcome.

Here's a random example from a(4), just to show it is valid:

+--+--+
| 4| 2|
|  | 1|
+--+--+
|  |  |
| 3|  |
+--+--+

In case anyone is interested, I include perl code below that calculates
the sequence. (_Is_ anyone ever interested in this? Would you prefer it
in more verbose form, with comments?)

This first constructs the list of 288 complete grids, then finds the
C(16, n) masks that remove all but n digits, then counts which results
are unique over the cross-product of the two lists. (Note: memory
requirement approx 500MB, though that could easily be reduced.)

Hugo van der Sanden
---
my @tr = map eval "sub { local \$_ = \$_[0]; tr{1234}{$_}; \$_ }", qw/
  1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431
  3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321
/;
my @full = map { my $norm = $_; map $_->($norm), @tr } map {
  $_, substr($_, 0, 8) . substr($_, 12, 4) . substr($_, 8, 4)
} qw/ 
  1234341221434321 1234341223414123 1234342121434312
  1234431221433421 1234432121433412 1234432124133142
/;

for (0 .. 16) {
  my %seen;
  for my $mask (perms($_, 0)) { 
    ++$seen{$mask & $_} for @full;
  }
  printf "$_: %d\n", scalar grep $_ == 1, values %seen;
}               

sub perms {
  my($c, $i) = @_;
  ($i == 16) ? ($c ? () : (""))
    : (map("0$_", perms($c, $i + 1)), map("7$_", perms($c - 1, $i + 1)));
}