Backtracking method

The core of the OpenSudokuLib engine to generate sudoku configurations is the method backTrackingRows, a backtracking method which enables the class to find a valid sudoku case.

Backtracking is a recursive algorithm which tries to find a solution by trying a certain partial path and extending it step by step until a final solution is being found. If the partial path does not fulfill the criteria of a valid solution, we have to step back and try a different path from the point where it still was satisfying the criteria.

An example for the backtracking method

Let us imagine a set of interconnected points building a network as shown in the image. Finding a path from point 1 to point 5 riding along the edges from point to point can be easily done using the backtracking method. The algorithm allows us to randomly choose the connection to be used to reach the next point, as long as the selected link does not lead us to the point we came from.

maze sketch

The crucial part of the algorithm is when we can not opt for any other edge to be followed because we reached a dead end. For example choosing the path 1 – A – 2 – A will lead us to such a dead end. In that case we have to step back and return to the point we came from right before to be able to try another link we did not choose before. Returning to our example, this means to return to point 2 and choose the next path 1 – A – 2 – B which leads us to point 4.

Insisting in this procedure leads us sooner or later to the target point and tells us a valid path through the maze.

Prerequisites to use the backtracking method

This simple example shows that we basically choose a path and extend it step by step by trial and error until we get a solution. If the path at any time does not fulfill the criteria, we step back and try another one, omitting all paths we already discarded. This implies that for every extension of the partial path we can evaluate whether the actual position is valid or not. Otherwise we will not be able to discard the invalid paths. In the example an invalid path leads us to a dead end. Also we have to be able to remember the attempts to be able to discard a path which has been already followed. And finally we have to be able to check in every step whether we already found a final solution.

How does it apply to the sudoku case?

Now finding a valid sudoku case is very similar to find a way through a labyrinth as shown above. Imagine that every point in the network is a field in a 4×4 sudoku square and following a edge in the labyrinth means to fill in a certain number into the relevant field. From each point you will have 4 options to follow instead of only 2. For each possible number from 1-4 we could fill in a sudoku field, we can follow one option.

We will begin with the first row of the sudoku case filled random with all numbers from 1-4. The rest of the rows will be figured out with the backtracking algorithm based on this first row. We will fill in a random number in the first field, check whether the sudoku is still valid and if so we go on filling the next field random.

4x4 sudoku backtracking example

As shown in the figure, filling the first field of the second row with 1 or 2 will not lead to a valid sudoku case as filling the number 1 leads to a repetition in the first column and filling the number 2 leads to a repetition in the upper left inner square.

Only using the numbers 3 or 4 in the first field of the second row is a possible path where we expect a valid configuration. In the figure we choose the number 3 as option to be followed. For the second field of the second row we iterate the procedure. This will be repeated until we are still able to choose valid options through our imaginary maze.

If at any time we are not able to fill in a number from 1-4 because none of them does fulfill the criteria for a valid sudoku case, we will step back to the field before and try the next number to be filled in.

These steps will be repeated until all sudoku fields are filled.

  1. Did we fill already all sudoku fields? If yes, then leave the loop. We did it!!!
  2. Did we already try all possible numbers? If yes, then step back and execute BackTrackingRows(n-1) trying a different number
  3. Set next field n
  4. Is the sudoku case valid by now? If yes, execute recursive call of BackTrackingRows(n+1) to set the next field

You will find the source code of the described method backTrackingRows in class Sudoku of the OpenSudokuLib engine, which is well documented. You can download the source code from Sourceforge or get it from the download section of this website (adf.ly).
You will find more information about the sudoku generator in this article.