127.0.0.1: Created page with "'''Constraint Satisfaction Problems''' can be solved using ''Donald Knuth's'' Dancing Links algorithm. Another way to program Sudoku as a constraint satisfaction problem..."

2021-10-26T09:37:36Z

Created page with "'''Constraint Satisfaction Problems''' can be solved using ''Donald Knuth's'' Dancing Links algorithm. Another way to program Sudoku as a constraint satisfaction problem..."

New page

'''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 ==
[http://en.wikipedia.org/wiki/Constraint_satisfaction_problem Constraint Satisfaction Problem] entry on Wikipedia

Constraint satisfaction problem - Revision history

127.0.0.1: Created page with "'''Constraint Satisfaction Problems''' can be solved using ''Donald Knuth's'' Dancing Links algorithm. Another way to program Sudoku as a constraint satisfaction problem..."