Sudoku Solver for 16x16 grids

Ordinary sudoku is a 9x9 grid further separated into 3x3 blocks of 3x3 cells. Hex sudoku is 16x16 cells seperated into 4x4 blocks of 4x4 cells.

I will not go much into what sudoku is or how it is played. I will just point to wikipedias article which explains it in great detail. The rules for 16x16 are the same as for 9x9 except the numbers are not 1 to 9 but 1 to 16, or in hexa decimal numbers 0 to F.

My solver can either do a simple depth first search for a solution which takes approx. 600 million moves, or it can employ a simple heuristics which take approx. 64 thousand moves. On my system (Intel core2dua 1.8MHz) the simple search takes 5 minutes and the more intelligent one takes 2 seconds.

I am not terribly interested in playing those little puzzles, so I didn't bother to think up a brilliant strategy for solving the problem. I simply try placing a number in the next cell with the fewest valid options. If there is a cell which can only take the value 5 without breaking the rules and another cell can take both the values 7 and 2 then I start with the one which can only take a 5. That is actually enough to quickly cut away at the search tree.

My solver is quite a lot faster than other solvers I have compared it with. That is mainly due to the fact that there is no heap allocation and de-allocation when the search is performed. Everything is stored inside small pre allocated arrays. They take around 1,5 kB of memory and cut the processing time down very much. When valid moves are sought, they can generally be found from a few costant time array lookups, and when a move is taken it is pushed to a stack which is again implemented as a fixed size array.

The code is fairly well documented since it was turned in as the solution for an assignment in a graduate student course in artificial intelligence. I will not spend more time right now explaining the project, but let the interested reader get the source code and executable and look at it. The code is c# .net 2.0 written in vs2005.

If you try the program then note that "load game" means to load the comma separated string at the bottom into a board as an initial problem. Hitting "solve" will start the solver with either heuristics or no heuristics, and when solving the current state of the board will be displayed every n iterations, where n is a user defined number. The smaller n then slower the solution will be calculated.

I realize that the above description is very brief and fairly rough in its form. I might come back some day and clean it up. Till then...

Thomas Grønneløv,
Apr 12, 2011, 12:26 PM