logigrid

A Sudoku solver that reasons like a human before it guesses.

What it is

Most Sudoku solvers just backtrack: try a digit, recurse, undo if it breaks. That solves anything, but it tells you nothing about how hard the puzzle actually is. logigrid instead applies the same techniques a person uses on paper — naked singles, hidden singles, locked candidates, naked pairs, hidden pairs — always reaching for the simplest applicable technique first, and only falls back to backtracking search when logic alone runs out. The result is a step-by-step trace of why each digit got placed, and a difficulty rating derived from which techniques were actually required rather than an arbitrary label.

Feed it the famous Arto Inkala "world's hardest sudoku" and it'll tell you straight away that no amount of pure logic cracks it — 0 logical steps before it has to start guessing.

Install / run

Needs Python 3.9+, no dependencies.

git clone https://github.com/neverlone/logigrid.git
cd logigrid
python3 -m logigrid examples/easy.txt

Usage example

Puzzle files are 9 lines of 9 characters, . or 0 for blanks:

$ python3 -m logigrid examples/hard.txt
2 1 9 | 5 7 8 | 3 4 6
5 3 6 | 9 4 1 | 8 7 2
4 7 8 | 2 6 3 | 5 9 1
---------------------
3 5 1 | 6 9 7 | 4 2 8
7 6 2 | 4 8 5 | 1 3 9
9 8 4 | 3 1 2 | 7 6 5
---------------------
1 9 3 | 7 5 6 | 2 8 4
6 2 5 | 8 3 4 | 9 1 7
8 4 7 | 1 2 9 | 6 5 3

Difficulty: Medium
Logical steps: 44
  naked single: 40
  hidden single: 3
  locked candidates: 1

examples/ has three puzzles that exercise the whole range:

file	difficulty	notes
easy.txt	Easy	solved entirely by naked/hidden singles
hard.txt	Medium	needs a locked-candidates deduction, no guessing
extreme.txt	Extreme (guessing required)	Arto Inkala's 2012 "world's hardest sudoku" — logic alone gets 0 steps

How it works

The board is 81 cells; for every empty cell logigrid tracks the set of digits still legal for it given its row, column and 3x3 box (its "candidates"). Each solving pass tries these techniques, in order, and applies the first one that fires:

1. Naked single — a cell has exactly one remaining candidate.
2. Hidden single — a digit fits in only one cell within some row, column, or box, even if that cell has other candidates too.
3. Locked candidates — a digit's candidates within a box all sit in one row or column, so it can be eliminated from the rest of that row/column outside the box (and the box-line-reduction mirror of that).
4. Naked pair — two cells in a unit share the exact same two candidates, so those two digits can be eliminated from every other cell in the unit.
5. Hidden pair — two digits are confined to the same two cells in a unit, so every other candidate can be stripped from those two cells.

After each successful deduction the candidate sets are updated and the solver starts back at technique 1 — mirroring a human who always prefers the easiest available move. If no technique fires and the puzzle isn't complete, logigrid falls back to a recursive backtracking search (picking the cell with fewest candidates first) to finish it, and flags that the puzzle needed guessing. The difficulty rating is just the hardest technique tier that was actually needed: Easy (singles only), Medium (locked candidates), Hard (pairs), or Extreme (backtracking).

Tests

python3 -m unittest discover -s tests -v

Covers board parsing, individual technique functions, and full solves of all three bundled example puzzles (checking the result is a valid, complete grid that preserves every original clue).