Sudoku

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";
      };
   };
};

Optimization Category (Linear Programing, Integer, MIP and etc.):