# Solving Sudokus with MIP

A sudoku solver that uses a MIP to find solutions.

We have binary variables x[i, j, k] which, if = 1, say that cell (i, j) contains the number k. The constraints are: 1 - Each cell has one value only 2 - Each row contains each number exactly once 3 - Each column contains each number exactly once 4 - Each 3x3 subgrid contains each number exactly once We will take the initial grid as a CSV file at filepath, where 0s are blanks.

using JuMP
import GLPK
import Test

function example_sudoku(filepath::String)
initial_grid = zeros(Int, 9, 9)
open(filepath, "r") do fp
for row in 1:9
initial_grid[row, :] .= parse.(Int, split(line, ","))
end
end
model = Model(GLPK.Optimizer)
@variable(model, x[1:9, 1:9, 1:9], Bin)
@constraints(model, begin
# Constraint 1 - Only one value appears in each cell
cell[i in 1:9, j in 1:9], sum(x[i, j, :]) == 1
# Constraint 2 - Each value appears in each row once only
row[i in 1:9, k in 1:9], sum(x[i, :, k]) == 1
# Constraint 3 - Each value appears in each column once only
col[j in 1:9, k in 1:9], sum(x[:, j, k]) == 1
# Constraint 4 - Each value appears in each 3x3 subgrid once only
subgrid[i=1:3:7, j=1:3:7, val=1:9], sum(x[i:i + 2, j:j + 2, val]) == 1
end)
# Initial solution
for row in 1:9, col in 1:9
if initial_grid[row, col] != 0
fix(x[row, col, initial_grid[row, col]], 1)
end
end
# Solve it
optimize!(model)
# Check solution
term_status = termination_status(model)
is_optimal = term_status == MOI.OPTIMAL
if is_optimal
mip_solution = value.(x)
sol = zeros(Int, 9, 9)
for row in 1:9, col in 1:9, val in 1:9
if mip_solution[row, col, val] >= 0.9
sol[row, col] = val
end
end
return sol
else
error("The solver did not find an optimal solution.")
end
end
example_sudoku (generic function with 1 method)

Create an initial file. We could have set the example_sudoku function to take a matrix as input, but this example shows Julia's ability to parse files.

open("sudoku.csv", "w") do io
write(io, """
3, 1, 0, 0, 5, 8, 0, 0, 4
0, 0, 9, 3, 2, 0, 0, 0, 0
0, 2, 5, 1, 0, 4, 0, 9, 0
0, 0, 0, 0, 0, 0, 3, 8, 9
0, 0, 8, 0, 0, 0, 5, 0, 0
5, 4, 6, 0, 0, 0, 0, 0, 0
0, 8, 0, 2, 0, 3, 6, 5, 0
0, 0, 0, 0, 7, 1, 4, 0, 0
7, 0, 0, 4, 8, 0, 0, 2, 1
""")
end
234

Now try solving the example:

solution = example_sudoku("sudoku.csv")

Test.@test solution == [
3 1 7 9 5 8 2 6 4;
4 6 9 3 2 7 8 1 5;
8 2 5 1 6 4 7 9 3;
2 7 1 6 4 5 3 8 9;
9 3 8 7 1 2 5 4 6;
5 4 6 8 3 9 1 7 2;
1 8 4 2 9 3 6 5 7;
6 9 2 5 7 1 4 3 8;
7 5 3 4 8 6 9 2 1
]
Test Passed

The matrix can be hard to read. Print the solution properly:

function print_sudoku_solution(solution)
println("Solution:")
println("[-----------------------]")
for row in 1:9
print("[ ")
for col in 1:9
print(solution[row, col], " ")
if col % 3 == 0 && col < 9
print("| ")
end
end
println("]")
if row % 3 == 0
println("[-----------------------]")
end
end
end

print_sudoku_solution(solution)
Solution:
[-----------------------]
[ 3 1 7 | 9 5 8 | 2 6 4 ]
[ 4 6 9 | 3 2 7 | 8 1 5 ]
[ 8 2 5 | 1 6 4 | 7 9 3 ]
[-----------------------]
[ 2 7 1 | 6 4 5 | 3 8 9 ]
[ 9 3 8 | 7 1 2 | 5 4 6 ]
[ 5 4 6 | 8 3 9 | 1 7 2 ]
[-----------------------]
[ 1 8 4 | 2 9 3 | 6 5 7 ]
[ 6 9 2 | 5 7 1 | 4 3 8 ]
[ 7 5 3 | 4 8 6 | 9 2 1 ]
[-----------------------]

Clean up the file we made:

rm("sudoku.csv")