25.7. Sudoku Example: Sudoku.drl

There are three types of solving rules in Sudoku.drl: one group handles the allocation of a number to a cell, another group detects feasible allocations, and the third group eliminates values from candidate sets.

The rules set a value, eliminate a value from Cell and retract setting depend on the presence of a Setting object.

Set a value handles the assignment to the cell and the operations for removing the value from the "free" sets of the cell's three groups. Also, it decrements a counter that, when zero, returns control to the Java application that has called fireUntilHalt().

Eliminate a value from Cell reduces the candidate lists of all cells that are related to the newly assigned cell.

Retract setting retracts the triggering Setting fact when all of the eliminations have been made.

There are just two rules that detect a situation where an allocation of a number to a cell is possible. Rule single fires for a Cell with a candidate set containing a single number. Rule hidden single fires when there is a cell containing a candidate but this candidate is absent from all other cells in one of the groups the cell belongs to. Both rules create and insert a Setting fact.

Rules from the largest group of rules implement, singly or in groups of two or three, various solving techniques, as they are employed when solving Sudoku puzzles manually.

Rule naked pair detects two identical candidate sets in two cells of a group. These two values may be removed from all other candidate sets of that group.

In hidden pair in rules, the rules look for a subset of two numbers in exactly two cells of a group, with neither value occurring in any of the other cells of this group. This means that all other candidates can be eliminated from the two cells harbouring the hidden pair.

A pair of rules deals with X-wings in rows and columns. When there are only two possible cells for a value in each of two different rows (or columns) and these candidates are in the same columns (or rows), then all other candidates for this value in the columns (or rows) can be eliminated. The conditions same or only result in patterns with suitable constraints or prefixed with not.

The rule pair intersection removal... is based on the restricted occurrence of a number within one square, either in a single row or in a single column. This means that this number must be in one of those two or three cells of the row or column. It can be removed from the candidate sets of all other cells of the group. The pattern establishes the restricted occurrence and then fires for each cell outside the square and within the same cell file.

To solve very difficult grids, the rule set would need to be extended with more complex rules. (Ultimately, there are puzzles that cannot be solved except by trial and error.)