# Sudoku¶

We solve a following Sudoku puzzle using flopt.

0 1 2   3 4 5   6 7 8
+-------+-------+-------+
0  |       |       |   1   |
1  | 4     |       |       |
2  |   2   |       |       |
+-------+-------+-------+
3  |       |   5   | 4   7 |
4  |     8 |       | 3     |
5  |     1 |   9   |       |
+-------+-------+-------+
6  | 3     | 4     | 2     |
7  |   5   | 1     |       |
8  |       | 8   6 |       |
+-------+-------+-------+

We represent this problem’s hints as following list. For example, (1, 0, 7) hint represents 1 is in the cell where row is 0 and column is 7.

# problem format
hints = [
# (value, row, column)
(1, 0, 7), (4, 1, 0), (2, 2, 1), (5, 3, 4), (4, 3, 6),
(7, 3, 8), (8, 4, 2), (3, 4, 6), (1, 5, 2), (9, 5, 4),
(3, 6, 0), (4, 6, 3), (2, 6, 6), (5, 7, 1), (1, 7, 3),
(8, 8, 3), (6, 8, 5),
]

In addition, we create lists for modeling.

# A list of number sequence
Sequence = list(range(9))
Vals = Sequence
Rows = Sequence
Cols = Sequence

We create Binary variables $$x_{ijk}$$ such that $$x_{ijk} = 1$$ if $$j$$-row and $$k$$-column cell’s value is $$i$$ else $$x_{ijk} = 0$$.

from flopt import Variable

# The problem variables
x = Variable.array("x", (9, 9, 9), cat="Binary", ini_value=0)

Following given hints, we replace some variables with number 1.

# The starting numbers are entered as constant
for value, row, col in hints:
x[value-1, row, col] = 1

Then, we create Problem.

from flopt import Problem, Sum

prob = Problem("Sudoku")

# A constraint ensuring that only one value can be in each piece
for r in Rows:
for c in Cols:
prob += Sum(x[:, r, c]) == 1  # is equal to Sum(x[i, r, c] for i in Vals) == 1

# The row, column and box constraints are added for each value
for v in Vals:
for r in Rows:
prob += Sum(x[v, r, :]) == 1

for c in Cols:
prob += Sum(x[v, :, c]) == 1

for r in [0, 3, 6]:
for c in [0, 3, 6]:
prob += Sum(x[v, r:r+3, c:c+3]) == 1

We solve this problem using AutoSolver.

prob.solve(solver="auto", msg=True)
>>> Welcome to the flopt Solver
>>> Version 0.5.4
>>> Date: September 1, 2022
>>>
>>> Algorithm: ScipyMilpSearch
>>> Params: {'timelimit': inf}
>>> Number of variables 712 (continuous 0 , int 0, binary 712, permutation 0 (0))
>>>
>>>
>>>      Trial Incumbent    BestBd  Gap[%] Time[s]
>>> ----------------------------------------------
>>> S        0       inf         -       -    0.00
>>> *        0   0.00000         -       -    0.04
>>>
>>> Status: normal termination
>>> Objective Value: 0
>>> Time: 0.035471200942993164
>>> Running HiGHS 1.2.2 [date: 2022-08-26, git hash: n/a]
>>> Copyright (c) 2022 ERGO-Code under MIT licence terms
>>> Presolving model
>>> 477 rows, 290 cols, 2280 nonzeros
>>> 0 rows, 0 cols, 0 nonzeros
>>> Presolve: Optimal
>>>
>>> Solving report
>>>   Status            Optimal
>>>   Primal bound      0
>>>   Dual bound        0
>>>   Gap               0% (tolerance: 0.01%)
>>>   Solution status   feasible
>>>                     0 (objective)
>>>                     0 (bound viol.)
>>>                     0 (int. viol.)
>>>                     0 (row viol.)
>>>   Timing            0.00 (total)
>>>                     0.00 (presolve)
>>>                     0.00 (postsolve)
>>>   Nodes             0
>>>   LP iterations     0 (total)
>>>                     0 (strong br.)
>>>                     0 (separation)
>>>                     0 (heuristics)

The result is as follows.

from flopt import Value

# display result
row_line = "+-------+-------+-------+"
print(row_line)
for r in Rows:
if r in {3, 6}:
print(row_line)
for c in Cols:
if c in {0, 3, 6}:
print("| ", end="")
for v in Vals:
if Value(x[v, r, c]) == 1:
print(f"{v+1} ", end="")
if c == 8:
print("|")
print(row_line)
+-------+-------+-------+
| 6 9 3 | 7 8 4 | 5 1 2 |
| 4 8 7 | 5 1 2 | 9 3 6 |
| 1 2 5 | 9 6 3 | 8 7 4 |
+-------+-------+-------+
| 9 3 2 | 6 5 1 | 4 8 7 |
| 5 6 8 | 2 4 7 | 3 9 1 |
| 7 4 1 | 3 9 8 | 6 2 5 |
+-------+-------+-------+
| 3 1 9 | 4 7 5 | 2 6 8 |
| 8 5 6 | 1 2 9 | 7 4 3 |
| 2 7 4 | 8 3 6 | 1 5 9 |
+-------+-------+-------+