This project implements a Simulated Annealing (SA) algorithm to solve Sudoku puzzles, inspired by the paper "Metaheuristics can solve Sudoku puzzles" by Lewis (2007). The algorithm demonstrates a reliable approach to consistently find solutions to Sudoku puzzles using a metaheuristic optimization technique.
The SA algorithm works by iteratively exploring the solution space and probabilistically allowing worse solutions to escape local minima. As the process progresses, the "temperature" parameter gradually decreases, refining the search. If a better solution isn't found within a set number of steps, a reheating mechanism is applied to help the search escape potential plateaus.
notebook.ipynb- A Jupyter Notebook demonstrating and visualizing the SA approach for solving Sudoku puzzles, with step-by-step explanations.simulated_annealing.py- Core implementation of the Simulated Annealing algorithm.sudoku_solver.py- Contains helper functions, the objective funciton, the nieghborhood operator, the delta evaluation function and the necessary Sudoku-specific logic required by the SA algorithm.
find_square: Determines the 3x3 grid for a given cell.initial_candidate_sudoku: Generates an initial candidate Sudoku solution.objective_function: Computes the objective function value for a given Sudoku solution.neighborhood_operator: Swaps two random cells in the same 3x3 grid of the Sudoku.delta_evaluation: Evaluates the change in the objective function value after a swap operation.simulated_annealing: Executes the Simulated Annealing algorithm.simulated_annealing_e: Executes an enhanced version of the Simulated Annealing algorithm with delta evaluation.
The results and visualizations can be found in the notebook.ipynb file. Open it with Jupyter Notebook to see step-by-step explanations and plots.
- Lewis, R. Metaheuristics can solve sudoku puzzles. J Heuristics 13, 387–401 (2007). DOI: https://doi.org/10.1007/s10732-007-9012-8