Constraint Processing

Wiki-Quelltext dieser Seite.

<language>Java</language>
== CP solver for the Sudoku game ==
=== Introduction ===
Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution.

[[Bild:Sudoku.png|200px]] --> [[Bild:Sudoku2.png|200px]]

=== Modeling Sudoku as Constraint Satisfaction Problem ===

'''Variables:''' $X_{11},...,X_{99}$

'''Domains:''' {1,..,9}

'''Constraints:''' 
* '''Row Constraints''' $X_{11} \neq X_{12},..,X_{11} \neq X_{19}$ etc. 
* '''Column Constraints''' $X_{11} \neq X_{21},..,X{11} \neq X_{91}$ etc.
* '''Block Constraints''' $X_{11} \neq X_{12},..,X_{11} \neq X_{33}$ etc.

We have 81 squares. Each square is part of 20 binary constraints of form $X_i \neq X_j$: 8 row constraints + 8 column constraints + 4 block constraints. So in total there are 81 * 20 / 2 = 810 constraints. 

=== Solving Sudoku with the basic Backtracking Solver ===
<code id="51b9ba2932671"></code>
<code id="51b9a50c38e1c"></code>
<run id="51b9b94e8299f"></run>