Red Hat Training

A Red Hat training course is available for JBoss Enterprise SOA Platform

Chapter 28. Sudoku Example

28.1. Sudoku Example: Loading the Example

Procedure 28.1. Task

  1. Open sudoku.drl in the IDE.
  2. Execute java org.drools.examples.DroolsExamplesApp and click on SudokuExample. The window contains an empty grid, but the program comes with a number of grids stored internally which can be loaded and solved.
  3. Click on File → Samples → Simple to load one of the examples. All buttons are disabled until a grid is loaded. Loading the Simple example fills the grid according to the puzzle's initial state.
  4. Click on the Solve button and the JBoss Rules engine will fill out the remaining values. The buttons will be inactive again.
  5. Alternatively, click on the Step button to see the next digit found by the rule set. The Console window will display detailed information about the rules which are executing to solve the step in a readable format like the example below: 
    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]
  6. Click on the Dump button to see the state of the grid. The cells show either the established value or the remaining possible candidates. See the example below: 
    Col: 0     Col: 1     Col: 2     Col: 3     Col: 4     Col: 5     Col: 6     Col: 7     Col: 8     
Row 0:   2 4  7 9   2 456        4567 9   23 56  9  --- 5 ---  --- 1 ---    3  67 9  --- 8 ---     4 67   
Row 1:  12    7 9  --- 8 ---  1    67 9   23  6  9  --- 4 ---   23  67    1 3  67 9    3  67 9  --- 5 --- 
Row 2:  1  4  7 9  1  456     --- 3 ---      56 89      5 78       5678   --- 2 ---     4 67 9  1  4 67   
Row 3:  1234       12345      1  45      12  5  8   --- 6 ---   2  5 78       5 78      45 7    --- 9 --- 
Row 4:  --- 6 ---  --- 7 ---      5      --- 4 ---   2  5  8   --- 9 ---      5  8   --- 1 ---  --- 3 --- 
Row 5:  --- 8 ---  12 45      1  45   9  12  5      --- 3 ---   2  5 7        567       4567     2 4 67   
Row 6:  1 3   7    1 3  6     --- 2 ---    3 56 8       5  8     3 56 8   --- 4 ---    3 567 9  1    678  
Row 7:  --- 5 ---  1 34 6     1  4 678     3  6 8   --- 9 ---    34 6 8   1 3  678   --- 2 ---  1    678  
Row 8:    34       --- 9 ---     4 6 8   --- 7 ---  --- 1 ---   23456 8     3 56 8     3 56          6 8

28.2. Sudoku Example: Debugging a Broken Example

Procedure 28.2. Task

  1. Open sudoku.drl in your IDE.
  2. Click on File → Samples → !DELIBERATLEY BROKEN!. The JBoss Rules engine will inspect the grid and produce the following output: 
    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.
  3. Click on the Solve button to apply the solving rules to this invalid grid. These rules use the values of the cells for problem solving. The rules detecting these situations insert a Setting fact including the solution value for the specified cell. This fact removes the incorrect value from all cells in the group.

28.3. Sudoku Example: Java Source and Rules

  • The Java source code can be found in the /src/main/java/org/drools/examples/sudoku directory, with the two DRL files defining the rules located in the /src/main/rules/org/drools/examples/sudoku directory.
  • The package org.drools.examples.sudoku.swing contains a set of classes which implement a framework for Sudoku puzzles. This package does not have any dependencies on the JBoss Rules libraries.
  • SudokuGridModel defines an interface which can be implemented to store a Sudoku puzzle as a 9x9 grid of Cell objects.
  • SudokuGridView is a Swing component which can visualize any implementation of SudokuGridModel.
  • SudokuGridEvent and SudokuGridListener are used to communicate state changes between the model and the view. Events are fired when a cell's value is resolved or changed.
  • SudokuGridSamples provides a number of partially filled Sudoku puzzles for demonstration purposes.
  • The package org.drools.examples.sudoku.rules contains a utility class with a method for compiling DRL files.
  • The package org.drools.examples.sudoku contains a set of classes implementing the elementary Cell object and its various aggregations. It contains the CellFile subtypes CellRow, CellCol and CellSqr, all of which are subtypes of CellGroup.

28.4. Sudoku Example: Cell Objects

  • Cell and CellGroup are subclasses of SetOfNine, which provides a property free with the type Set<Integer>. For a Cell it represents the individual candidate set. For a CellGroup the set is the union of all candidate sets of its cells, or the set of digits that still need to be allocated.
  • 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. For example, you can create a list of Cell objects with 81 Cell and 27 CellGroup objects. You can also combine the linkage provided by the Cell properties cellRow, cellCol, cellSqr and the CellGroup property cells.

28.5. Sudoku Example: Classes and Objects

  • An object belonging to the Setting class is used for triggering the operations that accompany the allocation of a value. The presence of a Setting fact is used in all rules that should detect changes in the process. This is to avoid reactions to inconsistent intermediary states.
  • An object of class Stepping is used in a low priority rule to execute an emergency halt when a "Step" ends unexpectedly. This indicates that the puzzle cannot be solved by the program.
  • The class org.drools.examples.sudoku.SudokuExample implements a Java application combining the above components.

28.6. Sudoku Example: Validate.drl

  • Sudoku Validator Rules (validate.drl) detect duplicate numbers in cell groups. They are combined in an agenda group which enables them to be activated after loading a puzzle.
  • The three rules duplicate in cell... are very similar. The first pattern locates a cell with an allocated value. The second pattern pulls in any of the three cell groups the cell belongs to. The final pattern finds a cell with the same value as the first cell and in the same row, column or square, respectively.
  • Rule terminate group fires last. It prints a message and calls halt.

28.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.)