|
At the Problem view on the left a user may freely enter values in the white
cells - the initial implementation does not validate user's actions. A
click on "Solution" creates and solves a constraint satisfaction
problem and display the results at the Solution view on the right.
The entire implementation has be done inside a single Excel
file - see Sudoku.xls.
SUDOKU Constraints
Implementation This game is
implemented using OpenRules Rule Solver that utilizes the power of the
constraint solver "Choco".
When a user clicks on "Solution", the method "createSudokuProblem"
is called to create a constraint satisfaction problem:
| Method void createSudokuProblem(RuleSolver s) |
CpProblem p = s.newProblem();
// Create 9X9 Square of constrained variables with values from 1 to
9
CpVariable[] vars = p.addSquare(1, 9, 9, "x");
postDataConstraints(p);
postSudokuConstraints(p); |
It describes the entire problem as 9x9
two-dimensional array "x" of constrained variables with possible values from
1 to 9. Then it posts the problem data described at the worksheet
"Data" of the file Sudoku.xls:
| Data SudokuData data |
| x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
| 0 |
6 |
9 |
0 |
0 |
7 |
0 |
0 |
5 |
| 0 |
5 |
0 |
0 |
0 |
4 |
0 |
2 |
0 |
| 4 |
0 |
0 |
0 |
5 |
0 |
1 |
0 |
0 |
| 8 |
0 |
5 |
0 |
0 |
0 |
6 |
0 |
0 |
| 6 |
7 |
0 |
2 |
9 |
5 |
0 |
1 |
4 |
| 0 |
0 |
1 |
0 |
0 |
0 |
7 |
0 |
9 |
| 0 |
0 |
6 |
0 |
1 |
0 |
0 |
0 |
7 |
| 0 |
1 |
0 |
4 |
0 |
0 |
0 |
8 |
0 |
| 5 |
0 |
0 |
3 |
0 |
0 |
2 |
6 |
0 |
And finally it posts row, column, and block
constraints using a single table "postSudokuConstraints" from the worksheet
"Sudoku Constraints" of the file
Sudoku.xls:
This is a Rules table without conditions. As a result, every
rule (row) will be executed by creating an array of variables described in
this row and posting constraint "affDiff" for this array using
p.allDiff(array).post(); The constraint
"allDiff" is the most popular global constraint available in any constraint
solver. Thus, the implementation of Sudoku constraints became a simple
Excel's copy-paste operation to properly define Sudoku's rows, columns, and
blocks. To solve the problem we rely on the standard solving method for the
constraint satisfaction problem:
|
Method boolean solveSudokuProblem(CpProblem p) |
CpVariable[] x = p.getArray("x");
return p.solve(x); |
It would be simple to validate user's
actions just posting them as new constraints and using the same method to
make sure that a solution can be found.
The web interface implementation is self-explanatory - see
OpenRules Forms presented in the worksheets "Problem Layout" and "Solution
Layout" of the same file Sudoku.xls.
Back to Fun Lab
|
