I've lately (winter 2005 to 2006) been playing Su Doku quite a bit (and enjoying the stray thought, begotten of Norwegian's meaning for ku and a Unix geek's familiarity with sudo, of a cow running with administrator privileges). Su Doku is a puzzle in which a nine by nine grid of square cells is divided into a three by three grid of tiles, each of three by three cells; thus each row, column and tile of the puzzle has exactly nine cells in it. In a valid solution to a Su Doku puzzle, each of the digits 1 through 9 appears exactly once in each row, in each column and in each tile. The puzzle, as set, supplies the grid with some entries filled in: the player has to fill in the rest. You can play Su Doku at my sister's friend Gaby's web site (and, if you follow some of the advertising links there, you'll be helping keep Gaby in money to keep running that site).

I'm sure the problem of how may possible Su Doku end states there are has
been solved before, but I want to work it out for my self. It should be obvious
that we can apply any permutation of the numbers 1 through 9 consistently to the
whole lattice and turn any end-state into a functionally equivalent, though
different-looking one; we may, thus, re-label the digits so that (say) the top
left tile has the digits 1, 2, 3 as its top row, then 4, 5, 6 as its second row
and 7, 8, 9 as its third row, in the given orders within each row. There are 9!
(that is, nine factorial

, the result of multiplying the numbers one
through 9 together, 9×8×…×2×1) = 362880
permutations of the digits, so each solution with the given top left tile is
equivalent to 9! other solutions with superficially different top left tiles.

Let us now consider how many ways there are to fill in a tile in the same
row or column as the tile which we've used to define our re-labelling; we may as
well suppose it to be the middle tile on the left. We may start by considering
how we may fill its left column. This stands below the 1, 4, 7 column of our
given top left tile; so it cannot contain any of the digits 1, 4 or 7. First,
let us ignore the order of elements within its three columns; think of each
column as simply a set of digits, without regard to order, constrained to not
share an element with the corresponding column of our first tile. The left
column can either consist of exactly the three entries in either the middle or
right columns of the first tile; or draw two from one of these columns and one
from the other. In the former case, the new tile must use the top left tile's
left column's entries in its column *not* below the one it borrowed for
its left column; and the top left tile's entries in that column as its entries
in the column it borrowed for its left column. Thus we have two possible ways
to chose which digits go in which columns that simply shuffle the columns of the
top left tile; otherwise, we take two from either mid or right column and one
from the other to form our new left column. For the latter case, we have nine
possiblities drawing two from the middle and one from the right, and nine
possibilities drawing two from the right and one from the middle; we have three
ways to chose which one to draw from the column supplying only one; for the
other column, we have three ways to chose a first digit, two ways to chose a
second, but that counts each pair twice by chosing its entries in both orders,
so we must divide the result by two. In each of these eighteen cases, below the
top left tile's column which supplied two entries to our new tile's left column,
we must take the two unused entries from the column which supplied only one to
the new left column; and may chose any one of the top left tile's entries from
its left column as our third entry; the new tile's third column must then be
filled with the two unused entries from the top left tile's left column and the
one unused entry from the top left tile's column which supplied two entries to
the new tile's left column. Thus each of the eighteen ways to make a new left
column by mixing the top tile's left and right columns yields three new tiles;
three eighteens make 54; add two for the un-mixed possibilities, to get 56 =
8×7 = 8×7×6/3! = 8!/3!/5! = chose(8,3) – the number of
ways one may chose a subset of size 3 from a set of size 8 – possible ways
to select which digit goes in which column, without regard to order within the
column.

We can use any order *within* each column, now that we know which
digits are in it; so we get 8×7×3!×3!×3! possible middle
left tiles. At first sight we might suppose we can apply the same logic to
determine the top middle tile; but we then have to wonder whether this might
lead to some conflict between these two tiles when it comes to settling the
central tile's contents.