---

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

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 then becomes

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

The other three constraints can also be set up as linear sums.

Reference

Constraint Satisfaction Problem entry on Wikipedia

This page was last modified 01:14, 15 April 2009.  

---