« first  « prev  » next  » last 

Jump to:


Search Techniques, Data Structures and Code

1. 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!

An example Sudoku problem (rated hard)
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 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.

First branch of the decision tree
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.

Second branch of the decision tree
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.

Third branch of the decision tree
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.

Backtracking through the decision tree
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.

The solution to the example problem
Figure 6: The solution to the example problem


2. 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[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.

« first  « prev  » next  » last 

Jump to: