Sudoku

The first question on my first optimization exam was to formulate a mathematical model for solving a Sudoku puzzle. Well, at that moment I made a huge mistake: I included nonlinear constraints, which resulted in a score of 0. And since this was one of my favorite subjects, I’ve always remembered that bad experience.

That’s why I’m here today to correct that past mistake.

A Sudoku is a puzzle game with very simple rules, but honestly, I find it difficult to solve. It consists of a 9×9 grid where some cells contain numbers while others are empty. The puzzle involves filling in each row and each column with the numbers 1 through 9 without repeating them.

The above condition must also be met for each of the 3×3 squares in the following image, where you can see the puzzle and its solution on the right:

Well, mathematically this can be formulated as follows, and I’ll show how to program the same thing in Python using PuLP. At the end, I’ll put all the code in a GIT repository

Initialize the mathematical problem
prob = pulp.LpProblem(“prob”, pulp.LpMaximize)

Indices:

Row f \in 1..9
row = [x for x in range(9)]
Column c \in 1..9
col = [x for x in range(9)]
Value v \in 1..9
val = [x for x in range(9)]

Decision variables

G_{f,c,v} \in [0,1] where 1 means that the value v is assigned to row f, column c.

game = [[[pulp.LpVariable(cat =‘Binary’, name =‘row {}, col {} is {}’.format(f, c, v+1)) for f in row] for c in colum] for v in val]

Parameters

P_{f,c,v} \in [0,1] where 1 means that the value v must be assigned to row f, column c.

wb = load_workbook(“sudoku.xlsx”, data_only=True)
sh = wb.worksheets[0]
puzzle = [[[0 for k in range(9)] for j in range(9)] for i in range(9)]
for f,c,v in product(range(9),range(9),range(9)):
    if sh.cell(f+1,c+1).value == v+1:
        puzzle[f][v] = 1

Objective Function

max \sum_{f,c,v} G_{f,c,v} Maximize the sum of assigned values

prob += pulp.lpSum(game)

Constraints:

The puzzle must be satisfied

\forall f,c,v G_{f,c,v} \ge P_{f,c,v}

for f,c,v in product(row,col,val):
    prob += game[f][v] >= puzzle[f][v]

Each cell can only contain one value

\forall f,c \sum_v G_{f,c,v} \le 1

for f,c in product(row,col):
    prob += pulp.lpSum([game[f][v] for v in val]) <= 1

Each row can contain each value only once

\forall f,v \sum_c G_{f,c,v} \le 1

for f,v in product(row,val):
    prob += pulp.lpSum([game[f][v] for c in colum]) <= 1

Each column can contain each value only once

\forall c,v \sum_f G_{f,c,v} \le 1

for c,v in product(row,val):
    prob += pulp.lpSum([game[f][v] for f in row]) <= 1

Each quadrilateral must have each value exactly once

cc = index of the quadrilateral in the column
cf = index of the quadrilateral in the row
f = row of the quadrilateral
c = column of the quadrilateral
`$$ \forall cf,cc,v \in [1,2,3],[1,2,3],val \sum{f\in[1,2,3],c\in[1,2,3],v} G{f+3cf,f+3cc,v} \le 1 $$

for cf,cc,v in product(range(3),range(3),val):
    prob += pulp.lpSum([game[f+3*cf][v] for f,c in product(range(3),range(3))]) <= 1

Solve the problem and obtain results

solver = pulp.getSolver(‘PULP_CBC_CMD’)
prob.solve(solver)

sol = [[0 for k in range(9)] for j in range(9)]
for f,c,v in product(row,colum,val):
    if(pulp.value(game[f][v]) > 0.9):
        sol[f] = v + 1

for f in row:
    print(sol[f])

[6, 4, 3, 5, 1, 7, 9, 2, 8]
[8, 1, 5, 3, 2, 9, 7, 4, 6]
[2, 9, 7, 8, 6, 4, 3, 1, 5]
[9, 2, 8, 1, 7, 5, 6, 3, 4]
[4, 7, 1, 6, 3, 2, 5, 8, 9]
[5, 3, 6, 9, 4, 8, 1, 7, 2]
[7, 5, 9, 4, 8, 3, 2, 6, 1]
[3, 6, 4, 2, 5, 1, 8, 9, 7]
[1, 8, 2, 7, 9, 6, 4, 5, 3]

Which is the same as the example:

You can find the complete code on my GitHub:
https://github.com/danielfm123/sudoku_solver

Best regards!

Translated with DeepL.com (free version)