counting Sudoku _problems_

[hv at crypt.org]

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.

I have no idea how to go about determining the intermediate values,
but if a(n) is the number of possible problems with _n_ of the 81
digits filled in, we have a(n) <= C(81,n) . a(81), with a(81)
already known from the calculations of Jarvis, Felgenhauer and
Russell.

The first possible ambiguity involves a block of 4 digits, so
equality will be achieved for n > 77. An ambiguity doesn't
disappear when more digits are removed, so we can refine to:
  a(n) <= a(n+1) . (n+1)/(81-n)  for 0 <= n <= 80

 From the other end, a(n) = 0 for at least n <= 9, and I'm sure
pushing that to n <= 18 will be trivial. However, when I check
some examples of actual problems, the most extreme examples had
a(n) = 22, and I suspect this is at or near the actual minimum.
I'm sure that establishing "the hardest possible Sudoku problems"
would be of particular interest to the puzzling community.

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.

Hugo