TwiddleLab / Code / Recursion: Functions That Call Themselves
Backtracking: Solving a Maze
What you will learn
- Backtracking: try a choice and go deeper; at a dead end, undo the last choice and try the next one.
- In code, each call tries its options in order and returns False when none works, so the caller tries its next option.
- Mark visited cells, or the search walks in circles until the stack overflows.
- The chalk line is the stack of calls. Flood fill and AI search work the same way.
How the lesson goes
Lost in a maze with chalk in your pocket. Is there a rule that always gets you out?
Walk to the star. Your chalk marks the way; step back and it rubs out.
A robot follows one rule: try right, then down, then left, then up.
Where does it first hit a dead end and have to turn back? Tap the cell.
Watch the robot. The chalk is its stack of calls.
Each cell is a call to solve(r, c). A dead end returns False and the robot steps back.
solve(r, c) calls solve on its neighbours one by one. If all of them return False, it returns False too, its card comes off the stack, and its caller tries its next neighbour. That is backtracking.
Backtracking.
Backtracking is brute force that gives up early: go down one choice; the moment it's hopeless, undo it and try the next.
Each choice is a recursive call. A dead end returns False, which sends control back to the caller, who tries its next option.
A visited mark (the chalk) stops the search from walking in circles. Base cases: the goal says True, a wall or chalk says False.
Predict the robot in a bigger maze.
At each fork, tap the cell it enters next. Right, down, left, up.
Write the robot: solve(r, c).
Base cases first: the goal says True, anything but open floor says False. Then chalk the cell and try the four neighbours.
or tries each neighbour left to right and stops at the first True, so the order right, down, left, up is built into one line. return False at the end is the step back.
This robot forgot its chalk. It crashes. Fix it.
Without marks, it walks back and forth between two cells forever.
From (3, 3) the robot tries left to (3, 2), and from (3, 2) it tries right back to (3, 3), forever. A chalk mark makes the second visit hit the != "." base case and return False.
Paint bucket: the same robot, without a goal.
A fill visits a cell, colors it, and spreads right, down, left, up. Match the target in as few taps as you can.
New maze. Draw the chalk line the robot ends with.
Dead ends get rubbed out, so only the way to the star keeps its chalk. Then Check.
When solve reaches G, every call on the stack returns True without rubbing out its chalk. Those cells are exactly the path from start to goal.
Your solver in a maze it has never seen.
Same code, a bigger maze. Press Run. AI planners search like this too: depth first, backing up at dead ends.
Previous lesson: Generate Everything: Subsets and Orders · Next lesson: Sudoku Solver · Part of the course: Recursion: Functions That Call Themselves
Lessons are interactive and need JavaScript. Turn it on to play them.
