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.
Written by Eddy.