This project implements a Sudoku solver using the Simulated Annealing optimization algorithm 🔄. The solver mimics the physical process of heating a material and then slowly lowering the temperature 🌡️ to decrease defects, thus minimizing the energy (number of conflicts) of the Sudoku puzzle.
- Simulated Annealing Algorithm 🔥: Utilizes simulated annealing to solve Sudoku puzzles by minimizing the number of conflicts.
- Dynamic State Generation 🔄: Generates new potential solutions by mutating the current state, respecting immutable cells.
- Optimization Over Iterations ⏳: Gradually decreases the temperature to reduce the likelihood of accepting worse solutions, honing in on the optimal solution.
The project is structured into several key components:
- SingleSolution Class 🧩: Manages individual solutions of the Sudoku puzzle, providing methods to generate, mutate, and evaluate the fitness of solutions.
- SimulatedAnnealing Class 🌡️: Oversees the simulated annealing process, including temperature management, state transitions, and probability calculations for accepting new states.
- Utils Folder 📁: Contains scripts for data handling and visualization:
- Sudoku CSV Processor: Manages reading and formatting Sudoku puzzles and solutions from CSV files.
- Matrix Image Generator: Generates and saves images of Sudoku solution matrices for visualization.
- Plot Generator: Produces plots to visually represent the evolution of solution metrics over iterations.
For more detailed information and usage instructions, check out our documentation.
Ensure Python is installed along with the following packages:
numpymultiprocessingpandasmatplotlibcsvpytest
- Clone the Repository 📥:
- Use the command
git clone https://github.com/F-a-b-r-i-z-i-o/Parallel-SA-For-Sudoku-Solving.gitto clone the repository to your local machine.
- Use the command
- Create and Activate Virtual Environment 🌐:
- Navigate to the repository directory:
cd Parallel-SA-For-Sudoku-Solving - Create a virtual environment named
envwithin this directory:python3 -m venv env
- Activate the virtual environment using the
script.shscript:. ./active_env.sh
- Navigate to the repository directory:
- Install Dependencies 📦:
- Install required dependencies by executing:
pip3 install -r requirements.txt
- Install required dependencies by executing:
To ensure the functionality and stability of the Sudoku solver, tests have been implemented using pytest. Here’s how you can run these tests:
- Activate the Virtual Environment
- Run Tests:
- With the virtual environment active, simply execute the following command in the project root directory:
pytest
- This will discover and run all tests written for the Sudoku solver, reporting any failures and their respective reasons.
- With the virtual environment active, simply execute the following command in the project root directory:
This setup enables easy testing and debugging, ensuring that enhancements or changes do not introduce regressions or new issues.
The Sudoku puzzles used in this project were sourced from the following Kaggle dataset: Sudoku Dataset.
While all Sudoku puzzles have been solved using the algorithm, due to size limitations, only the first 100 solutions are uploaded to GitHub. The complete set of solutions remains available upon request or can be generated using the provided scripts.
The simulated annealing algorithm has been effectively applied to solve numerous Sudoku puzzles. The method's adaptability and efficiency in finding solutions within acceptable time frames have been thoroughly documented through various metrics plotted during the solving process.
Contributions to enhance the project are welcome. Please feel free to fork the repository, make improvements, and submit pull requests.
This project is released under the MIT License.
Enjoy 2F_