Sudoku

[hv at crypt.org]

Thane Plambeck <thane at best.com> wrote:
:I noticed this paragraph on a blog and thought I would pass it on 
:(although I don't know if the problem is well posed, or even what it is, 
:exactly)
: 
:*  snip *
:Counting version: How many different filled in Sudoku-n grids are there? 
:Let me get you started: For n=1, the answer is 1. For n=2... actually, I 
:don't know, but there are at most (4!)^4 ways to arrange 4 lines of 
:permutations of {1,2,3,4}, so checking all 300,000-ish possibilities 
:won't take too long on a modern PC.

Transpositions don't affect the result, so you can fix the first line
to (1, 2, 3, 4) and check the (4!)^3 possibilities for the other lines,
then multiply the result by 4!. Once you have fixed the second and third
lines, there is only one possibility for the 4th line: you just need to
check whether that gives a valid result, so that's (4!)^2 to check.

The second line must have (3, 4) or (4, 3) followed by (1, 2) or (2, 1).
The third and fourth lines can be swapped without affecting validity,
so we can fix the first element of the third line to be the lower of
the two possibilities and multiply the results by two. That'll leave
at most 4 possibilities for the 3rd line (2 choices in each of the
remaining 3 positions, and one position will have our selected number
as one of the choices), so that's just 16 possibilities that need to
be checked, and the final results to be multiplied by 48.

So who needs a computer? :)

1234/3412/2143/4321 1234/3412/2341/4123 1234/3421/2143/4312
1234/4312/2143/3421 1234/4321/2143/3412 1234/4321/2413/3142

a(2) = 6 * 48.

:But for 3, 
:one will need some smarter techniques to do the counting, perhaps 
:building up satisfying sublocks, and using symmetries more cleverly. I 
:couldn't spot any entries in Neil Sloane's encylopedia of integer 
:sequences <http://www.research.att.com/%7Enjas/sequences/> for this 
:problem yet...
:* snip *

Pruning the a(3) searchspace similarly should render it tractable.
Fix the top line as before (muliply results by 9!); that leaves 6!
possibilities for the top left 3x3 block, half of which we can skip
by swapping the second and third lines (multiply results by 2).
(3!)^2 of those pick 4-5-6 as the start of the second line, which
leaves 6^4 possibilities for the other two 3x3 blocks, and the others
leave 6^4 x 3 possibilities, giving a total of:
  (3!)^2 x 6^4 + (6!/2 - (3!)^2) x 6^4 x 3 = 28 x 6^6
possibilities for the second and third lines together.

 From here I'd work in columns: the second and third groups of 3 lines
can be swapped wlog, and so can the 3 lines within each group. So the
first digit for the fourth line can be taken as the lowest available
(multiply the results by 6), for the fifth and sixth lines can be
ordered (multiply by 2) and for lines 7-8-9 can be ordered (multiply
by 6) for a total of 5C2 = 10 possibilities. Column 2 has at most 6!
possibilities, and column 3 at most (3!)^2.

Not sure how well things can prune beyond that, but worst case the
remaining columns have 6!, 5.5!, 6^2, (3!)^2, (2.2!)^2, 1 for a worst
case total of:
  28 x 6^6 x 10 x 6! x 6^2 x 6! x 5.5! x 6^2 x (3!)^2 x (2.2!)^2 x 1 
which is about 3 x 10^21 (down from (9!)^9 ~= 1.1 x 10^50), and I'm sure
tightening up those remaining columns would be able to lop another
digit or two from that. Don't forget the multiplier - now at 144.9!.

Hugo