« first  « prev 

Jump to:


Conclusions and Downloads

1. The Depth First Search and How To Solve Sudoku Faster


I've deliberately avoided using any domain knowledge to create my example Sudoku solver. My intentions were to show how depth first search can be applied to just about any problem using a simple representation of the problem (the Sudoku board in this case) and a representation of how to take actions to alter the problem representation (by placing symbols on the board in this case).

We can then solve a whole host of problems by traversing the decision tree created by applying actions to our problem representation.

By avoiding the use of any heuristics in my search algorithm I have also neatly demonstrated one of the main flaws of the depth first search technique: it can be incredibly slow. The more complex the problem and the more operations we can perform at each branch of the tree, the more time we need to traverse each branch. Luckily for me, Sudoku puzzles are simple enough to be solved within a reasonable amount of time, so they're great as a demonstration.

Domain knowledge holds the key to speeding up this problem solving technique. We can use what we know about how humans solve the problem to create a heuristic to choose the most promising branch of the decision tree first, thus (hopefully) avoiding the traversal of huge fruitless subtrees.

For Sudoku puzzles, a promising heuristic lies in the order in which we choose the next square. My algorithm blindly picks the next avaiable square based on an arbitrary left-to-right-top-to-bottom traversal of the board. If, instead, we always choose the square which has the lowest number of possible branches (i.e. where the fewest symbols can legally be placed) then we decrease the number of branches we traverse at each level of the tree.

Using this simple heuristic should dramatically increase the speed we can solve Sudoku puzzles. Code listings follow, so why not give it a go yourself?

2. The Sudoku Application (and Downloads)


Feel free to download the Soduko Solver and all associated code. If you do play around with it, please credit "Logical Genetics". Also, be aware that it comes without warranty (as per usual)!

The Sudoku applciation is very simple indeed. There are two tabs on the main form, one is used to set up the problem and one to enter the solution. Use the "Problem" tab to enter values for the fixed cells and then switch to the "Solution" tab to solve the problem - either by hand or using the AI solver.

Sudoku problems can be loaded and saved using the "Load" and "Save" buttons. Files are in a very basic ASCII format and have the extension ".sudoku".

The "Play" button starts the AI solving code, which should be visible (albeit flickery) as it runs.

The Sudoku Application
Figure 1: The Sudoku Application

« first  « prev 

Jump to: