Difference between revisions of "Constraint satisfaction problem"

Latest revision as of 19:30, 22 July 2025

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.

The cell‑constraint is then:

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

@@ Line 1: / Line 1: @@
-'''Constraint Satisfaction Problems''' can be solved using Donald Knuth’s [[Dancing Links]] algorithm.
+'''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]].
+Another way to model 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>
+; <code>x(i,j,k) = 0</code>
-: if [[Cell|cell]] <math>(i,j)</math> in the [[Grid|grid]] is **not** equal to <math>k</math>
+: if [[Cell|cell]] <code>(i, j)</code> in the [[Grid|grid]] is **not** equal to <code>k</code>
-; <math>x(i,j,k)=1</math>
+; <code>x(i,j,k) = 1</code>
-: if [[Cell|cell]] <math>(i,j)</math> in the grid **is** equal to <math>k</math>
+: if cell <code>(i, j)</code> in the grid **is** equal to <code>k</code>
-The cell [[Constraint|constraint]] then becomes:
+The cell‑[[Constraint|constraint]] is then:
 ; Cell constraint
-: <math>\sum_{k} x(i,j,k)=1 \quad \forall\, i,j</math>
+: ‘‘Sum over <code>k</code> of <code>x(i,j,k)</code> = 1 for all <code>i</code> and <code>j</code>.’’
-The other three constraints (row, column and block) can be expressed in a similar way as linear sums.
+The remaining three constraints (row, column and block) can be expressed in the same way—as simple linear sums.