**Summary**: The objective of sudoku is to fill a 9 x 9 grid so that each column, each row, and each of the nine 3 x 3 boxes contains all of the digits from 1 to 9 exactly once.

### Case Study Contents

## Solve the Puzzle

Click here to go to the new Sudoku puzzle.

## Mathematical Formulation

Sudoku can be formulated as a mixed integer linear programming (MILP) problem and solved using one of the MILP solvers on the NEOS Server. If you submit the puzzle to be solved by the NEOS Server, the applet will create an AMPL model of the instance, submit the model to the NEOS Server, and retrieve the results. Then, you can click the 'Reveal Solution' button to display the solution.

### The Mathematical Model

The objective of sudoku is to fill a 9 x 9 grid so that each column, each row, and each of the nine 3 x 3 boxes contains all of the digits from 1 to 9. Let \(n\) be the dimension of the boxes that make up the grid; \(n = 3\) in a standard 9 x 9 sudoku puzzle.

**Parameters**

\(n\) = dimension of the puzzle (\(n = 9\))

\(m\) = dimension of the boxes that make up the grid (\(m = 3\))

\(P\{N,N\}\) = prespecified digits, i.e., \(P[i,j] = k\) means that digit \(k\) should be the number in cell \((i,j)\)

**Set**

\(N\) = set of digits from 1 to \(n\)

**Variables**

\[ z[i, j, k] = \left\{ \begin{array}{ll}

1 & \mbox{if \(k\) is the entry in row \(i\) and column \(j\)} \\

0 & \mbox{otherwise}

\end{array} \right.

\]

**Objective Function**: minimize 0

The objective of the puzzle is to find a solution that satisfies the constraints; there is no objective function to be minimized or maximized. Typically, the prespecified values are set in such a way that there is a unique solution to the puzzle.

**Constraints**

Column constraints: only one of each digit in each column

\( \sum_{i \in N} z[i,j,k] = 1, \forall j \in N, k \in N\)

Row constraints: only one of each digit in each row

\( \sum_{j \in N} z[i,j,k] = 1, \forall i \in N, k \in N\)

Box constraints: only one of each digit in each box

\(\sum_{p=1}^m \sum_{q=1}^m z[mr + p, mc + q, k] = 1, \forall r \in 0..m-1, c \in 0..m-1, k \in N\)

Uniqueness constraints: only one digit in each cell

\(\sum_{k \in N} z[i,j,k] = 1, \forall i \in N, j \in N\)

Prespecified values constraints: fix location of prespecified values

\(z[i,j,P[i,j]] = 1, \forall i \in N, j \in N, P[i,j] < > 0\)

## AMPL model

param m >= 1, integer, default 3; param n := m*m; set N := 1..n; # prespecified data values param P{N,N} default 0, integer, >= 0, <= n; # z[i,j,k] = 1 if digit k is in row i and column j var z{N,N,N} binary; # dummy objective minimize obj: 0; # only one of each digit in each column subject to col_sum{j in N, k in N}: sum{i in N} z[i,j,k] = 1; # only one of each digit in each row subject to row_sum{i in N, k in N}: sum{j in N} z[i,j,k] = 1; # only one of each digit in each box subject to sqr_sum{r in 0..m-1, c in 0..m-1, k in N}: sum{p in 1..m, q in 1..m} z[m*r+p,m*c+q,k] = 1; # only one digit in each cell subject to unique{i in N, j in N}: sum{k in N} z[i,j,k] = 1; # fix position of prespecified values subject to fixed{i in N, j in N: P[i,j] <> 0}: z[i,j,P[i,j]] = 1; data; param m:= 3; param P: 1 2 3 4 5 6 7 8 9 := 1 1 . . . . 6 3 . 8 2 . . 2 3 . . . 9 . 3 . . . . . . 7 1 6 4 7 . 8 9 4 . . . 2 5 . . 4 . . . 9 . . 6 9 . . . 2 5 1 . 4 7 6 2 9 . . . . . . 8 . 4 . . . 7 6 . . 9 5 . 7 6 . . . . 3 ; solve; #display the results for {i in N}{ for {j in N}{ for {k in N}{ if (z[i,j,k] == 1) then printf "%3i", k; }; if ((j mod m) == 0) then printf " | "; }; printf "\n"; if ((i mod m) == 0) then { for {j in 1..m}{ for {k in 1..m-1}{ printf "---" }; if (j < m) then printf "----+-"; else printf "----+\n"; }; }; };