Repository files navigation

• 📘 Table of Contents
  • 🌟 About the Project
    • 👾 Tech Stack
    • 🎯 Features
  • 🔧 Configuration and Environment Variables
    • Example Environment Variables
  • 🧰 Getting Started
    • ❗ Prerequisites
    • ⚙ Installation
    • Run Project Reference Site Locally
    • 🔬 Running Tests
    • 🚀 Run Locally
  • 👀 Usage
  • 🗺 Roadmap
  • ⚠ License
  • 💎 Acknowledgements

This Sudoku Solver project is designed to solve Sudoku puzzles using two state-of-the-art techniques:

1. AConstraint Propagation approach that leverages backtracking, forward-checking, and advanced heuristics such as MAC (Maintaining Arc Consistency), MRV (Most Restrictive Variable), and LCV (Least Constraining Value).
2. ALocal Search Genetic Algorithm (LSGA) based on a novel evolutionary approach that uses column and sub-block local search to effectively balance exploration and exploitation.

Both algorithms are benchmarked on a large dataset of Sudoku puzzles, allowing detailed performance analysis in terms of speed, memory efficiency, and backtracking steps. Results from these analyses offer insights into each algorithm's strengths and weaknesses across varying levels of Sudoku difficulty.

• Solves Sudoku puzzles using both Constraint Propagation and Genetic Algorithms.
• Benchmarking capabilities for evaluating performance, including tracking memory and CPU usage.
• Detailed logging and configurable settings for custom execution parameters.
• Advanced heuristics and local search techniques for enhanced algorithmic efficiency.

To customize the application, adjust variables inconfig.py.

# Population Sizepopulation_size=150# Elite Poulation Sizeelite_size=50# Tournament Sizetournament_size=2# Maximum Generations Countmax_generations=200# PC1 or Individual Crossover Rateindividual_crossover_rate=0.2# PC2 or Row Crossover Raterow_crossover_rate=0.1# PM1 or Swap Mutation Rateswap_mutation_rate=0.3# PM2 or Reinitialization Mutation Ratereinitialization_mutation_rate=0.05

• Python 3.12 or later is required to run this project.
• We recommend usingPoetry for dependency management. Install it globally:

  pip install poetry

Clone the repository:

git clone https://github.com/PayThePizzo/SudokuSolver.git

Navigate to the project directory:

cd sudoku-solver

Create the virtual environment:

# Root folderpython -m venv .venv

Activate the environment:

# Root folder (Windows).venv\Scripts\activate

Install dependencies with poetry:

(.venv) pip install poetry(.venv) poetry install

Install dependencies with pip:

(.venv) pip install -r requirements.txt

You can run the project reference site to quickly consult the reference and read the comparative analysis.

Just run

mkdocs serve

To execute unit tests for both Constraint Propagation and LSGA modules, run:

# MACpoetry run pyton /tests/test_sudoku_solver_MAC.py# LSGApoetry run pyton /tests/test_sudoku_solver_LSGA.py

To run the project locally, run the solver after adding a given puzzle:

# MACpoetry run python sudoku_solver_CSP.py# LSGApoetry run python sudoku_solver_LSGA.py

This toolkit can be used to analyze and solve any 9x9 Sudoku puzzle, either by specifying a puzzle directly in the code or by loading from a dataset.

• Implement Constraint Propagation algorithm with MAC, MRV, LCV and Backtracking
• Integrate Local Search Genetic Algorithm for alternative solving
• Implement performance tracking and benchmarking across multiple puzzles
• Add a web interface for interactive Sudoku solving and visualization
• Improve LSGA mutation and crossover strategies
• Improve MAC with Numpy
• Fix Logger
• Add GPU support for LSGA and MAC with PyTorch or Tensorflow
• Fix Unit Tests

Distributed under the GNU GPL v3 License. SeeLICENSE for more information.

This project draws on foundational work in AI and Sudoku-solving algorithms. Notable references include:

• The implementation of LSGA is completely inspired by the paper:A Novel Evolutionary Algorithm With Column and Sub-Block Local Search for Sudoku Puzzles by Chuan Wang et al. The algorithm has been implemented to the best of our capabilities, with aim of reproducing their work. Our implementatio isnot official by any means and is not to be considered like a distribution of the original algorithm.
• Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig.