Sudoku Solver

A Sudoku solver written in Python that supports arbitrary board sizes — 4×4, 9×9, and non-square variants like 6×6 — all from the same codebase.

Features

• Solves standard 9×9 Sudoku and other valid sizes (N×N where N = box_row_size × box_col_size, both ≥ 2)
• Backtracking solver that searches only legal candidates rather than brute-forcing every digit
• Validates puzzles at construction time and rejects inputs that break Sudoku rules
• Clear command-line interface with helpful error messages

Installation

Requires Python 3.10+.

git clone https://github.com/F5F0A0/sudoku
cd sudoku
python -m venv .venv
source .venv/bin/activate        # on Windows: .venv\Scripts\activate
pip install -e .

The editable install (-e) means changes to the source take effect immediately without reinstalling.

Usage

Solve a puzzle passed as a string. Use 0 or . for empty cells:

python -m sudoku "530070000600195000098000060800060003400803001700020006060000280000419005000080079"

Or read a puzzle from a file:

python -m sudoku --file puzzle.txt

Example

Puzzle:
---------------------------------------
| 5 | 3 |   ||   | 7 |   ||   |   |   |
| 6 |   |   || 1 | 9 | 5 ||   |   |   |
|   | 9 | 8 ||   |   |   ||   | 6 |   |
---------------------------------------
| 8 |   |   ||   | 6 |   ||   |   | 3 |
| 4 |   |   || 8 |   | 3 ||   |   | 1 |
| 7 |   |   ||   | 2 |   ||   |   | 6 |
---------------------------------------
|   | 6 |   ||   |   |   || 2 | 8 |   |
|   |   |   || 4 | 1 | 9 ||   |   | 5 |
|   |   |   ||   | 8 |   ||   | 7 | 9 |
---------------------------------------

Solved in 0.048s:
---------------------------------------
| 5 | 3 | 4 || 6 | 7 | 8 || 9 | 1 | 2 |
| 6 | 7 | 2 || 1 | 9 | 5 || 3 | 4 | 8 |
| 1 | 9 | 8 || 3 | 4 | 2 || 5 | 6 | 7 |
---------------------------------------
| 8 | 5 | 9 || 7 | 6 | 1 || 4 | 2 | 3 |
| 4 | 2 | 6 || 8 | 5 | 3 || 7 | 9 | 1 |
| 7 | 1 | 3 || 9 | 2 | 4 || 8 | 5 | 6 |
---------------------------------------
| 9 | 6 | 1 || 5 | 3 | 7 || 2 | 8 | 4 |
| 2 | 8 | 7 || 4 | 1 | 9 || 6 | 3 | 5 |
| 3 | 4 | 5 || 2 | 8 | 6 || 1 | 7 | 9 |
---------------------------------------

Architecture

The project separates three concerns into independent layers:

• Cell — a single square. Tracks its value, whether it is an original clue ("given"), and the set of digits that could still legally go in it.
• Grid — the board. Owns a 2D structure of Cell objects and answers the queries a solver needs: rows, columns, boxes, peers, candidates, and whether the board is valid or solved.
• BacktrackingSolver — the algorithm. Depends only on Grid's public interface, so it could be swapped for a different solving strategy without touching the board representation.

This separation means input formats, board representation, and solving algorithm can each change independently.

Design notes

• Arbitrary sizes. Box dimensions default to √N × √N for perfect-square boards, or can be given explicitly for variants like 6×6 (2×3 boxes).
• Construction-time validation. A Grid cannot be built from a puzzle that already violates Sudoku rules — the error is caught immediately rather than surfacing later as a confusing solver failure.
• Candidate-driven search. The solver iterates only the legal values for each cell instead of trying all digits and validating afterward.

Future work

• Image input: read puzzles from a photo using OCR
• Constraint-propagation techniques (naked singles, hidden singles)
• Minimum-Remaining-Values heuristic for faster solving on hard puzzles
• A web interface

Project structure

src/sudoku/
├── __main__.py                 # entry point for `python -m sudoku`
├── cli.py                      # command-line interface
├── core/
│   ├── cell.py                 # Cell class
│   ├── grid.py                 # Grid class
│   └── basic_9x9_solver.py     # puzzle-string parser
└── solver/
    └── backtracking.py         # BacktrackingSolver

tests/                          # pytest test suite
puzzles/                        # sample puzzle files