Sudoku
Sudoku is a puzzle played on a $9\times 9$ grid in which each cell must be filled with a digit from 1 to 9, subject to the following conditions:
- Each row contains the digits 1 through 9 exactly once.
- Each column contains the digits 1 through 9 exactly once.
- Each of the nine $3\times 3$ blocks contains the digits 1 through 9 exactly once.
The puzzle is presented with a partial assignment (the clues); the goal is to fill in the remaining empty cells while satisfying the constraints above.
The programs in the video, chapter by chapter, are on the page Video: Sudoku.
Formulation with one-hot encoding
We use a 3-dimensional array of binary variables $X=(x_{i,j,k})$ ($0\leq i, j, k \leq 8$), with the one-hot encoding that $x_{i,j,k}=1$ iff cell $(i, j)$ contains digit $k+1$. Because each cell holds exactly one digit, exactly one of the nine $x_{i,j,k}$ values along axis $k$ is 1.
We impose the following constraints:
- Each cell holds exactly one digit:
- Each row contains each digit exactly once:
- Each column contains each digit exactly once:
- Each $3\times 3$ block contains each digit exactly once:
These equalities are declared as constraints with qbpp.cons() to define the expression $f$. The energy of a constraint is the square of its violation, and any assignment with $f=0$ corresponds to a valid Sudoku solution.
Fixing variables from clues
Rather than encoding clues as additional penalties, we fix the affected variables directly to 0 or 1. When the clue tells us that cell $(i, j)$ contains digit $v$, the following variables are forced:
\[\begin{aligned} x_{i,j,v-1} &= 1 && \text{(cell $(i, j)$ IS digit $v$)}\\ x_{i,j,k} &= 0 && \text{($k \ne v-1$, cell $(i, j)$ is not any other digit)}\\ x_{i,j',v-1} &= 0 && \text{($j' \ne j$, no other cell in the same row holds $v$)}\\ x_{i',j,v-1} &= 0 && \text{($i' \ne i$, same for the column)}\\ x_{i',j',v-1} &= 0 && \text{($(i', j')$ in the same $3\times 3$ block, same for the block)} \end{aligned}\]Collecting these forced values into a dictionary {Var: 0 or 1} and passing it to qbpp.replace removes the corresponding variables from the expression, drastically reducing the number of variables the solver needs to handle.
PyQBPP program
The following PyQBPP program builds the expression with the declared constraints, fixes the clue-related variables, and then solves the puzzle with EasySolver:
import pyqbpp as qbpp
# 0 represents an empty cell. The example puzzle (Grid 01) of Project Euler Problem 96.
PUZZLE = [
[0, 0, 3, 0, 2, 0, 6, 0, 0],
[9, 0, 0, 3, 0, 5, 0, 0, 1],
[0, 0, 1, 8, 0, 6, 4, 0, 0],
[0, 0, 8, 1, 0, 2, 9, 0, 0],
[7, 0, 0, 0, 0, 0, 0, 0, 8],
[0, 0, 6, 7, 0, 8, 2, 0, 0],
[0, 0, 2, 6, 0, 9, 5, 0, 0],
[8, 0, 0, 2, 0, 3, 0, 0, 9],
[0, 0, 5, 0, 1, 0, 3, 0, 0],
]
def sudoku_expr(x):
# Each cell holds exactly one digit.
f = qbpp.cons(qbpp.vector_sum(x, axis=2) == 1)
# Each row has each digit exactly once.
f += qbpp.cons(qbpp.vector_sum(x, axis=1) == 1)
# Each column has each digit exactly once.
f += qbpp.cons(qbpp.vector_sum(x, axis=0) == 1)
# Each 3x3 box has each digit exactly once.
for br in range(3):
for bc in range(3):
for k in range(9):
f += qbpp.cons(qbpp.sum(x[3*br:3*br+3, 3*bc:3*bc+3, k]) == 1)
return f
def fix_variables(x, puzzle):
sub = {}
for i in range(9):
for j in range(9):
v = puzzle[i][j]
if v == 0:
continue
k_clue = v - 1
for k in range(9):
sub[x[i, j, k]] = 1 if k == k_clue else 0
for jj in range(9):
if jj != j:
sub.setdefault(x[i, jj, k_clue], 0)
for ii in range(9):
if ii != i:
sub.setdefault(x[ii, j, k_clue], 0)
br, bc = i // 3, j // 3
for ii in range(3 * br, 3 * br + 3):
for jj in range(3 * bc, 3 * bc + 3):
if (ii, jj) != (i, j):
sub.setdefault(x[ii, jj, k_clue], 0)
return sub
def print_sudoku(solution):
for i in range(9):
if i % 3 == 0 and i > 0:
print("------+-------+------")
row = []
for j in range(9):
v = solution[i][j]
row.append(str(v + 1) if v >= 0 else ".")
if j % 3 == 2 and j < 8:
row.append("|")
print(" ".join(row))
x = qbpp.var("x", 9, 9, 9)
f = sudoku_expr(x)
sub = fix_variables(x, PUZZLE)
initial_sol = qbpp.Sol(f).set(sub)
print("Puzzle:")
print_sudoku(qbpp.onehot_to_int(initial_sol(x)))
g = qbpp.replace(f, sub)
g.simplify_as_binary()
solver = qbpp.EasySolver(g)
sol = solver.search(target_energy=0)
full_sol = qbpp.Sol(f).set(sol, sub)
print("\nSolution:")
print_sudoku(qbpp.onehot_to_int(full_sol(x)))
qbpp.var("x", 9, 9, 9) creates a 3-dimensional array x of binary variables with shape $(9, 9, 9)$.
The function sudoku_expr declares the four families of equality constraints. The cell, row and column constraints use qbpp.vector_sum(x, axis=...), which sums an array along one axis. The summed axis disappears, so each result is a $9\times 9$ array of 81 sums:
qbpp.vector_sum(x, axis=2)sums along axis $k$; element $(i, j)$ is the sum of the 9 variables of cell $(i, j)$.qbpp.vector_sum(x, axis=1)sums along axis $j$; element $(i, k)$ is the sum of the 9 variables for digit $k+1$ in row $i$.qbpp.vector_sum(x, axis=0)sums along axis $i$; element $(j, k)$ is the sum of the 9 variables for digit $k+1$ in column $j$.
Applying == 1 to an array gives 81 element-wise equalities, and enclosing them in qbpp.cons() declares all 81 constraints at once. For the block constraints, the slice x[3*br:3*br+3, 3*bc:3*bc+3, k] extracts the 2D array of the 9 variables for digit $k+1$ in a $3\times 3$ block; its qbpp.sum is compared with == 1 and enclosed in qbpp.cons(). For an expression with declared constraints, the search stops when the energy is at most target_energy and all constraints are satisfied.
The function fix_variables collects all forced values (1 for the clue digit, 0 for everything that conflicts with it) into a dictionary sub. Because Python’s dict naturally handles repeated writes to the same key, the clue cell entries use plain sub[...] = ... (overwrite) and the neighbor entries use sub.setdefault(...) (write only if the key is new). In a valid puzzle (no two clues with the same digit in a row, column or block), all writes to the same variable have the same value, so it does not matter which one is kept: no neighbor rule of another clue writes “= 0” to the “= 1” variable of a clue.
qbpp.replace(f, sub) produces a new expression g in which every variable listed in sub has been substituted by its constant value (0 or 1). The forced variables therefore disappear, and g.simplify_as_binary() reduces g so it contains only the variables corresponding to empty cells.
qbpp.EasySolver(g) wraps g for solving, and solver.search(target_energy=0) searches for a solution sol reaching energy 0. Since g no longer references the clue-related variables, sol only holds values for the empty cells. To produce a complete assignment over the original variables of f, we build qbpp.Sol(f).set(sol, sub): this creates a new Sol over the variables of f, copies the values of sol, and then applies the forced values from sub.
Finally, full_sol(x) returns the 3-dimensional 0/1 array, qbpp.onehot_to_int decodes each one-hot vector along axis $k$ into an integer in $\lbrace0,\ldots,8\rbrace$, and print_sudoku prints the value plus 1.
Running the program produces the clues (with . for empty cells) and the solution:
Puzzle:
. . 3 | . 2 . | 6 . .
9 . . | 3 . 5 | . . 1
. . 1 | 8 . 6 | 4 . .
------+-------+------
. . 8 | 1 . 2 | 9 . .
7 . . | . . . | . . 8
. . 6 | 7 . 8 | 2 . .
------+-------+------
. . 2 | 6 . 9 | 5 . .
8 . . | 2 . 3 | . . 9
. . 5 | . 1 . | 3 . .
Solution:
4 8 3 | 9 2 1 | 6 5 7
9 6 7 | 3 4 5 | 8 2 1
2 5 1 | 8 7 6 | 4 9 3
------+-------+------
5 4 8 | 1 3 2 | 9 7 6
7 2 9 | 5 6 4 | 1 3 8
1 3 6 | 7 9 8 | 2 4 5
------+-------+------
3 7 2 | 6 8 9 | 5 1 4
8 1 4 | 2 5 3 | 7 6 9
6 9 5 | 4 1 7 | 3 8 2