SuDoKu
Introduction (Introduction nicked from the Wikipedia entry)
Sudoku (Japanese: 数独, sūdoku), sometimes spelled Su Doku, is a placement puzzle, also known as Number Place in the United States. The aim of the puzzle is to enter a numeral from 1 through 9 in each cell of a grid, most frequently a 9×9 grid made up of 3×3 subgrids (called "regions"), starting with various numerals given in some cells (the "givens"). Each row, column and region must contain only one instance of each numeral. Completing the puzzle requires patience and logical ability. Its grid layout is reminiscent of other newspaper puzzles like crosswords and chess problems. Sudoku initially became popular in Japan in 1986 and attained international popularity in 2005.
Programming
I have developed a simple but automated solver for SuDoKu. This was written in C using a recursive procedure - the result is something that is not very efficient (though still plenty good enough to solve most puzzles in under a second) but which is very easy to understand. Basically, the three main steps are:
- Scan through the matrix to identify "legal" moves for each of the blank squares
- Fill out the first blank square encountered with one of these legal moves.
- Solve the resulting matrix (and back out a level if no
solution is possible)
There is also an (extremely crude) GUI which uses wxwidgets: wxsudoku.tgz
Though this is probably too crude and disorganised to be of much interest to anyone but myself :-)
Oh and yes, all of this is available under the GPL - I'll get round to distributing a copy of the license with the source eventually! Anyway, for what it's worth, here's a screenshot:
