AlgoScope

Rat in a Maze

Move through open cells toward the exit. Retreat from dead ends.

Backtracking, algorithm, intermediate
Step down to 1, 0.012012111101001
Step down to 1, 0.012012111101001

Backtracking: A maze with a dead end

Decision, step 2 of 8

At (0, 0). down is open: step to (1, 0).

How backtracking works

Cost

Best
O(r * c)
Average
exponential
Worst
O(4^(r * c))
Space
O(r * c)

Leads to

Topics that need this one first.

Taught by the same lesson

Backtracking covers these too, in the same run.