Enter your Logical Genetics login details here or **Register Now!**

## LoginEnter your Logical Genetics login details here or ## Recent Activity on the ForumsWiPi by ballista (Friday 20:11) WiPi by genious (Monday 15:03) WiPi by genious (Friday 05:58) Mono C# on the Raspberry Pi by genious (Monday 10:59) Google Maps API by genious (Monday 06:51) Interesting Linux Webcam Project by genious (Saturday 16:47) Mono C# on the Raspberry Pi by genious (Saturday 15:55) Mono C# on the Raspberry Pi by genious (Monday 06:58) ## Latest Photos
## Mobile Photo...
## Online Articles
- Hacked
- Evolution in a 3D Fitness Landscape
- Titanic Survivor Prediction
- Solving Sudoku Puzzles using Depth First Search
- Architecture of Artificial Neural Networks
- Evolutionary Algorithms
- Emergent Behaviour and Artificial Life
- Artificial Immune Systems and Negative Selection
- Return to the Animal Kingdom
- Neural Networks in Nature
## Search |
## Search Techniques, Data Structures and Code## 1. Depth First SearchFirstly, 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!
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 three branches 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.
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 4 shows the next step through the tree. We have two choices for square 0,3: 5 and 9. We select 5 and continue.
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.
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.
## 2. The Data StructuresThere 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[3] = 7 there are seven '4' symbols free for placement on the board; and if SymbolSet[8] = 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.## 3. 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.Fixed[c, r] then begin // if fixed then remove value from available symbol set Symbols.RemoveSymbol(ABoard[c, r]); end else begin // if this is not a fixed cell then clear it ABoard[c, r] := -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[c, r] := i; // if it fits if ABoard.OK[c, r] 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[c, r] := -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! Of course, the solution can take a few minutes. On the next page I'll talk briefly about the ways in which we could speed up the algorithm and the basic components of a depth first algorithm which make it useful for a huge array of real-world problems. There are also code downloads for the Sudoku project. |