|
Sudoku is a popular game that came into existence quite recently. The object is to place the numbers 1 through 9 such that each number occurs only once in each row, column, and 3x3 block.
However, my original thought was that there was only one basic solution and all others can be derived from it by some simple operations, that will be enumerated later. This has proven false. Thanks to Christian Baune (see below).
However, to continue on, let's propose that the basic solution is:
A D G a b c d e f g h i R r 1 2 3 4 5 6 7 8 9 s 4 5 6 7 8 9 1 2 3 t 7 8 9 1 2 3 4 5 6 U u 2 3 4 5 6 7 8 9 1 v 5 6 7 8 9 1 2 3 4 w 8 9 1 2 3 4 5 6 7 X x 3 4 5 6 7 8 9 1 2 y 6 7 8 9 1 2 3 4 5 z 9 1 2 3 4 5 6 7 8 New solutions can be generated from this one by performing certain operations. Borrowing from group theory we use [ab] for exchanging "a" with "b", and cyclic permutations with (abcd...z) where "a" is replaced by "b", "c" by "d", ..., and "z" replaced by "a".
Therefore, it becomes a combinatorial problem only, where the number of choices can easily be counted giving the possible number of solutions.
The allowed set of operations are:
- Exchange of any block row. There are 3! choices from the set of [ R U X ].
- Exchange of any block column. There are 3! choices from the set of [ A D G ].
- Exchange of any row within a block row. There are 3! choices for each of the sets of [ r s t ], [ u v w ], and [ x y z ].
- Exchange of any column within a column row. There are 3! choices for each of the sets of [ a b c ], [ d e f ], and [ g h i ].
- Transpose the matrix along the diagonal. There are 2 choices here.
- Finally, recognising that the symbols 1,2,3,...,9 are merely that. They can be exchanged with any combination of numbers 1,2,3,...,9. There are 9! choices for the set of symbol substition in the the set [ 1 2 3 4 5 6 7 8 9 ].
Hence, the number of solutions is given by:
3! x 3! x (3!)3 x (3!)3 x 2 x 9! = 2 x (3!)8 x 9! = 1,218,998,108,160Other operations can be reduced to the above set though, and are not considered unique.
For example, a horizontal inversion can be done with: [ R X ][rt][uw][xz]
And a vertical inversion with: [ A G ][ac][df][gi] .Note that an inversion along the main diagonal can not be performed because it would require the same three symbols to be present everywhere on the diagonal, where the other 6 symbols are exchanged as 3 identical pairs. However, an inversion along the anti-diagonal is the same as a horizontal or vertical inversion followed by an inversion along the diagonal and then again by the same horizontal or vertical inversion in the first half.
The problem with the above analysis is that it can be shown by example that combinations of operations can give the same result as other combinations of operations. For example, suppose only a cyclic permutation of the symbols is performed. Say, (123456789). This operation can easily be duplicated with [rst][RUX]. Therefore, the number of solutions can be over counted. But more disturbing is that there are solutions that can not be obtained from the original basic solution by this set of operations.
Take, for example, in block row U see that the symbol 1 and 4 are always in the same column. Just do a transpose of these two symbols and you still have a valid solution. The question is whether any set of operations can result in this solution? I believe not.
Christian Baune has written a posting (in French) at
http://www.forum.math.ulg.ac.be/searchresult.html?keywords=sudoku&author=Baune+C.§ion=-1
which can be adequately translated with Babel Fish by cutting-and-pasting the URL and selecting "From French" to the language of your choice.At this point, we regress from the 3x3 version of Sudoku to a simpler and smaller subset ... the 2x2 version and demonstrate the failure of the above analysis by explicit example.
Last Modified: 2007/05/06 22:11:13
Brought to you by: R.K. Owen,Ph.D.
This page is http://owen.sj.ca.us/rkowen/howto/sudoku.html
