Constraint satisfaction problem

Constraint Satisfaction Problems can be solved using Donald Knuth’s Dancing Links algorithm.

Another way to program Sudoku as a constraint satisfaction problem is to treat it as a Binary Integer Linear Program. In that case define:

<math>x(i,j,k)=0</math>

if cell <math>(i,j)</math> in the grid is **not** equal to <math>k</math>

<math>x(i,j,k)=1</math>

if cell <math>(i,j)</math> in the grid **is** equal to <math>k</math>

The cell constraint then becomes:

Cell constraint

<math>\sum_{k} x(i,j,k)=1 \quad \forall\, i,j</math>

The other three constraints (row, column and block) can be expressed in a similar way as linear sums.