Sudoku Solver

About

My first-semester project for Fundamentals of Computer and Programming at Shiraz University (February 2021). Rather than brute-force backtracking, the solver computes the candidates of every empty cell and applies the same elimination techniques a person would, one deduction at a time, until none applies. The original single-script submission was later restructured, tested and extended with the triple and quad techniques.

Techniques

Applied in order, restarting from the top after every deduction:

1. Naked single — a cell with exactly one candidate takes that value.
2. Hidden single — a value that fits in only one cell of a row, column or box goes there.
3. Naked pair / triple / quad — k cells of a unit whose candidates together are exactly k values, so those values are removed from the rest of the unit.
4. Hidden pair / triple / quad — k values confined to the same k cells, so those cells keep nothing else.

Pairs, triples and quads share one implementation each (naked_subset(k) and hidden_subset(k)).

Tooling

• Command-line entry point that reads a puzzle from a file or stdin, with a --log flag that prints every deduction.
• Optional --backtrack guess-and-check fallback for puzzles that need X-Wing-class steps.
• Pygame step-through viewer: placed digits drawn large, remaining candidates small, one deduction per key press.
• pytest cases, one per technique, on small hand-made grids.