Math

Backtracking: queens and sudoku

Follow recursive backtracking for N queens and full 9×9 Sudoku, compare pruning and variable ordering, and enumerate queen solutions.

By Mykhailo Makarov

Actual application image

Try this

Watch choices, rejected branches and retreats in a real recursive search. Queens exclude shared columns and diagonals. Sudoku uses row, column and 3×3 constraints; MRV chooses the most constrained empty cell.

Equations used in the module

Equations
Queens: qᵢ ≠ qⱼ and |qᵢ−qⱼ| ≠ |i−j|
Sudoku: every row, column and 3×3 box contains 1…9
Backtracking explores a partial assignment, then undoes it
MRV chooses an unfilled variable with the fewest legal values

Related experiments

Back to catalogue

Math

Edit distance and diff

Build edit-distance tables from your own strings and trace an optimal alignment with adjustable substitution cost.

Math

String search: KMP, Boyer–Moore, Rabin–Karp

Compare naive, KMP, full Boyer–Moore and rolling-hash substring search, with recorded comparisons, prefix tables and overlapping matches.

Math

Mazes: generate and solve

Generate mazes with depth-first carving, Prim and Wilson, then compare breadth-first, A* and wall-following routes.