sodoku automatic problem solver

February 2007

Sodoku puzzles are formatted as a 9 x 9 grid, broken down into nine 3 x 3 boxes. To solve a sodoku, the numbers 1 through 9 must fill each row, column and box. Each number can appear only once in each row, column and box. You can figure out the order in which the numbers will appear by using the numeric clues already provided in the boxes. The more numbers you name, the easier it gets to solve the puzzle.
Source: The St Thomas Times-Journal

The notable mathematician, Prof Alan Turing, late of Manchester is considered to be largely responsible for the breaking of the Nazi Enigma code, the key man in the Allied effort. He credited the most essential piece of logic arising, years earlier, from a professor of his at Cambridge That knowledge being, "When a contradiction is discovered it is certain there are an infinite number of other possibilities." By this, given that there is one and only one object in my bedroom if we can prove that this object is not a pink elephant we know that there is an infinite selection of other elements possibly in my bedroom. When Turing and his colleagues were breaking the German code, they knew they weren't dealing with an infinite number of possibilities, rather a finite quantity. Consequently Turing developed an electro-mechanical device called, "the Bombe" which made rapid decryption of enemy secret messages possible.

Basically Turing's Bombe, upon detecting a contradiction, ruled out that attempt and moved on to another possible solution. This process was repeated systematically until a solution that could not be rejected was discovered. This should not be regarded as "trial and error."

What does this have to do with Sodoku? Well, I've often wondered if I would find an occasion(s) to apply the same principle Prof Turing so deftly employed. When I read the rules regarding the puzzle I decided to try. The program attempts a solution, constantly checking to see that the solution conforms to the rules. If an attempt is non-conforming that attempt is abandoned and the program tries, in a logical and exhaustive fashion, another solution, until a solution is found.

I've implemented the same algorithm using Java, the source file is available here for download in Zip file format.

Of course, there probably are faster ways of solving sodoku puzzles than this one.

Incidentally, for his work during WWW II Prof Turing was awarded the OBE. More importantly Prof Alan Turing saved countless lives. As for me,. I'll just be happy with the satisfaction of exercising my mind.