**Description**: Shows how to solve Sudoku puzzles using integer programming and JuMP.

**Author**: Iain Dunning

**License**:

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

*A partially solved Sudoku puzzle*

Sudoku is a popular number puzzle. The goal is to place the digits 1,...,9 on a nine-by-nine grid, with some of the digits already filled in. Your solution must satisfy the following rules:

- The numbers 1 to 9 must appear in each 3x3 square
- The numbers 1 to 9 must appear in each row
- The numbers 1 to 9 must appear in each column

This isn't an optimization problem, its actually a *feasibility* problem: we wish to find a feasible solution that satsifies these rules. You can think of it as an optimization problem with an objective of 0.

We can model this problem using 0-1 integer programming: a problem where all the decision variables are binary. We'll use JuMP to create the model, and then we can solve it with any integer programming solver.

In [1]:

```
# Load JuMP
using JuMP
```

We will define a binary variable (a variable that is either 0 or 1) for each possible number in each possible cell. The meaning of each variable is as follows:

```
x[i,j,k] = 1 if and only if cell (i,j) has number k
```

where `i`

is the row and `j`

is the column.

In [2]:

```
# Create a model
sudoku = Model()
# Create our variables
@defVar(sudoku, x[i=1:9, j=1:9, k=1:9], Bin)
```

Out[2]:

In [3]:

```
for i = 1:9, j = 1:9 # Each row and each column
# Sum across all the possible digits
# One and only one of the digits can be in this cell,
# so the sum must be equal to one
@addConstraint(sudoku, sum{x[i,j,k],k=1:9} == 1)
end
```

In [4]:

```
for ind = 1:9 # Each row, OR each column
for k = 1:9 # Each digit
# Sum across columns (j) - row constraint
@addConstraint(sudoku, sum{x[ind,j,k],j=1:9} == 1)
# Sum across rows (i) - column constraint
@addConstraint(sudoku, sum{x[i,ind,k],i=1:9} == 1)
end
end
```

`for`

loops, then sum over the squares.

In [7]:

```
for i = 1:3:7, j = 1:3:7, k = 1:9
# i is the top left row, j is the top left column
# We'll sum from i to i+2, e.g. i=4, r=4, 5, 6
@addConstraint(sudoku, sum{x[r,c,k], r=i:i+2, c=j:j+2} == 1)
end
```

`0`

if there is no digit in that location.

In [8]:

```
# The given digits
init_sol = [ 5 3 0 0 7 0 0 0 0;
6 0 0 1 9 5 0 0 0;
0 9 8 0 0 0 0 6 0;
8 0 0 0 6 0 0 0 3;
4 0 0 8 0 3 0 0 1;
7 0 0 0 2 0 0 0 6;
0 6 0 0 0 0 2 8 0;
0 0 0 4 1 9 0 0 5;
0 0 0 0 8 0 0 7 9]
for i = 1:9, j = 1:9
# If the space isn't empty
if init_sol[i,j] != 0
# Then the corresponding variable for that digit
# and location must be 1
@addConstraint(sudoku, x[i,j,init_sol[i,j]] == 1)
end
end
```

In [9]:

```
# We are now ready to solve the problem
# For this to work, you must have an integer programming
# solver installed. If you don't, you can install one with
# Pkg.add("GLPKMathProgInterface")
# or
# Pkg.add("Cbc")
solve(sudoku)
```

Out[9]:

To display the solution, we need to look for the values of `x[i,j,k]`

that are 1.

In [10]:

```
# Extract the values of x
x_val = getValue(x)
# Create a matrix to store the solution
sol = zeros(Int,9,9) # 9x9 matrix of integers
for i in 1:9, j in 1:9, k in 1:9
# Integer programs are solved as a series of linear programs
# so the values might not be precisely 0 and 1. We can just
# round them to the nearest integer to make it easier
if iround(x_val[i,j,k]) == 1
sol[i,j] = k
end
end
# Display the solution
println(sol)
```

Which is the correct solution:

*A completed Sudoku puzzle*