Sudoku

Sudoku puzzle consists of 81 squares (some of them are prefilled) and the objective is to fill all of them such that all rows, columns and boxes (groups of 3x3 squares) contain digits 1 to 9. Let \( x_{sd} \) be an indicator variable for the square \( s \) and the digit \(d \). $$\sum_{s \in u} x_{sd} = 1 \quad \forall u \ \forall d$$

Since the number of digits and the number of squares in a unit is the same we can define the following (redundent?) constraints. $$\sum_d x_{sd} = 1 \quad \forall s$$

When a digit is assigned to a square then we can set zero that digit in neigbor squares. $$x_{sd}=1 \Rightarrow x_{s'd}=0 \quad \forall s'\in N(s)$$

If we can find two digits elligible to only two squares of a unit then we can safely remove the other possible digits from these squares. (Hall's theorem? pigoenhole principle?) $$ \begin{align} \exists s_1, s_2 \in u, \ \exists d_1, d_2 \quad x_{s_1 d_1} + x_{s_1 d_2} + x_{s_2 d_1} + x_{s_2 d_2} = 2 \quad \\ \Rightarrow x_{s_1d} = 0, x_{s_2d}=0 \quad \forall d \notin (d_1, d_2) \end{align} $$

If possible squares in a box aligns to a row (resp. column) then we can remove that digit the rest of the row (resp. column). $$ x_{s_1d} + x_{s_2d} = 1 \Rightarrow x_{s'd} = 0 \quad \forall s' \in N(s_1, s_2) $$

If for a square, all the digits are eliminated except one then we can assign that digit to that square. $$ \exists d,s \quad x_{sd'}=0 \quad \forall d' \neq d \Rightarrow x_{sd} = 1$$

If in a unit there is only one elligible square remained for a digit then we can assign that digit to that square. $$\exists u,d,s \sum_{s'\in u, \ s' \neq s} x_{s'd} = 0 \Rightarrow x_{sd} = 1$$