import copy
from collections import deque
import matplotlib.pyplot as plt
import matplotlib.patches as patches
# show a sudoku problem
puzzle = [
[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]
]
Sudoku as Constraint Search
Each blank is a variable with candidates 1 through 9. Rows, columns, and 3-by-3 boxes must contain no repeated digit. This is a constraint satisfaction problem (CSP).
Compare plain backtracking with a solver that combines inference and backtracking. Run the cells in order with Matplotlib installed. The saved results are specific to these puzzles, not a benchmark across Sudoku instances.
Imports and Puzzle
The puzzle is a list of nine row lists. Zero represents an unassigned cell, not a Sudoku digit. The nonzero entries are fixed clues.
Draw the Grid
The helper writes only nonzero entries, draws thin cell boundaries, and emphasizes each 3-by-3 box. The vertical coordinate is flipped so list row 0 appears at the top. Drawing does not validate a solution.
def draw_puzzle(puzzle):
fig, ax = plt.subplots(figsize=(3, 3))
ax.set_aspect('equal')
ax.set_xlim(0, 9)
ax.set_ylim(0, 9)
ax.set_xticks([])
ax.set_yticks([])
ax.add_patch(patches.Rectangle((0, 0), 9, 9, fill=False))
for i in range(9):
for j in range(9):
if puzzle[i][j] != 0:
ax.text(j + 0.5, 8.5 - i, str(puzzle[i][j]), ha='center', va='center')
for i in range(3):
for j in range(3):
ax.add_patch(patches.Rectangle((3 * j, 3 * i), 3, 3, fill=False
, linewidth=2))
for i in range(8):
ax.add_patch(patches.ConnectionPatch((i + 1, 0), (i + 1, 9), 'data', 'data'))
ax.add_patch(patches.ConnectionPatch((0, i + 1), (9, i + 1), 'data', 'data'))
plt.show()Inspect the Starting State
Choose one blank and eliminate digits already present in its row, column, and box. That manual candidate test is what the next helper automates.
Example answer
Using zero-based indices, choose (0, 2). Its row excludes 3, 5, and 7; its column excludes 8; and its box excludes 3, 5, 6, 8, and 9. The remaining candidates are 1, 2, and 4. This is a local legality check, not a guarantee that all three candidates extend to a full solution.
Check a Candidate
is_valid(puzzle, i, j, n) checks whether digit n conflicts with an existing entry in the row, column, or box of a blank cell. Integer division identifies the upper-left corner of the box.
The counter records recursive calls; success_flag avoids printing the solution repeatedly as recursion unwinds. Reset both before repeating the plain solver.
Backtrack Through Assignments
The solver chooses the first blank in row-major order and tries digits from 1 through 9. A legal digit is written into the board before recursion. If the recursive call fails, the cell is reset to zero before trying another digit.
No blanks means success. Exhausting candidates at a blank means failure. This implementation assumes the supplied clues are valid; it is not a separate validator for arbitrary filled boards. The recursion mutates its argument, so later runs pass a deep copy.
def solve(puzzle):
global success_flag, num
num += 1
for i in range(9):
for j in range(9):
if puzzle[i][j] == 0:
for n in range(1, 10):
if is_valid(puzzle, i, j, n):
puzzle[i][j] = n
if solve(puzzle):
if not success_flag:
print(f"Solved. Recursive calls: {num:,}.")
draw_puzzle(puzzle)
success_flag = True
return True
puzzle[i][j] = 0
return False
return True
Represent Candidate Domains
Every coordinate maps to a set of candidates. Blank cells initially allow all digits; clue cells begin with a singleton set. make_domains creates a fresh dictionary for each puzzle and checks the 9-by-9 shape and digit range. Conflicting clues are detected during inference.
A fixed cell keeps its singleton domain. An empty domain always means failure; it is never used to mark a processed cell.
all_cells = [(i, j) for i in range(9) for j in range(9)]
def make_domains(puzzle):
if len(puzzle) != 9 or any(len(row) != 9 for row in puzzle):
raise ValueError("The puzzle must have 9 rows and 9 columns.")
if any(type(n) is not int or not 0 <= n <= 9
for row in puzzle for n in row):
raise ValueError("Entries must be integers from 0 through 9.")
return {
(i, j): {puzzle[i][j]} if puzzle[i][j] else set(range(1, 10))
for i, j in all_cells
}
possible_values = make_domains(puzzle)
Find the Peer Cells
Peers share a row, column, or box with a cell. Set union removes duplicates where those groups overlap. The cell itself is excluded, leaving 20 distinct peers. Sorting the peers later makes the propagation order reproducible.
Remove an Assigned Digit from Peers
infer removes the assigned digit from each peer’s domain. If a peer loses its last candidate, it returns False. Otherwise it returns True, meaning this deletion step found no contradiction. It does not mean the puzzle is solved.
Because the source cell is not its own peer, its singleton remains intact. Two conflicting singleton clues make one peer’s domain empty and are rejected.
Propagate Forced Values
propagate puts singleton cells into a queue. For each one, it writes the forced digit to the board and removes that digit from peers. Newly forced peers join the queue, so propagation continues until no forced cells remain to process.
The local processed set avoids propagating the same cell twice during this call. Domains remain nonempty unless a contradiction is found. This helper mutates its arguments; the search function below gives it branch-local copies.
def propagate(puzzle, possible_values):
if any(not possible_values[cell] for cell in all_cells):
return False
queue = deque(cell for cell in all_cells
if len(possible_values[cell]) == 1)
processed = set()
while queue:
cell = queue.popleft()
if cell in processed:
continue
i, j = cell
n = next(iter(possible_values[cell]))
if puzzle[i][j] not in (0, n):
return False
puzzle[i][j] = n
processed.add(cell)
if not infer(possible_values, i, j, n):
return False
for peer in sorted(peers(i, j)):
if len(possible_values[peer]) == 1 and peer not in processed:
queue.append(peer)
return TrueSearch When Propagation Stalls
solve_reduce first propagates on copied state. If every domain is singleton, the board is complete. Otherwise, minimum remaining values (MRV) chooses an unresolved cell with the fewest candidates. Values are tried in increasing order.
Each guess restricts a fresh child domain to {n}. The recursive call propagates that decision before making another guess. If it fails, discard the child and try the next value; the parent’s board and domains stay intact. The function returns False only after propagation fails or every candidate branch fails.
num_reduce = 0
def solve_reduce(puzzle, possible_values):
global num_reduce
num_reduce += 1
copy_possible_values = copy.deepcopy(possible_values)
copy_puzzle = copy.deepcopy(puzzle)
if not propagate(copy_puzzle, copy_possible_values):
return False
unresolved = [cell for cell in all_cells
if len(copy_possible_values[cell]) > 1]
if not unresolved:
print(f"Solved. Recursive calls: {num_reduce:,}.")
draw_puzzle(copy_puzzle)
return True
cell = min(unresolved, key=lambda cell: len(copy_possible_values[cell]))
for n in sorted(copy_possible_values[cell]):
child_domains = copy.deepcopy(copy_possible_values)
child_domains[cell] = {n}
if solve_reduce(copy_puzzle, child_domains):
return True
return FalseRun Plain Backtracking
Reset the counter and output flag before each run. The deep copy protects the original clues. This puzzle takes 4,209 recursive calls with the row-major solver; calls are not the same as individual constraint checks.
Run Inference and Backtracking
The queue solves this supplied puzzle through forced values within one search call, without guessing. The same function can branch when propagation stalls. One propagation pass can do many candidate checks, so recursive-call counts are not a direct timing comparison. The final True is the returned success flag.
Test a Puzzle That Needs Guessing
An empty grid has no singleton domains, so propagation alone cannot start. The solver must restrict a guessed cell to one digit before recursion. It returns the first valid completion; an empty grid has many solutions.
Each recursive choice fixes one unresolved cell. Every candidate receives its own branch-local domains.
Reject a Locally Legal Wrong Clue
Digit 1 is locally legal at (0, 2) in the starting puzzle: it does not immediately repeat a row, column, or box digit. Fixing it there nevertheless makes this puzzle unsatisfiable. A local legality check does not guarantee a full completion.
Here the added fixed clue leads to an empty domain during initial propagation, so the solver returns False. When guessing is needed, a failed branch instead returns to its parent; the whole search fails only if every branch fails. A failed local-search run would not provide the same no-solution guarantee.
Compare the Two Approaches
- Confirm that every original clue is unchanged in the displayed solutions.
- Trace where plain backtracking undoes a choice and where inference removes a candidate.
- Explain why choosing a cell with few remaining values can reduce branching. This is the minimum remaining values (MRV) heuristic.
- Find where a guessed value changes its domain and explain why a failed branch cannot change its parent.
Answers and discussion
- Check the clues independently of the blanks. Every initially nonzero entry must equal the corresponding final entry. For example, the original top-row 5, 3, and 7 retain their positions. Plain backtracking writes only into zeros; the inference version initializes each clue with exactly its given digit. A complete solution also needs each row, column, and box to contain digits 1 through 9.
- Undo versus eliminate. In
solve, the linepuzzle[i][j] = 0restores a blank after a recursive branch fails. Ininfer,.remove(n)deletes an assigned digit from peer domains. The inference solver instead uses copied boards and domains, so it discards a failed child rather than undoing changes in shared state. - MRV exposes difficult choices early. A cell with two candidates creates at most two branches, while one with eight creates up to eight. A singleton is forced, and an unresolved empty domain signals failure. MRV often reduces wasted search by finding constrained decisions and contradictions early, but does not guarantee the smallest search tree on every puzzle.
- A guess changes its domain. The line
child_domains[cell] = {n}records the decision. The recursive call propagates it on a copied board and copied domains. No set is shared with the parent, and each candidate starts with a fresh copy. Restricting an unresolved domain and propagating its singleton makes progress; failure discards that branch’s deletions.
Takeaway: inference can avoid search, but a general solver still needs correct state management and branching when propagation stalls.