Constraint Processing

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.

-->

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