A Sudoku puzzle is a constraint-satisfaction problem: fill a 9 × 9 grid with digits 1–9 so every row, column, and 3 × 3 subgrid contains each digit without repetition. section 5.4
The puzzle adapts the Latin-square idea into a popular number game, while also supporting applications in problem-solving practice, developmental psychology, and steganography. section 5.4
Solving approaches include:
- Use backtracking to search assignments that satisfy the row, column, and subgrid constraints. section 5.4
- Use simulated annealing to search candidate grids, with parameters such as iteration limits, temperature bounds, and cooling schedule. section 5.4
- Compare simulated annealing with backtracking and PuLP across puzzle difficulties; performance varies substantially by method and difficulty. section 5.4
Python setup
A hard 9 × 9 instance can be represented as a nested list, passed to optalgotools.problems.Sudoku, and solved with SimulatedAnnealing using geometric cooling. section 5.4
Listing 5.3 Solving Sudoku using SA
from optalgotools.algorithms import SimulatedAnnealing #1
from optalgotools.problems import Sudoku #2
sa = SimulatedAnnealing(max_iter=100000, max_iter_per_temp=1000,
initial_temp=500, final_temp=0.001, cooling_schedule='geometric',
cooling_alpha=0.9, debug=1) #3
Sudoku_hard = [
[9, 0, 0, 1, 0, 0, 0, 5, 4],
[0, 0, 0, 0, 8, 0, 0, 0, 0],
[0, 0, 5, 0, 0, 9, 0, 0, 3],
[0, 9, 0, 0, 3, 5, 0, 4, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0],
[4, 1, 0, 2, 6, 0, 0, 8, 0],
[7, 0, 0, 3, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 4, 0, 0, 0, 0],
[3, 5, 0, 0, 0, 1, 0, 0, 6],
]
sudoku_prob = Sudoku(Sudoku_hard)
sudoku_prob.print() #4
#4
sudoku_prob.solve_backtrack() #5
sa.run(sudoku_prob, 0) #6
#1 Import the SA solver.
#2 Import a Sudoku problem.
#3 Create a SA solver with the selected parameters.
#4 Create a hard <span class="times">9 × 9</span> Sudoku (available variants include trivial, easy, medium, hard, and evil).
#5 Solve the Sudoku using the backtracking algorithm.
#6 Solve the Sudoku using SA.
Inspect the complete Sudoku input and simulated-annealing configuration, including iteration and temperature settings. section 5.4
