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 \;\; \text{if and only if cell (i,j) has number k} $$ where i is the row and j is the column.
using JuMP
#using Clp
using Cbc
#using Gurobi
# Create a model
#sudoku = Model(solver=ClpSolver())
# 0 - dual simplex
# 1 - primal simplex
# 3 - barrier with crossover to optimal basis
# 4 - barrier without crossover to optimal basis
# 5 - automatic
sudoku = Model(solver=CbcSolver())
#sudoku = Model(solver=GurobiSolver(Method=1)) # Method=1 (Simplex), Method=2 (Barrier)
m = 9
# Create our variables
#@variable(sudoku, x[i=1:m, j=1:m, k=1:m], Bin)
@variable(sudoku, 0 <= x[i=1:m, j=1:m, k=1:m] <= 1)
# no objective
@constraints(sudoku, begin
cell[i=1:m, j=1:m], sum{x[i,j,k], k=1:m} == 1
end)
@constraints(sudoku, begin
row[i=1:m, k=1:m], sum{x[i,j,k], j=1:m} == 1
col[j=1:m, k=1:m], sum{x[i,j,k], i=1:m} == 1
end)
@constraints(sudoku, begin
blk[i=1:3:(m-2), j=1:3:(m-2), k=1:m], sum{x[r,c,k], r=i:(i+2), c=j:(j+2)} == 1
end)
# 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
@constraint(sudoku, x[i,j,init_sol[i,j]] == 1)
end
end
solve(sudoku)
:Optimal
# Extract the values of x
x_val = getvalue(x)
x_val_round = round(Integer, x_val)
@show all(x_val .== x_val_round)
# 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
# There are many ways to solve integer programs, and in this case the solution may not be exactly binary values.
if round(Integer, x_val[i,j,k]) == 1
sol[i,j] = k
end
end
# Display the solution
sol
all(x_val .== x_val_round) = true
9×9 Array{Int64,2}: 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9