Solving techniques

The program contains several algorithms for solving grids. Although they can be used to just update the grid automatically they are meant to be used with the program's graphcial hint system to enable the user to learn to recognise the patterns involved. Before the algorithms/patterns can be described it is necessary to define some terms.

Terminology

There appear to be no universally agreed terms for describing the components of a Sudoku puzzle or for the names of the algorithms used to find their solutions. However, a consensus may emerge through the Sudopedia initiative. Initially I invented two new terms of my own (alts and 9mers). For this version of the web site and program I have decided to abandon "alts" for "candidates", but have yet to come to terms with using "house" instead of 9mer. So 9mer is retained, at least for now, and is defined below. Initially I used "square" where the sudopedia site uses "box", so I've now switched to their defintion, as for them, "square" is an alias for cell. I am not entirely happy with the typical defintion of the Sudoku "Rule" such as "Complete the grid in such a way that each row, column and box contain digits 1-9." For now I've stuck with my original two "rules" as I think they make explanation easier. The terms used here are defined below. This is the pedantic bit.

A Sudoku puzzle is a grid of 81 cells arranged in 9 rows and 9 columns which are partitioned into 9 3x3 boxes. In a correctly completed puzzle, nine symbols, generally represented as the numbers 1-9, each occur exactly once in each row, column and box. The puzzle setter provides a grid in which some (usually around 28) of the cells are set (clues or givens); the solver tries to set the rest.

Each row, column or box in a Sudoku grid is a termed a 9mer. Each cell is therefore a member of three 9mers: one row, one column and one box. There are twenty seven 9mers in a Sudoku grid. The more common term for a 9mer is a house but several others are in use.

Rule 1

Each of the nine symbols can occur only once in each 9mer.

Because there are 9 symbols and 9 cells in a 9mer(!), a corollary of Rule 1 is as follows.

Rule 2

Each of the 9 symbols must occur in every 9mer.

Algorithms

The algorithms are described roughly in order of complexity. They rely only on two ideas: Rule 1: that any symbol can occur only once in each 9mer, and, Rule 2: given that there are also nine symbols, the necessity for each of the 9 symbols to occur in each 9mer.

Simple filter

This is the most obvious algorithm, and its repeated application, in combination with setting singles, is sufficient to produce a solution for the simplest puzzles.

The algorithm proceeds as follows: for each cell remove any candidates which are already used by cells in the same row, column or box. If any cell is left with a single candidate, set the cell symbol accordingly (this is termed "setting singles").

Note that this algorithm is automatically applied exhaustively before any of the more complex algorithms are searched for. This can be achieved explicitly by use of the "s" button in the Toolbar.

Singles

This "algorithm" is included here only for completeness and is not offered as a separate option within the program. If a cell has only one remaining candidate, then it can be set to that symbol. Note that the Simple filter automatically detects and sets singles.