21.8. Sudoku example decisions (complex pattern matching, callbacks, and GUI integration)
The Sudoku example decision set, based on the popular number puzzle Sudoku, demonstrates how to use rules in Red Hat Decision Manager to find a solution in a large potential solution space based on various constraints. This example also shows how to integrate Red Hat Decision Manager rules into a graphical user interface (GUI), in this case a Swing-based desktop application, and how to use callbacks to interact with a running decision engine to update the GUI based on changes in the working memory at run time.
The following is an overview of the Sudoku example:
-
Name:
sudoku
-
Main class:
org.drools.examples.sudoku.SudokuExample
(insrc/main/java
) -
Module:
drools-examples
- Type: Java application
-
Rule files:
org.drools.examples.sudoku.*.drl
(insrc/main/resources
) - Objective: Demonstrates complex pattern matching, problem solving, callbacks, and GUI integration
Sudoku is a logic-based number placement puzzle. The objective is to fill a 9x9 grid so that each column, each row, and each of the nine 3x3 zones contains the digits from 1 to 9 only one time. The puzzle setter provides a partially completed grid and the puzzle solver’s task is to complete the grid with these constraints.
The general strategy to solve the problem is to ensure that when you insert a new number, it must be unique in its particular 3x3 zone, row, and column. This Sudoku example decision set uses Red Hat Decision Manager rules to solve Sudoku puzzles from a range of difficulty levels, and to attempt to resolve flawed puzzles that contain invalid entries.
Sudoku example execution and interaction
Similar to other Red Hat Decision Manager decision examples, you execute the Sudoku example by running the org.drools.examples.sudoku.SudokuExample
class as a Java application in your IDE.
When you execute the Sudoku example, the Drools Sudoku Example
GUI window appears. This window contains an empty grid, but the program comes with various grids stored internally that you can load and solve.
Click File → Samples → Simple to load one of the examples. Notice that all buttons are disabled until a grid is loaded.
図21.19 Sudoku example GUI after launch
When you load the Simple example, the grid is filled according to the puzzle’s initial state.
図21.20 Sudoku example GUI after loading Simple sample
Choose from the following options:
Click Solve to fire the rules defined in the Sudoku example that fill out the remaining values and that make the buttons inactive again.
図21.21 Simple sample solved
Click Step to see the next digit found by the rule set. The console window in your IDE displays detailed information about the rules that are executing to solve the step.
Step execution output in the IDE console
single 8 at [0,1] column elimination due to [1,2]: remove 9 from [4,2] hidden single 9 at [1,2] row elimination due to [2,8]: remove 7 from [2,4] remove 6 from [3,8] due to naked pair at [3,2] and [3,7] hidden pair in row at [4,6] and [4,4]
Click Dump to see the state of the grid, with cells showing either the established value or the remaining possibilities.
Dump execution output in the IDE console
Col: 0 Col: 1 Col: 2 Col: 3 Col: 4 Col: 5 Col: 6 Col: 7 Col: 8 Row 0: 123456789 --- 5 --- --- 6 --- --- 8 --- 123456789 --- 1 --- --- 9 --- --- 4 --- 123456789 Row 1: --- 9 --- 123456789 123456789 --- 6 --- 123456789 --- 5 --- 123456789 123456789 --- 3 --- Row 2: --- 7 --- 123456789 123456789 --- 4 --- --- 9 --- --- 3 --- 123456789 123456789 --- 8 --- Row 3: --- 8 --- --- 9 --- --- 7 --- 123456789 --- 4 --- 123456789 --- 6 --- --- 3 --- --- 5 --- Row 4: 123456789 123456789 --- 3 --- --- 9 --- 123456789 --- 6 --- --- 8 --- 123456789 123456789 Row 5: --- 4 --- --- 6 --- --- 5 --- 123456789 --- 8 --- 123456789 --- 2 --- --- 9 --- --- 1 --- Row 6: --- 5 --- 123456789 123456789 --- 2 --- --- 6 --- --- 9 --- 123456789 123456789 --- 7 --- Row 7: --- 6 --- 123456789 123456789 --- 5 --- 123456789 --- 4 --- 123456789 123456789 --- 9 --- Row 8: 123456789 --- 4 --- --- 9 --- --- 7 --- 123456789 --- 8 --- --- 3 --- --- 5 --- 123456789
The Sudoku example includes a deliberately broken sample file that the rules defined in the example can resolve.
Click File → Samples → !DELIBERATELY BROKEN! to load the broken sample. The grid starts with some issues, for example, the value 5
appears two times in the first row, which is not allowed.
図21.22 Broken Sudoku example initial state
Click Solve to apply the solving rules to this invalid grid. The associated solving rules in the Sudoku example detect the issues in the sample and attempts to solve the puzzle as far as possible. This process does not complete and leaves some cells empty.
The solving rule activity is displayed in the IDE console window:
Detected issues in the broken sample
cell [0,8]: 5 has a duplicate in row 0 cell [0,0]: 5 has a duplicate in row 0 cell [6,0]: 8 has a duplicate in col 0 cell [4,0]: 8 has a duplicate in col 0 Validation complete.
図21.23 Broken sample solution attempt
The sample Sudoku files labeled Hard are more complex and the solving rules might not be able to solve them. The unsuccessful solution attempt is displayed in the IDE console window:
Hard sample unresolved
Validation complete. ... Sorry - can't solve this grid.
The rules that work to solve the broken sample implement standard solving techniques based on the sets of values that are still candidates for a cell. For example, if a set contains a single value, then this is the value for the cell. For a single occurrence of a value in one of the groups of nine cells, the rules insert a fact of type Setting
with the solution value for some specific cell. This fact causes the elimination of this value from all other cells in any of the groups the cell belongs to and the value is retracted.
Other rules in the example reduce the permissible values for some cells. The rules "naked pair"
, "hidden pair in row"
, "hidden pair in column"
, and "hidden pair in square"
eliminate possibilities but do not establish solutions. The rules "X-wings in rows"
, "`X-wings in columns"`, "intersection removal row"
, and "intersection removal column"
perform more sophisticated eliminations.
Sudoku example classes
The package org.drools.examples.sudoku.swing
contains the following core set of classes that implement a framework for Sudoku puzzles:
-
The
SudokuGridModel
class defines an interface that is implemented to store a Sudoku puzzle as a 9x9 grid ofCell
objects. -
The
SudokuGridView
class is a Swing component that can visualize any implementation of theSudokuGridModel
class. -
The
SudokuGridEvent
andSudokuGridListener
classes communicate state changes between the model and the view. Events are fired when a cell value is resolved or changed. -
The
SudokuGridSamples
class provides partially filled Sudoku puzzles for demonstration purposes.
This package does not have any dependencies on Red Hat Decision Manager libraries.
The package org.drools.examples.sudoku
contains the following core set of classes that implement the elementary Cell
object and its various aggregations:
-
The
CellFile
class, with subtypesCellRow
,CellCol
, andCellSqr
, all of which are subtypes of theCellGroup
class. The
Cell
andCellGroup
subclasses ofSetOfNine
, which provides a propertyfree
with the typeSet<Integer>
. For aCell
class, the set represents the individual candidate set. For aCellGroup
class, the set is the union of all candidate sets of its cells (the set of digits that still need to be allocated).In the Sudoku example are 81
Cell
and 27CellGroup
objects and a linkage provided by theCell
propertiescellRow
,cellCol
, andcellSqr
, and by theCellGroup
propertycells
(a list ofCell
objects). With these components, you can write rules that detect the specific situations that permit the allocation of a value to a cell or the elimination of a value from some candidate set.-
The
Setting
class is used to trigger the operations that accompany the allocation of a value. The presence of aSetting
fact is used in all rules that detect a new situation in order to avoid reactions to inconsistent intermediary states. -
The
Stepping
class is used in a low priority rule to execute an emergency halt when a"Step"
does not terminate regularly. This behavior indicates that the program cannot solve the puzzle. -
The main class
org.drools.examples.sudoku.SudokuExample
implements a Java application combining all of these components.
Sudoku validation rules (validate.drl)
The validate.drl
file in the Sudoku example contains validation rules that detect duplicate numbers in cell groups. They are combined in a "validate"
agenda group that enables the rules to be explicitly activated after a user loads the puzzle.
The when
conditions of the three rules "duplicate in cell …"
all function in the following ways:
- The first condition in the rule locates a cell with an allocated value.
- The second condition in the rule pulls in any of the three cell groups to which the cell belongs.
- The final condition finds a cell (other than the first one) with the same value as the first cell and in the same row, column, or square, depending on the rule.
Rules "duplicate in cell …"
rule "duplicate in cell row" when $c: Cell( $v: value != null ) $cr: CellRow( cells contains $c ) exists Cell( this != $c, value == $v, cellRow == $cr ) then System.out.println( "cell " + $c.toString() + " has a duplicate in row " + $cr.getNumber() ); end rule "duplicate in cell col" when $c: Cell( $v: value != null ) $cc: CellCol( cells contains $c ) exists Cell( this != $c, value == $v, cellCol == $cc ) then System.out.println( "cell " + $c.toString() + " has a duplicate in col " + $cc.getNumber() ); end rule "duplicate in cell sqr" when $c: Cell( $v: value != null ) $cs: CellSqr( cells contains $c ) exists Cell( this != $c, value == $v, cellSqr == $cs ) then System.out.println( "cell " + $c.toString() + " has duplicate in its square of nine." ); end
The rule "terminate group"
is the last to fire. This rule prints a message and stops the sequence.
Rule "terminate group"
rule "terminate group" salience -100 when then System.out.println( "Validation complete." ); drools.halt(); end
Sudoku solving rules (sudoku.drl)
The sudoku.drl
file in the Sudoku example contains three types of rules: 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. The first rule handles the assignment to the cell and the operations for removing the value from the free
sets of the three groups of the cell. This group also reduces a counter that, when zero, returns control to the Java application that has called fireUntilHalt()
.
The purpose of the rule "eliminate a value from Cell"
is to reduce the candidate lists of all cells that are related to the newly assigned cell. Finally, when all eliminations have been made, the rule "retract setting"
retracts the triggering Setting
fact.
Rules "set a value", "eliminate a value from a Cell", and "retract setting"
// A Setting object is inserted to define the value of a Cell. // Rule for updating the cell and all cell groups that contain it rule "set a value" when // A Setting with row and column number, and a value $s: Setting( $rn: rowNo, $cn: colNo, $v: value ) // A matching Cell, with no value set $c: Cell( rowNo == $rn, colNo == $cn, value == null, $cr: cellRow, $cc: cellCol, $cs: cellSqr ) // Count down $ctr: Counter( $count: count ) then // Modify the Cell by setting its value. modify( $c ){ setValue( $v ) } // System.out.println( "set cell " + $c.toString() ); modify( $cr ){ blockValue( $v ) } modify( $cc ){ blockValue( $v ) } modify( $cs ){ blockValue( $v ) } modify( $ctr ){ setCount( $count - 1 ) } end // Rule for removing a value from all cells that are siblings // in one of the three cell groups rule "eliminate a value from Cell" when // A Setting with row and column number, and a value $s: Setting( $rn: rowNo, $cn: colNo, $v: value ) // The matching Cell, with the value already set Cell( rowNo == $rn, colNo == $cn, value == $v, $exCells: exCells ) // For all Cells that are associated with the updated cell $c: Cell( free contains $v ) from $exCells then // System.out.println( "clear " + $v + " from cell " + $c.posAsString() ); // Modify a related Cell by blocking the assigned value. modify( $c ){ blockValue( $v ) } end // Rule for eliminating the Setting fact rule "retract setting" when // A Setting with row and column number, and a value $s: Setting( $rn: rowNo, $cn: colNo, $v: value ) // The matching Cell, with the value already set $c: Cell( rowNo == $rn, colNo == $cn, value == $v ) // This is the negation of the last pattern in the previous rule. // Now the Setting fact can be safely retracted. not( $x: Cell( free contains $v ) and Cell( this == $c, exCells contains $x ) ) then // System.out.println( "done setting cell " + $c.toString() ); // Discard the Setter fact. delete( $s ); // Sudoku.sudoku.consistencyCheck(); end
Two solving rules detect a situation where an allocation of a number to a cell is possible. The rule "single"
fires for a Cell
with a candidate set containing a single number. The rule "hidden single"
fires when no cell exists with a single candidate, but when a cell exists containing a candidate, this candidate is absent from all other cells in one of the three groups to which the cell belongs. Both rules create and insert a Setting
fact.
Rules "single" and "hidden single"
// Detect a set of candidate values with cardinality 1 for some Cell. // This is the value to be set. rule "single" when // Currently no setting underway not Setting() // One element in the "free" set $c: Cell( $rn: rowNo, $cn: colNo, freeCount == 1 ) then Integer i = $c.getFreeValue(); if (explain) System.out.println( "single " + i + " at " + $c.posAsString() ); // Insert another Setter fact. insert( new Setting( $rn, $cn, i ) ); end // Detect a set of candidate values with a value that is the only one // in one of its groups. This is the value to be set. rule "hidden single" when // Currently no setting underway not Setting() not Cell( freeCount == 1 ) // Some integer $i: Integer() // The "free" set contains this number $c: Cell( $rn: rowNo, $cn: colNo, freeCount > 1, free contains $i ) // A cell group contains this cell $c. $cg: CellGroup( cells contains $c ) // No other cell from that group contains $i. not ( Cell( this != $c, free contains $i ) from $cg.getCells() ) then if (explain) System.out.println( "hidden single " + $i + " at " + $c.posAsString() ); // Insert another Setter fact. insert( new Setting( $rn, $cn, $i ) ); end
Rules from the largest group, either individually or in groups of two or three, implement various solving techniques used for solving Sudoku puzzles manually.
The rule "naked pair"
detects identical candidate sets of size 2
in two cells of a group. These two values may be removed from all other candidate sets of that group.
Rule "naked pair"
// A "naked pair" is two cells in some cell group with their sets of // permissible values being equal with cardinality 2. These two values // can be removed from all other candidate lists in the group. rule "naked pair" when // Currently no setting underway not Setting() not Cell( freeCount == 1 ) // One cell with two candidates $c1: Cell( freeCount == 2, $f1: free, $r1: cellRow, $rn1: rowNo, $cn1: colNo, $b1: cellSqr ) // The containing cell group $cg: CellGroup( freeCount > 2, cells contains $c1 ) // Another cell with two candidates, not the one we already have $c2: Cell( this != $c1, free == $f1 /*** , rowNo >= $rn1, colNo >= $cn1 ***/ ) from $cg.cells // Get one of the "naked pair". Integer( $v: intValue ) from $c1.getFree() // Get some other cell with a candidate equal to one from the pair. $c3: Cell( this != $c1 && != $c2, freeCount > 1, free contains $v ) from $cg.cells then if (explain) System.out.println( "remove " + $v + " from " + $c3.posAsString() + " due to naked pair at " + $c1.posAsString() + " and " + $c2.posAsString() ); // Remove the value. modify( $c3 ){ blockValue( $v ) } end
The three rules "hidden pair in …"
functions similarly to the rule "naked pair"
. These rules detect a subset of two numbers in exactly two cells of a group, with neither value occurring in any of the other cells of the group. This means that all other candidates can be eliminated from the two cells harboring the hidden pair.
Rules "hidden pair in …"
// If two cells within the same cell group contain candidate sets with more than // two values, with two values being in both of them but in none of the other // cells, then we have a "hidden pair". We can remove all other candidates from // these two cells. rule "hidden pair in row" when // Currently no setting underway not Setting() not Cell( freeCount == 1 ) // Establish a pair of Integer facts. $i1: Integer() $i2: Integer( this > $i1 ) // Look for a Cell with these two among its candidates. (The upper bound on // the number of candidates avoids a lot of useless work during startup.) $c1: Cell( $rn1: rowNo, $cn1: colNo, freeCount > 2 && < 9, free contains $i1 && contains $i2, $cellRow: cellRow ) // Get another one from the same row, with the same pair among its candidates. $c2: Cell( this != $c1, cellRow == $cellRow, freeCount > 2, free contains $i1 && contains $i2 ) // Ascertain that no other cell in the group has one of these two values. not( Cell( this != $c1 && != $c2, free contains $i1 || contains $i2 ) from $cellRow.getCells() ) then if( explain) System.out.println( "hidden pair in row at " + $c1.posAsString() + " and " + $c2.posAsString() ); // Set the candidate lists of these two Cells to the "hidden pair". modify( $c1 ){ blockExcept( $i1, $i2 ) } modify( $c2 ){ blockExcept( $i1, $i2 ) } end rule "hidden pair in column" when not Setting() not Cell( freeCount == 1 ) $i1: Integer() $i2: Integer( this > $i1 ) $c1: Cell( $rn1: rowNo, $cn1: colNo, freeCount > 2 && < 9, free contains $i1 && contains $i2, $cellCol: cellCol ) $c2: Cell( this != $c1, cellCol == $cellCol, freeCount > 2, free contains $i1 && contains $i2 ) not( Cell( this != $c1 && != $c2, free contains $i1 || contains $i2 ) from $cellCol.getCells() ) then if (explain) System.out.println( "hidden pair in column at " + $c1.posAsString() + " and " + $c2.posAsString() ); modify( $c1 ){ blockExcept( $i1, $i2 ) } modify( $c2 ){ blockExcept( $i1, $i2 ) } end rule "hidden pair in square" when not Setting() not Cell( freeCount == 1 ) $i1: Integer() $i2: Integer( this > $i1 ) $c1: Cell( $rn1: rowNo, $cn1: colNo, freeCount > 2 && < 9, free contains $i1 && contains $i2, $cellSqr: cellSqr ) $c2: Cell( this != $c1, cellSqr == $cellSqr, freeCount > 2, free contains $i1 && contains $i2 ) not( Cell( this != $c1 && != $c2, free contains $i1 || contains $i2 ) from $cellSqr.getCells() ) then if (explain) System.out.println( "hidden pair in square " + $c1.posAsString() + " and " + $c2.posAsString() ); modify( $c1 ){ blockExcept( $i1, $i2 ) } modify( $c2 ){ blockExcept( $i1, $i2 ) } end
Two rules deal with "X-wings"
in rows and columns. When only two possible cells for a value exist in each of two different rows (or columns) and these candidates lie also in the same columns (or rows), then all other candidates for this value in the columns (or rows) can be eliminated. When you follow the pattern sequence in one of these rules, notice how the conditions that are conveniently expressed by words such as same
or only
result in patterns with suitable constraints or that are prefixed with not
.
Rules "X-wings in …"
rule "X-wings in rows" when not Setting() not Cell( freeCount == 1 ) $i: Integer() $ca1: Cell( freeCount > 1, free contains $i, $ra: cellRow, $rano: rowNo, $c1: cellCol, $c1no: colNo ) $cb1: Cell( freeCount > 1, free contains $i, $rb: cellRow, $rbno: rowNo > $rano, cellCol == $c1 ) not( Cell( this != $ca1 && != $cb1, free contains $i ) from $c1.getCells() ) $ca2: Cell( freeCount > 1, free contains $i, cellRow == $ra, $c2: cellCol, $c2no: colNo > $c1no ) $cb2: Cell( freeCount > 1, free contains $i, cellRow == $rb, cellCol == $c2 ) not( Cell( this != $ca2 && != $cb2, free contains $i ) from $c2.getCells() ) $cx: Cell( rowNo == $rano || == $rbno, colNo != $c1no && != $c2no, freeCount > 1, free contains $i ) then if (explain) { System.out.println( "X-wing with " + $i + " in rows " + $ca1.posAsString() + " - " + $cb1.posAsString() + $ca2.posAsString() + " - " + $cb2.posAsString() + ", remove from " + $cx.posAsString() ); } modify( $cx ){ blockValue( $i ) } end rule "X-wings in columns" when not Setting() not Cell( freeCount == 1 ) $i: Integer() $ca1: Cell( freeCount > 1, free contains $i, $c1: cellCol, $c1no: colNo, $ra: cellRow, $rano: rowNo ) $ca2: Cell( freeCount > 1, free contains $i, $c2: cellCol, $c2no: colNo > $c1no, cellRow == $ra ) not( Cell( this != $ca1 && != $ca2, free contains $i ) from $ra.getCells() ) $cb1: Cell( freeCount > 1, free contains $i, cellCol == $c1, $rb: cellRow, $rbno: rowNo > $rano ) $cb2: Cell( freeCount > 1, free contains $i, cellCol == $c2, cellRow == $rb ) not( Cell( this != $cb1 && != $cb2, free contains $i ) from $rb.getCells() ) $cx: Cell( colNo == $c1no || == $c2no, rowNo != $rano && != $rbno, freeCount > 1, free contains $i ) then if (explain) { System.out.println( "X-wing with " + $i + " in columns " + $ca1.posAsString() + " - " + $ca2.posAsString() + $cb1.posAsString() + " - " + $cb2.posAsString() + ", remove from " + $cx.posAsString() ); } modify( $cx ){ blockValue( $i ) } end
The two rules "intersection removal …"
are based on the restricted occurrence of some 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 and 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 of the square and within the same cell file.
Rules "intersection removal …"
rule "intersection removal column" when not Setting() not Cell( freeCount == 1 ) $i: Integer() // Occurs in a Cell $c: Cell( free contains $i, $cs: cellSqr, $cc: cellCol ) // Does not occur in another cell of the same square and a different column not Cell( this != $c, free contains $i, cellSqr == $cs, cellCol != $cc ) // A cell exists in the same column and another square containing this value. $cx: Cell( freeCount > 1, free contains $i, cellCol == $cc, cellSqr != $cs ) then // Remove the value from that other cell. if (explain) { System.out.println( "column elimination due to " + $c.posAsString() + ": remove " + $i + " from " + $cx.posAsString() ); } modify( $cx ){ blockValue( $i ) } end rule "intersection removal row" when not Setting() not Cell( freeCount == 1 ) $i: Integer() // Occurs in a Cell $c: Cell( free contains $i, $cs: cellSqr, $cr: cellRow ) // Does not occur in another cell of the same square and a different row. not Cell( this != $c, free contains $i, cellSqr == $cs, cellRow != $cr ) // A cell exists in the same row and another square containing this value. $cx: Cell( freeCount > 1, free contains $i, cellRow == $cr, cellSqr != $cs ) then // Remove the value from that other cell. if (explain) { System.out.println( "row elimination due to " + $c.posAsString() + ": remove " + $i + " from " + $cx.posAsString() ); } modify( $cx ){ blockValue( $i ) } end
These rules are sufficient for many but not all Sudoku puzzles. To solve very difficult grids, the rule set requires more complex rules. (Ultimately, some puzzles can be solved only by trial and error.)