Rat in a Maze
Move through open cells toward the exit; retreat from dead ends.
Decision · step 2 of 8Backtracking: A maze with a dead end
At (0, 0). down is open: step to (1, 0).
What you will see
The path grows through the grid and retracts from dead ends.
Cost
| Best | O(r * c) |
|---|---|
| Average | exponential |
| Worst | O(4^(r * c)) |
| Space | O(r * c) |
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
Related
Taught by the same lesson
Backtracking covers these too, in the same run.