AlgoScope

Sudoku Solver

Fill empty cells with a digit that satisfies row, column and box. Backtrack on dead ends.

Backtracking, algorithm, advanced
Place 2 at 0, 1.0123012312432
Place 2 at 0, 1.0123012312432

Backtracking: A 4 x 4 sudoku with a dead end to back out of

Decision, step 2 of 20

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.

How backtracking works

Cost

Best
O(1)
Average
exponential
Worst
O(9^(empty cells))
Space
O(empty cells)

Taught by the same lesson

Backtracking covers these too, in the same run.