In this article I hope to show how we can develop a solution to just about any problem using one of the most simple and generic problem solving techniques: a simple depth first search. I’m going to use Sudoku puzzles as an example.
Though I can guarantee that it will solve any Sudoku puzzle, I’m not trying to say that the technique I’m using is in any way the fastest or the most impressive. In fact, I can start this article by categorically stating that this is not the best way to solve sudoku. What I can say about the depth first method, however, is that it could be one of the most simple and generic ways to solve sudoku puzzles!
This page continues with a quick introduction to Sudoku puzzles and how people tend to solve them. The next page talks about depth-first search and how I applied it in my Suduko solving application. Finally, the third page has some concluding discussion on why this isn’t the optimum method and what we could do to improve it, along with code downloads.
Sudoku has recently become a very popular puzzle and has started to appear in just about every national newspaper alongside the crossword. The basic rules of the game are very simple, we must fill every square in a 9×9 grid with one of the digits 1-9. We are constrained by rules which state that no two of the same number can appear on the same row or column, or within the same 3×3 box (see figure).
Generally the puzzles will have enough numbers filled in to get us started. Those numbers are shown in Figure 1 in grey boxes. Our job is to fill in the white boxes.
Figure 1: A simple Sudoku puzzle
Figure 2 shows a possible first step. The bottom row has two numbers missing, 8 and 1. The 1 must go in the left hand box, since there is already a 1 in the bottom right 3×3 square. Therefore, the 8 must go on the right.
Figure 2: First steps to solving the puzzle
Figure 3 shows how we can take another step towards a solution. We must have a 2 in each of the 3×3 squares. Since we have a few 2’s on the board already we can easily see where the 2 must go in the middle-left 3×3 square.
Figure 3: Second step to solving the puzzle
We can continue in this way until all the squares have been filled. Our answers will help us to make more decisions as we go along.
Depth First Search
Firstly, here’s a simple Sudoku problem to use as an example. The depth-first technique can work with any puzzle, but this is quite a simple one so the diagrams should be smaller!
Figure 1: An example Sudoku problem (rated hard)
The depth first search algorithm traverses a “decision tree”. The decision tree isn’t a data structure in itself, it’s just a handy way to visualise the way that the algorithm traverses the problem space.
We start at the first free square on the board, row 0 (the top row) column 1 (the second column from the left). This is the first empty square on the board. There are a number of symbols we can use for this square: 1, 7 and 9; all other symbols would break the rules of Sudoku. Therefore there are threebranches to investigate – see figure 2. The depth first algorithm attempts to solve the problem by traversing down the left hand side of the decision tree, so we investigate the first branch by placing a 1 in square 0,1.
Figure 2: First branch of the decision tree
Once we’ve guessed at a symbol for the first square (0,1) we must attempt to find a symbol to go in square 0,2 (the second free square as we traverse the board in a raster-scan style). At this point we have two options, placing either a 7 or a 9 in the square. Therefore the tree branches into two here; we take the left hand branch by placing a 7 in square 0,2 – see figure 3.
Figure 3: Second branch of the decision tree
Figure 4 shows the next step through the tree. We have two choices for square 0,3: 5 and 9. We select 5 and continue.
Figure 4: Third branch of the decision tree
At some point one of two things will happen, either…
- We have filled every square on the board and therefore solved the puzzle
- We reach a square where we can’t place any symbol. In this case we backtrack by moving back to the previous square and trying the next possible symbol
Figure 5 shows us backtracking. The algorithm has investigated every possible branch with 1 in the first square and none lead to a solution. Therefore we try again with a 7 in the first square.
Figure 5: Backtracking through the decision tree
Note: the solution (shown in figure 6) does actually have a 1 in the first square. The backtracking shown in figure 5 is shown as an example, just to give you an idea of what happens – it doesn’t occur in this part of the tree for this particular problem.
Figure 6: The solution to the example problem
The Data Structures
There are two key data structures to understand before we look at the tree traversal code. Firstly, the TSudokuBoard class is used to represent the board. It has three properties which are of particular interest…
- Board[col, row] : Integer
A 2D array which exposes the symbols on each square. 0 – 8 represent the symbols (add 1!) and -1 represents an empty square.
- Fixed[col, row] : Boolean Another 2D array which we can use to see if a particular square is fixed (i.e. set as part of the initial puzzle) or free.
- OK[col, row] : Boolean We can use this array to check whether he symbol on a given square is “legal” within the rules of Sudoku.
Most other properties and methods of the board class are used for display or just for data storage.
The second key data structure is the TSudokuSymbolSet. This is used within the solution code to represent the symbols which we have not yet placed on the board. Its default array property is used to store the number of each symbol available for placement on the board, so if SymbolSet = 7 there are seven ‘4’ symbols free for placement on the board; and if SymbolSet = 0 then we’ve placed all available ‘9’s on the board and there are none left. The TSudokuSymbolSet also exposes methods to increment and decrement the symbol counts and to check whether there are any symbols left at all.
Solving Sudoku – The Code!
We use a recursive method to traverse the decision tree, recursing each time we step down through the tree and unwinding each time we backtrack, but first there are some initialisation tasks to get out of the way.
The TSudokuSolver.Solve method is called by the GUI when we click the solve button. This method prepares the initial symbol set and starts recursion through the problem space. the symbol set is first initialised by assigning a count of 9 for each of the nine symbols. We then travese the board, clearing all free squares and removing symbols in fixed squares from our initial symbol set.
Before the recursive “DoSolving” method is called, we are in a position where all non-fixed squares on the board are empty and the symbol set contains the set of symbols we need to place on the board in order to solve the problem.
procedure TSudokuSolver.Solve(ABoard: ISudokuBoard); var i, r, c : Integer; Symbols : ISudokuSymbolSet; begin // Create symbol set Symbols := TSudokuSymbolSet.Create(ABoard.SymbolCount); // Populate with nne of every symbol (as if board were blank) for i := 0 to Symbols.Count - 1 do Symbols[i] := (ABoard.Width * ABoard.Height) div ABoard.SymbolCount; // for each square on board for c := 0 to ABoard.Width - 1 do begin for r := 0 to ABoard.Height - 1 do begin if ABoard.Fixedthen begin // if fixed then remove value from available symbol setSymbols.RemoveSymbol(ABoard); end else begin // if this is not a fixed cell then clear it ABoard := -1; end; end; end; // Start the recursive solving process DoSolving(ABoard, Symbols); end;
The recursive “DoSolving” method is very simple too. The comments should explain the logic behind it…
function TSudokuSolver.DoSolving(ABoard: ISudokuBoard; ASymbols: ISudokuSymbolSet): Boolean; var i, r, c : Integer; NewSymbols : ISudokuSymbolSet; begin // Update the user interface to show our progress Step; // if we've run out of symbols then we've solved the problem! if ASymbols.IsEmpty then begin Result := True; Exit; end; // c (column) and r (row) are variable parameters FindFirstEmptySquare(ABoard, c, r); // for each symbol for i := 0 to ASymbols.Count - 1 do begin // if there are some of these left if ASymbols[i] > 0 then begin // try it in this location ABoard := i; // if it fits if ABoard.OK then begin // Create symbol set with this symbol removed NewSymbols := ASymbols.Clone; NewSymbols.RemoveSymbol(i); // Recurse if DoSolving(ABoard, NewSymbols) then begin // if "DoSolving" returned true then we've solved the problem - so return true. Result := True; Exit; end; end; end; end; // if we failed to place any of the symbols then clear the square // and backtrack ABoard := -1; Result := False; end;
And that’s all there is to it! Once the outer “DoSolving” method returns a value of true the board will contain the solution to the problem. Simple as that!
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?
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.
Figure 1: The Sudoku Application