Sudoku

Here, we will discuss

• a description of the sudoku puzzle and
• the backtracking algorithm.

The puzzle

The puzzle of sudoku is one consisting of a nine by nine grid of squares and the grid is divided up into three by three grids of three by three squares. Each row, column and sub-grid can only contain one instance of the digits 1 through 9 and some entries are given. A correct puzzle has enough entries to ensure a unique solution.

The algorithm

This is problem that is very appropriate for backtracking, as a digit in the wrong location often quickly shows that the solution is infeasable.

With n entries left,

• if there are no entries, n = 0, left, we are finished, indicate succes;
• otherwise, find a square that is not yet filled, and
• for each digit from 1 to 9,
• place the digit in the digit in that square and see whether the the solution is feasible, and if so call backtracking algorithm recursively, where
• if the algorithm indicates success, we are finished,
• otherwise, try the next digit; and
• if no digit works, there is no solution.

This algorithm is implemented in the source directory.