Sudoku Solver,
4×4 to 16×16.

Algorithm guide

How the Sudoku Solver works.

The solver uses a single unified engine for every board size: a constraint-propagation backtracking search guided by the Minimum Remaining Values (MRV) heuristic. Whether the grid is a 4×4 warm-up or a 256-cell 16×16 challenge, the algorithm adapts automatically — no size-specific code paths, no lookup tables, no pre-computed solution databases.

The Backtracking algorithm, step by step

The algorithm treats the puzzle as a constraint-satisfaction problem (CSP): a set of variables (empty cells), each with a domain of legal values (digits that don't conflict with the cell's row, column, or box), and constraints (no two cells in the same unit share a digit).

At every step it picks one empty cell, iterates over its legal candidates, assigns the next candidate, and recurses. If a branch reaches a cell with an empty domain, meaning no digit is legal — it backtracks: it undoes the last assignment and tries the next candidate. When every cell is filled without contradiction, the puzzle is solved. The search tree is finite for every board size, so the algorithm always terminates.

Minimum Remaining Values (MRV) heuristic

The most impactful optimisation is which cell to pick at each step. Choosing left-to-right gives poor results on large boards. Instead, the solver always selects the empty cell with the fewest legal candidates: the MRV or "fail-first" rule. This has two benefits:

• Contradictions surface at the shallowest possible tree depth, cutting entire subtrees before they're explored.
• Cells with exactly one candidate (naked singles) are resolved with zero backtracking, making easy puzzles nearly instantaneous regardless of board size.

The performance gains compound on large boards: a 16×16 grid has 256 cells and up to 16 candidates each — a search space of roughly 16²⁵⁶ without pruning. MRV combined with constraint propagation reduces the practical search to milliseconds for well-formed puzzles.

Eight board sizes: one engine

Every board size is defined by three numbers: the grid dimension N, the box height r, and the box width c (where r × c = N). The engine reads these from a config object and derives all constraints at runtime, so adding a new size requires only one config entry.

For boards larger than 9×9 the digit set exceeds single characters. This solver follows the standard competitive convention: digits 10–16 are displayed as letters A–G (the same mapping used by 16×16 Sudoku apps worldwide). Type a letter or its numeric value, both are accepted.

How the peer-cache makes large boards fast

For each board config the engine pre-computes a peer list: the set of cells that constrain any given cell (its row, column, and box neighbours). This list is computed once and cached in memory. On subsequent calls for the same config, including every cell change and every solve — the engine reads pre-built arrays instead of recomputing relationships. The cache is indexed by N-r-c, so switching between board sizes is instant after the first use.

The randomized puzzle generator

Clicking Generate puzzle creates a brand-new puzzle in three phases:

1. Diagonal-box seeding. The generator fills each box on the main diagonal with a random permutation of 1–N. These boxes are mutually independent; they share no row, column, or other box, so any permutation is immediately valid, with no constraint checking required. This gives the backtracking step a rich, diverse starting point.
2. Randomized backtracking. The remaining cells are filled using the same MRV backtracking engine, but with candidates shuffled into random order before each trial. Because the diagonal boxes already fill a significant fraction of every row and column, the solver finds a complete random solution very quickly.
3. Controlled cell removal. Once a solved grid exists, the generator randomly removes a percentage of cells based on the chosen difficulty: ~38% for Easy, ~53% for Medium, and ~65% for Hard. The removals are randomized independently every time, so consecutive "Generate" clicks always produce different puzzles.

Because the starting permutations are random and the removal indices are randomly shuffled, the probability of generating the same puzzle twice is astronomically small, effectively impossible in practice.

Conflict detection

As you type, the grid continuously checks every filled cell against its peers. Any cell that shares a digit with another cell in its row, column, or box is highlighted in red — on all board sizes, with the correct box boundaries for each configuration. The Solve instantly button is disabled while conflicts exist; resolve them before asking for a solution.

The Hint system

Hint uses a two-tier strategy. First it scans every empty cell for a naked single: a cell whose only legal digit, given the current board state, is exactly one value. Naked singles can be filled without any search, so this tier is instantaneous. If no naked single exists the solver internally computes the full solution and reveals the value of the most-constrained unfilled cell — enough of a nudge to make progress without giving away the puzzle.

Is every valid puzzle solvable?

Yes. The backtracking algorithm is complete: it will always find a solution if one exists, and correctly report "no solution" if none does. A well-formed puzzle has exactly one solution; puzzles with multiple solutions are technically ambiguous, but the solver returns the lexicographically first valid answer. This guarantee holds for all eight board sizes.