Algorithmic Sudoku Solver

A Python application that visually demonstrates and compares different algorithms for solving Sudoku puzzles.

Overview

This Sudoku Solver application visualizes how different algorithms approach and solve Sudoku puzzles. It generates a random puzzle and then solves it using four different algorithms, showing the step-by-step solution process and comparing their performance.

Features

• Interactive visualization of Sudoku solving algorithms
• Real-time animation of solving process
• Performance comparison between different algorithms
• Color-coded visualization (fixed numbers, correct placements, backtracking)
• Summary view of performance metrics

Algorithms Implemented

1. Backtracking Algorithm: A depth-first search algorithm that explores possibilities until finding a solution, backtracking when necessary.

2. Divide and Conquer: An approach that focuses on solving 3×3 subgrids first, working through the puzzle section by section.

3. Greedy Algorithm: Uses heuristics to prioritize cells with the fewest possible valid numbers, making locally optimal choices at each step.

4. Recursive Algorithm: Similar to backtracking but with a different traversal pattern and number selection strategy.

Requirements

• Python 3.6+
• Pygame 2.0.0+

Installation

1. Clone this repository:

git clone https://github.com/kyazs/sudoku-solver.git
cd sudoku-solver

2. Install the required packages:

pip install pygame

Usage

Run the program:

python sudoku.py

The application will:

1. Generate a random Sudoku puzzle
2. Solve it using each algorithm in sequence
3. Display a performance comparison at the end

Press any key to exit after the comparison is shown.

How It Works

• Puzzle Generation: Creates a fully solved Sudoku grid, then removes a percentage of numbers to create a puzzle
• Visualization:
  • Gray cells: Fixed/initial numbers
  • Green cells: Correctly placed numbers
  • Red cells: Backtracked numbers (attempts that didn't work)
  • Blue highlight: Currently processing cell
• Performance Measurement: Times each algorithm's solution process

Contributing

Contributions are welcome! Feel free to submit a Pull Request.

License

This project is licensed under the MIT License - see the LICENSE file for details.