Mirrored from **Sudopedia**, the Free Sudoku Reference Guide

# 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.