Sudoku Solver
Fill empty cells with a digit that satisfies row, column and box; backtrack on dead ends.
Decision · step 2 of 20Backtracking: A 4 x 4 sudoku with a dead end to back out of
Cell (0, 1). 1 is already in row 0. 2 fits. 3 is already in column 1. 4 fits. Place 2, the smallest that fits, and move on.
What you will see
Digits are tried in a cell; conflicts flash; a dead cell erases and moves back.
Cost
| Best | O(1) |
|---|---|
| Average | exponential |
| Worst | O(9^(empty cells)) |
| Space | O(empty cells) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Each node of the decision tree announces the choice made and whether it led to success, failure or further choices.
Reduced motion: Tree nodes appear and grey out in place; no travelling focus.
Before this
Taught by the same lesson
Backtracking covers these too, in the same run.