Tracing Recursive Backtracking
Let’s trace a maze where the first direction the search tries is not the one that reaches the exit.
0 1 2 3
┌───┬───┬───┬───┐
0 │ S │ │ │ █ │
├───┼───┼───┼───┤
1 │ │ █ │ │ █ │
├───┼───┼───┼───┤
2 │ │ █ │ █ │ │
├───┼───┼───┼───┤
3 │ │ │ │ E │
└───┴───┴───┴───┘
Each step below shows the maze grid next to the call stack, so you can see the path and the calls change together. This is the initial call to search:
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(0,0) waiting for a direction to try ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
Recall that the recursive search tries directions in this order: right, down, left, up. Starting at (0, 0), the search tries right, follows the open cells across the top row, then turns down to (1, 2). By the time it reaches (1, 2), the stack has grown one frame per cell it stepped through:
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │ │ │ █ │ 0 │ x │ x │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │[ ]│ █ │ 1 │ │ │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ │ █ │ █ │ │ 2 │ │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
3 │ │ │ │ E │ 3 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(1,2) waiting for a direction to try ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┌─────────────────────────────────────────────┐
│ search(0,2) waiting for search(1,2) │
├─────────────────────────────────────────────┤
│ search(0,1) waiting for search(0,2) │
├─────────────────────────────────────────────┤
│ search(0,0) waiting for search(0,1) │
└─────────────────────────────────────────────┘
From (1, 2), every direction fails:
- right is a wall
- down is a wall
- left is a wall
- up has already been visited
So the call on (1, 2) returns false. That sends control back to the call on (0, 2), whose remaining directions also fail. As each frame runs out of directions, it returns false and pops off the stack:
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │ │[ ]│ █ │ 0 │ x │ x │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ │ █ │ 1 │ │ │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ │ █ │ █ │ │ 2 │ │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
3 │ │ │ │ E │ 3 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(0,2) waiting for search(1,2) ┃ ◀── receives false
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┌──────────────────────────────────────┐
│ search(0,1) waiting for search(0,2) │
├──────────────────────────────────────┤
│ search(0,0) waiting for search(0,1) │
└──────────────────────────────────────┘
The cells of the right branch stay marked in visited, so the search will not enter them again. The false is passed back up the stack: (0, 1) returns false, and the search backtracks to the call on (0, 0). The first direction from the start failed, so the call on (0, 0) is ready to try its next direction: down.
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │[S]│ │ │ █ │ 0 │ x │ x │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ │ █ │ 1 │ │ │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ │ █ │ █ │ │ 2 │ │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
3 │ │ │ │ E │ 3 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(0,0) waiting for search(0,1) ┃ ◀── receives false
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
Going down, the search moves down the left column and then right along the bottom row toward the exit. The stack grows by one frame per cell again:
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │ │ │ █ │ 0 │ x │ x │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ │ █ │ 1 │ x │ │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ │ █ │ █ │ │ 2 │ x │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
3 │ │ │[ ]│ E │ 3 │ x │ x │ x │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(3,2) waiting for a direction to try ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┌─────────────────────────────────────────────┐
│ search(3,1) waiting for search(3,2) │
├─────────────────────────────────────────────┤
│ search(3,0) waiting for search(3,1) │
├─────────────────────────────────────────────┤
│ search(2,0) waiting for search(3,0) │
├─────────────────────────────────────────────┤
│ search(1,0) waiting for search(2,0) │
├─────────────────────────────────────────────┤
│ search(0,0) waiting for search(1,0) │
└─────────────────────────────────────────────┘
One more step right reaches the exit. The call on (3, 3) returns true. The frames on the stack are the path from the start to the exit:
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │ │ │ █ │ 0 │ x │ x │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ │ █ │ 1 │ x │ │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ │ █ │ █ │ │ 2 │ x │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
3 │ │ │ │[E]│ 3 │ x │ x │ x │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ search(3,3) return true (reached the exit) ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┌──────────────────────────────────────────────┐
│ search(3,2) waiting for search(3,3) │
├──────────────────────────────────────────────┤
│ search(3,1) waiting for search(3,2) │
├──────────────────────────────────────────────┤
│ search(3,0) waiting for search(3,1) │
├──────────────────────────────────────────────┤
│ search(2,0) waiting for search(3,0) │
├──────────────────────────────────────────────┤
│ search(1,0) waiting for search(2,0) │
├──────────────────────────────────────────────┤
│ search(0,0) waiting for search(1,0) │
└──────────────────────────────────────────────┘
When the call on the exit returns true, that true is passed back through the calls all the way back to the original call.
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │ │ │ █ │ 0 │ x │ x │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ │ █ │ 1 │ x │ │ x │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ │ █ │ █ │ │ 2 │ x │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
3 │ │ │ │ E │ 3 │ x │ x │ x │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
(empty — all calls have returned)