This Python project shows how to implement a sudoku generator and solver using the Simulated Annealing algorithm. Simulated Annealing is a probabilistic optimization algorithm based on stochastic processes and Monte Carlo Markov Chain (MCMC) that is particularly effective in solving combinatorial optimization problems. The code can generate and solve sudoku problems of arbitrary size.
These instructions will help you set up the project on your local machine for development and testing purposes.
Make sure you have the following installed on your system:
- Python 3.x
- Pip (Python package installer)
-
Clone the repository:
git clone https://github.com/giovanni-gatti/sudoku-solver.git
-
Navigate to the project directory:
cd sudoku-solver -
(Optional, recommended) Create and activate a virtual environment:
python -m venv venv source venv/bin/activate -
Install the required dependencies (using pip):
pip install -r requirements.txt
Run the project code with the following command:
python3 solve.pyThe src/SimAnn.py file contains the functions to run the Simulated Annealing algorithm to sample from the Boltzmann distribution using the Metropolis-Hastings rule.
The constructor of the Sudoku class, defined in src/Sudoku.py, accepts either an integer number or another Sudoku object as an argument. If the constructor gets a number, it initializes a sudoku table of size equal to the number. If instead it receives a Sudoku object, it chooses at random a fraction of the entries to keep fixed (with probability defined by the argument r), and shuffles the rest.
In the solve.py script, a valid sudoku table is first generated and filled up. Then, a sudoku problem to be solved is created from this valid sudoku table. Finally, the sudoku problem is solved.