The game *sudoku* is a logic puzzle. The idea of the puzzle is
to take a partially-filled 9 x 9 square, such as the one shown above,
and fill in the missing cells such that numbers 1 through 9 are
assigned uniquely for:

- each row,
- each column,
- and each of the 9 3 x 3 squares

(Here, we will adopt the convention that the initial values supplied are in black, and the values to be assigned by the puzzle solver are shown in gray, respectively.)

The goal for the puzzle solver is to not to simply fill in the missing
numbers but to find a *logically-justifiable* way of
determining the missing numbers *without resorting to guessing
their values*. In other words, the puzzle should be solved using
logic methods.

This program (written as an illustration of logical reasoning) shows you how to solve these puzzles in a step-by-step manner, justifying each number assignment with respect to the three constraints.

[By the way, the program was written using *Sicstus Prolog* for
the logic engine and the *TCK/TK* toolkit for the user
interface elements.]

We can determine the possible values for each cell in the initial puzzle as shown below:

We will use the convention of numbering the cells from left to right
and top to bottom with respect to row and column positions
(*row*,*column*) starting with position 1.

For example, in the above diagram, the top-left corner, namely cell (1,1), has 4 possible values [1,4,7,9], as shown using the little numbers, repeated below.

Adjacent cells (1,2), (2,1) and (2,2) have supplied (unique) values 2, 5 and 8, respectively.

The missing possibilities for cell (1,1), namely [2,3,5,6,8], are excluded by the row, column and 3 x 3 square uniqueness constraints: i.e. they are already taken up somewhere else either in column 1 ([5,3,6]), row 1 ([2,6,8]) or the 3 x 3 sub-square delimited by cells (1,1) through (3,3) ([2,5,8]).

This program will winnow the available choices for cell (1,1) down to
just 1 through *reasoning by contradiction* using one of a few
heuristics. The program will display its steps in the reasoning
process using both text messages and graphical illustration. Examples
are given below of each type of heuristic.

Click on the various sections below for further information:

- Heuristic 1a: Simple row, column or 3 x 3 area inconsistency. (Only red highlighting is used.)
- Heuristic 1b: Row, column or 3 x 3 area insufficiency. (Blue and red highlighting is used.)
- Heuristic 2: Row, column or 3 x 3 area set cover elimination. (Green and red highlighting is used.)
- Heuristic 3: Unique row/column combination. (Gold highlighting is used.)
- Heuristic 4: Unique mention in row, column or 3 x 3 area. (Brown and red highlighting is used.)
- Heuristic 1+: Boosted version of the inconsistency/insufficiency checker factoring in the two uniqueness heuristics. (Multiple highlighting is used.)

- Example puzzles and their solutions supplied with the program.
- The "Unsolvable 11" from SudokuList. Solutions.

Suggestions and comments to sandiway at email dot arizona dot edu.

Up