Summary: The objective of sudoku is to fill a \(9 \times 9\) grid so that each column, each row, and each of the nine \(3 \times 3\) boxes contains all of the digits from 1 to 9 exactly once.
Solve the Puzzle
To play, select a difficulty level and enter values in the empty squares. To check a hand-entered solution, including an incomplete one, click “Check My Solution”. To view the entire solution, click “Solve Sudoku”. For the best results, we recommend using Firefox for this interactive case study.
| Difficulty |
|---|
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";
};
};
};