Constraint satisfaction problem

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

Another way to model Sudoku as a constraint‑satisfaction problem is to treat it as a Binary Integer Linear Program.

x(i,j,k) = 0

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

x(i,j,k) = 1

if cell (i, j) in the grid **is** equal to k

The cell‑constraint is then:

Cell constraint

‘‘Sum over k of x(i,j,k) = 1 for all i and j.’’

The remaining three constraints (row, column and block) can be expressed in the same way—as simple linear sums.