A production-level Sudoku Solver built using Backtracking and Dancing Links (DLX) algorithms with step-by-step visualization, performance benchmarking, and interactive GUI.
This project demonstrates core Data Structures and Algorithms (DSA) concepts including recursion, constraint satisfaction, optimization techniques, and efficient search space exploration with a modern software architecture.
- 🔄 Step-by-step solving visualization
- ⚡ Backtracking + DLX algorithm support
- 📊 Performance benchmarking (time, memory, steps, backtracks)
- 🔬 Algorithm comparison (Backtracking vs DLX)
- ✏️ Custom puzzle input
- 🎨 Modern production UI with theme support
- 🔍 Constraint validation (row, column, subgrid)
- 🧪 Unit testing support
- 🌐 FastAPI backend API
- 🐳 Docker deployment ready
- 📝 Logging and configuration management
This project implements a Sudoku Solver that automatically solves a given 9×9 puzzle while satisfying all Sudoku constraints.
The system demonstrates:
- Recursion and backtracking techniques
- Constraint satisfaction problem solving
- Algorithm visualization
- Performance measurement and benchmarking
- Algorithm comparison (Backtracking vs DLX)
- Interactive user interface
It combines theoretical algorithm concepts with real-world application design.
git clone <your-repo-url>
cd sudoku-solver
pip install -r requirements.txt
python main.py
uvicorn src.api.main:app --reload
pytest
assets/images/solver.png
assets/images/input.png
- Python
- Backtracking Algorithm
- Dancing Links (DLX)
- Recursion
- Pygame (GUI Visualization)
- FastAPI (API Service)
- Pytest (Testing)
- Docker (Deployment)
- Logging System
- Performance Benchmarking
- Matrix / 2D Array Operations
Backtracking is a recursive problem-solving technique that explores possible solutions and eliminates invalid ones.
DLX is an optimized algorithm for solving exact cover problems and provides faster performance for complex Sudoku puzzles.
Sudoku is a constraint satisfaction problem where each solution must satisfy:
- Row constraint
- Column constraint
- 3×3 subgrid constraint
The project compares multiple solving approaches:
- Recursive search
- Constraint validation
- Explores search space systematically
- Exact cover formulation
- Optimized search
- Faster for complex puzzles
- Execution time
- Memory usage
- Steps and backtracks
- Nodes visited
DLX typically provides faster performance than standard backtracking.
- 2D Matrix → Sudoku grid representation
- Recursion Stack → Function calls during solving
- Constraint Checking Functions → Rule validation
- Highlights current cell
- Shows number placement
- Displays backtracking process
- Adjustable solving speed
- Counts recursive calls
- Tracks backtracking steps
- Measures execution time
- Displays solving statistics
- Manual puzzle entry
- Accepts values 1–9
- Empty cells represented as 0
- Input validation with error detection
- Row validation
- Column validation
- 3×3 subgrid validation
- Sudoku represented as 9×9 grid
- Empty cells represented using
0 - Solver fills all empty cells while maintaining constraints
Worst case: O(9^(n²)) for an n×n grid.
Backtracking explores possible values but prunes invalid paths early.
O(n²) due to board storage and recursion stack.
Sudoku-Solver/
│
├── src/
│ ├── api/ # FastAPI backend
│ ├── solver/ # Solver algorithms
│ ├── gui/ # GUI implementation
│ └── utils/ # Helper functions & configs
│
├── tests/ # Unit tests
├── assets/ # Images and icons
├── docs/ # Documentation
├── main.py # Entry point
├── Dockerfile
├── requirements.txt
└── README.md
- Puzzle solving systems
- Constraint satisfaction problems
- AI problem solving
- Game development
- Scheduling and optimization systems
- Designed primarily for 9×9 Sudoku puzzles
- Performance varies with puzzle difficulty
- Support for different grid sizes
- Advanced heuristics (MRV, forward checking)
- Web-based Sudoku interface
Hemanth Gudi