< Back to index
Tutorial 52026-08-13
Maze Search Lab
Three-hour Python session · BFS and DFS · one algorithm, one line of difference, animated in your terminal
Mission
Finish line: A maze that draws itself in the terminal while YOUR search code walks through it — cell by cell, in colour — and then draws the path it found.
Teacher provides
The maze, 24-bit colours, the animated screen, the side-by-side race, and the build checks.
Student builds
Six small functions. Together they are the entire search algorithm — nothing is hidden.
Not a project
This is one algorithm, studied closely. No game loop, no save files, no class.
Three-Hour Route
00:00-00:20
Part 1 - What a graph is
Nodes, edges, neighbours. Draw the seven-node graph on paper and read it out loud.
00:20-00:45
Part 2 - Stack
A pile of plates. Last in, first out. Three drills, all on paper first.
00:45-01:10
Part 3 - Queue
A line at a shop. First in, first out. Same appends as the stack, opposite answers.
01:10-01:25
Part 4 - Search a graph by hand
Warm-Up 8 on paper, twice: once with pop(0), once with pop(). They have now invented BFS and DFS.
01:25-01:35
Break
Leave the two paper answers side by side on the desk.
01:35-01:50
Part 5 - The same idea on a maze
Play the BFS and DFS animations on this page. A maze IS a graph: every open cell is a node.
01:50-02:20
TODO 1-3: read the map
Three tiny helpers that turn a grid into neighbours. Run the checkpoint after each.
02:20-02:45
TODO 4-5: the search
take_next is the stack-or-queue choice they already made on paper.
02:45-03:00
TODO 6, run it, change one line
Rebuild the path, watch the terminal animate, then flip pop(0) to pop().
Part 1 — What A Graph Is
One sentence: A graph is a set of places, plus the connections between them. Today every connection works in both directions and every step costs the same.
unweighted · undirected
What a graph is
nodes = ["A", "B", "C", "D", "E", "F", "G"]
1/6
Seven places
A graph starts as a set of places. We call each one a node. Nothing else is decided yet.
node
One place. A circle in the picture.
edge
One connection. A line. Undirected, so it works both ways.
neighbours
The nodes one edge away. This is the only question we ever ask a graph.
Practice
Warm-Up 15 min
Read the graph
This is the same graph you just watched. Work out each line yourself first, then check it against the sample output.
python
graph = { "A": ["B", "D"], "B": ["A", "C", "E"], "C": ["B", "F"], "D": ["A", "E"], "E": ["B", "D", "G"], "F": ["C"], "G": ["E"],}print(graph["E"])print(len(graph["F"]))print("C" in graph["B"])print("C" in graph["E"])Sample output
['B', 'D', 'G'] 1 True False
This is exactly what the finished program prints. Match it line for line.
Hint 1
graph["E"] is a list, so printing it shows square brackets.
Hint 2
"C" in graph["B"] searches inside B's neighbour list, not the whole graph.
Warm-Up 26 min
Are these two linked?
Return True when there is an edge straight between the two nodes. A missing node must return False, not crash.
python
graph = { "A": ["B"], "B": ["A", "C"], "C": ["B"],}def are_linked(graph, one, other): # TODO passprint(are_linked(graph, "A", "B"))print(are_linked(graph, "B", "A"))print(are_linked(graph, "A", "C"))print(are_linked(graph, "A", "Z"))Sample output
True True False False
This is exactly what the finished program prints. Match it line for line.
Hint 1
Guard first: if one is not a key of graph, return False.
Hint 2
A and C are linked through B, but that is a ROUTE, not an edge. Only edges count here.
Part 2 — Stack
One sentence: A stack is a pile of plates. You add on top, and you take from the top. The last thing in is the first thing out.
LIFO — last in, first out
Stack — a pile of plates
plates = []
top — push and pop happen here
(empty)
bottom — never touched
came out—
1/8
plates = []
An empty stack. We will use a plain Python list.
In Python you do not need a new type. A plain list is already a stack: append() puts one on top, pop() takes the top one off.
Practice
Warm-Up 35 min
Trace a stack
Say out loud which item is on top before every pop. Then check your four lines against the sample.
python
stack = []stack.append("A")stack.append("B")stack.append("C")print(stack.pop())print(stack.pop())stack.append("D")print(stack)print(stack.pop())Sample output
C B ['A', 'D'] D
This is exactly what the finished program prints. Match it line for line.
Hint 1
append() always adds to the end. pop() always removes from the end.
Hint 2
A went in first and is still sitting at the bottom, untouched.
Warm-Up 46 min
Reverse a word with a stack
Push every character, then pop them all back out. The stack does the reversing for you.
python
def reverse(text): # TODO: push every character, then pop them all passprint(reverse("maze"))print(reverse("bfs"))Sample output
ezam sfb
This is exactly what the finished program prints. Match it line for line.
Hint 1
First loop: push every character. Second loop: pop until the stack is empty.
Hint 2
The last character pushed is the first one popped, which is exactly reversal.
Warm-Up 56 min
Undo is a stack
Every editor's undo button is this. Work out all five lines, then check them.
python
history = []def do(history, action): history.append(action)def undo(history): if len(history) == 0: return "nothing to undo" return history.pop()do(history, "draw")do(history, "erase")do(history, "draw")print(undo(history))print(undo(history))print(history)print(undo(history))print(undo(history))Sample output
draw erase ['draw'] draw nothing to undo
This is exactly what the finished program prints. Match it line for line.
Hint 1
Undo always removes the most recent action, never the oldest one.
Hint 2
The guard matters: popping an empty list would crash.
Part 3 — Queue
One sentence: A queue is a line at a shop. You join at the back, and you are served from the front. The first thing in is the first thing out.
FIFO — first in, first out
Queue — a line at a shop
line = []
front — leaves hereback — joins here
(empty)
came out—
1/8
line = []
An empty queue. Same Python list, different rule.
Again a plain list is enough: append() joins the back, pop(0) serves the front. Note carefully — append() is identical for both. Only the taking is different.
| Stack | Queue | |
|---|---|---|
| put one in | things.append(x) | things.append(x) |
| take one out | things.pop() | things.pop(0) |
| who leaves first | the newest | the oldest |
| short name | LIFO | FIFO |
Practice
Warm-Up 65 min
Trace a queue
Exactly the same appends as Warm-Up 3. Only the taking changed. Work out the four lines, then put them next to Warm-Up 3's.
python
queue = []queue.append("A")queue.append("B")queue.append("C")print(queue.pop(0))print(queue.pop(0))queue.append("D")print(queue)print(queue.pop(0))Sample output
A B ['C', 'D'] C
This is exactly what the finished program prints. Match it line for line.
Hint 1
pop(0) removes position 0, and everything behind it shifts forward.
Hint 2
Compare with Warm-Up 3: same appends, opposite answers.
Warm-Up 76 min
One input, two rules
This is the whole tutorial in one function. Work out both lines before you look at the sample.
python
def take_all(items, mode): waiting = [] for item in items: waiting.append(item) out = [] while len(waiting) > 0: if mode == "queue": out.append(waiting.pop(0)) else: out.append(waiting.pop()) return outprint(take_all([1, 2, 3, 4], "queue"))print(take_all([1, 2, 3, 4], "stack"))Sample output
[1, 2, 3, 4] [4, 3, 2, 1]
This is exactly what the finished program prints. Match it line for line.
Hint 1
Everything above the while loop is identical for both modes.
Hint 2
A queue hands things back in the order they arrived. A stack hands them back backwards.
Warm-Up 88 min
Search a graph by hand
This IS the algorithm, on a four-node graph. Work it out on paper first, then change pop(0) to pop() and work it out again.
python
links = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}queue = ["A"]seen = ["A"]order = []while len(queue) > 0: current = queue.pop(0) order.append(current) for nxt in links[current]: if nxt not in seen: seen.append(nxt) queue.append(nxt)print(order)Sample output
['A', 'B', 'C', 'D']
This is exactly what the finished program prints. Match it line for line.
Hint 1
Keep two lists on paper: what is waiting, and what has been seen.
Hint 2
Without the 'seen' check, D would be added twice — once from B and once from C.
Part 4 — Searching A Graph
One sentence: Keep a to-do list of places you know about but have not visited. Take one out, look at its neighbours, add the new ones. That is the whole algorithm — and Warm-Up 8 already had you run it by hand.
python
# The frontier is a to-do list: cells we know about# but have not explored yet.frontier = [start]# came_from does two jobs at once:# 1. it remembers which cell we arrived FROM# 2. being a key already means "we have seen this cell"came_from = {start: None}while len(frontier) > 0: current = take_next(frontier, mode) # <-- the only difference for step in neighbors(grid, current): if step not in came_from: # never seen before came_from[step] = current # remember how we got here frontier.append(step) # add it to the to-do listfrontier
The to-do list. Use it as a queue and you get BFS. Use it as a stack and you get DFS.
came_from
A dict doing two jobs: it remembers the route, and its keys are the 'already seen' list.
A maze is a graph too. Every open cell is a node, and two open cells that touch side by side are joined by an edge. Nothing about the algorithm changes.
Part 5 — BFS On The Maze
The frontier is a QUEUE here. Press play, then pause anywhere and say out loud which cell will be taken next. The magenta cell is the one being explored right now.
queue — oldest first
Breadth-First Search
S
G
frontier = [start]came_from = {start: None} while len(frontier) > 0: current = take_next(frontier, mode) if current == goal: return came_from for step in neighbors(grid, current): if step not in came_from: came_from[step] = current frontier.append(step) path = rebuild_path(came_from, goal)
explored
1
waiting
0
path
—
frontier
next taken from the LEFT
(empty)
Take the cell that has waited longest — the front of the queue.
startgoalbeing exploredwaiting in frontierreached (darker = farther)final path
Notice the shape: the explored area grows as even rings around the start. Every cell in a ring is the same number of steps away. That is exactly why the first time BFS touches the goal, it has already used the fewest possible steps.
Part 6 — DFS On The Maze
Same maze, same start, same goal. The frontier is a STACK now, and that is the only change. Watch the magenta cell commit to one direction and only jump back when it runs out of room.
stack — newest first
Depth-First Search
S
G
frontier = [start]came_from = {start: None} while len(frontier) > 0: current = take_next(frontier, mode) if current == goal: return came_from for step in neighbors(grid, current): if step not in came_from: came_from[step] = current frontier.append(step) path = rebuild_path(came_from, goal)
explored
1
waiting
0
path
—
frontier
next taken from the RIGHT
(empty)
Take the cell added most recently — the top of the stack.
startgoalbeing exploredwaiting in frontierreached (darker = farther)final path
DFS touches fewer cells, and that can look like an advantage. But look at the path length when it finishes. It reached the goal by the first route it stumbled into, not the best one.
Side By Side
Both algorithms, one maze, running in step. This is the picture to remember.
same maze, same start, same goal
BFS vs DFS, side by side
BFS · queue
S
G
explored 1
DFS · stack
S
G
explored 1
The maze has 94 open cells. BFS fans out evenly and always finds the shortest route. DFS commits to one direction and only turns back when it runs out of room.
The One Line
Everything you just watched comes from this. Nothing else in the program is different.
python
def take_next(frontier, mode): if mode == "bfs": return frontier.pop(0) # take the FRONT -> a queue -> BFS return frontier.pop() # take the BACK -> a stack -> DFS| BFS | DFS | |
|---|---|---|
| takes from | the front — pop(0) | the back — pop() |
| the list acts like | a queue, like a line at a shop | a stack, like a pile of plates |
| shape of the search | rings growing outward | one long snake |
| path it finds | always the shortest | some path, often much longer |
| cells it explores | more | fewer |
Before You Code
Two last drills. Both appear inside the maze program almost word for word.
Warm-Up 96 min
A pair can be a dict key
A place on a map is two numbers, so we keep them together as a pair. Work out all five lines, then check.
python
cell = (3, 5)row, col = cellprint(row)print(col)seen = {}seen[(3, 5)] = "visited"seen[(3, 6)] = "visited"print((3, 5) in seen)print((9, 9) in seen)print(len(seen))Sample output
3 5 True False 2
This is exactly what the finished program prints. Match it line for line.
Hint 1
row, col = cell unpacks the pair into two separate names.
Hint 2
(3, 5) and (3, 6) are two different keys, so the dict holds two pairs.
Warm-Up 107 min
Walk backwards through a dict
Searching tells you where each place came FROM. Turn that into a route you can walk forwards.
python
came_from = { "hall": None, "library": "hall", "attic": "library",}def walk_back(came_from, end): # TODO passprint(walk_back(came_from, "attic"))Sample output
['hall', 'library', 'attic']
This is exactly what the finished program prints. Match it line for line.
Hint 1
Start at end and keep asking came_from where you arrived from.
Hint 2
Stop when the answer is None. Then reverse the list.
In The Terminal
This is a real frame from the finished program, captured mid-search. In a real terminal every block is a solid 24-bit colour, and the whole maze redraws about twenty times a second.
terminal
+----------------------------------------------------------------------------+| BREADTH-FIRST SEARCH || queue - take the cell that waited longest |+----------------------------------------------------------------------------+| || ################################ || ##S + + + + + @ . . . . . . . ## || ##+ + + + ############. . . . ## || ##+ + + + ##. . . . ##. . . . ## || ##+ + + + ##. ####. ##. . . . ## || ##+ + + ? ##. ##. . ##. . . . ## || ##+ + ? . ######. ####. . . . ## || ##+ ? . . . . . . . . . . . . ## || ##? ########################. ## || ##. . . . . . . . . . . . . G ## || ################################ || |+----------------------------------------------------------------------------+| BFS step 25/91 frontier 4 reached 29/94 path - || frontier [ (8,1) (7,2) (6,3) (5,4) ] || ^ BFS takes this end (oldest) |+----------------------------------------------------------------------------+| S start G goal ? in the frontier @ being explored || + already reached o final path ## wall |+----------------------------------------------------------------------------+The picture above is the plain fallback, used when the output is captured or piped. Run it in a real terminal to get the colours: '?' becomes amber, '+' becomes blue, '@' becomes magenta, 'o' becomes green.
TODO Contract
Six functions. Read the card before the code, finish one at a time, and run its checkpoint before moving on.
TODO 1Phase 1 - Reading the map
in_bounds
Purpose
Answer one question: is this cell still on the map?
Input
grid: list[str], cell: a pair (row, col)
Output / Return
True when the cell is inside the grid, otherwise False.
State change
Nothing.
Checkpoint
python
print(in_bounds(MAZE, (0, 0))) # Trueprint(in_bounds(MAZE, (-1, 0))) # Falseprint(in_bounds(MAZE, (11, 0))) # FalseTODO 2Phase 1 - Reading the map
is_open
Purpose
Answer one question: can I stand here, or is it a wall?
Input
grid, cell: a pair already known to be inside the grid
Output / Return
True for walkable floor, False for '#'.
State change
Nothing. 'S' and 'G' are walkable too.
Checkpoint
python
print(is_open(MAZE, (1, 1))) # True (the S cell)print(is_open(MAZE, (0, 0))) # False (a wall)TODO 3Phase 1 - Reading the map
neighbors
Purpose
List the cells you could step to from here.
Input
grid, cell: a pair (row, col)
Output / Return
A list of the walkable cells up, down, left and right, in DIRECTIONS order.
State change
Nothing. Reuse in_bounds and is_open instead of rewriting them.
Checkpoint
python
print(neighbors(MAZE, (2, 2)))# [(1, 2), (3, 2), (2, 1), (2, 3)]print(neighbors(MAZE, (1, 1)))# [(2, 1), (1, 2)]TODO 4Phase 2 - The search
take_next
Purpose
This is the whole difference between BFS and DFS. Two lines.
Input
frontier: list of waiting cells, mode: "bfs" or "dfs"
Output / Return
One cell, removed from frontier.
State change
"bfs" takes the cell that waited LONGEST. "dfs" takes the NEWEST one.
Checkpoint
python
waiting = [10, 20, 30]print(take_next(waiting, "bfs"), waiting) # 10 [20, 30]waiting = [10, 20, 30]print(take_next(waiting, "dfs"), waiting) # 30 [10, 20]TODO 5Phase 2 - The search
search (the expand step)
Purpose
Reach every new neighbour once, and write down where it came from.
Input
current: the cell just taken out of frontier
Output / Return
No return value here.
State change
For each neighbour that is NOT already a key of came_from: store came_from[step] = current, then append step to frontier.
Checkpoint
python
came_from, order = search(MAZE, START, GOAL, "bfs")print(len(order)) # 91 cells taken out of frontierprint(came_from[START]) # None the start came from nowhereprint(came_from[GOAL]) # (9, 13) the cell just before GTODO 6Phase 3 - The path
rebuild_path
Purpose
Turn the came_from dict into an actual route you can walk.
Input
came_from: the dict search() returned, goal: a pair
Output / Return
The list of cells from start to goal, in walking order. [] when the goal was never reached.
State change
Nothing. Walk backwards from goal until came_from gives None, then reverse.
Checkpoint
python
came_from, order = search(MAZE, START, GOAL, "bfs")print(len(rebuild_path(came_from, GOAL))) # 22print(rebuild_path(came_from, GOAL)[:3]) # [(1, 1), (2, 1), (3, 1)]print(rebuild_path({START: None}, GOAL)) # []Student Work Area
Only edit this part: All six TODOs live here, and this is the whole algorithm. You never need to read the drawing code to finish them.
student_work.py
python
# ================================================================# A cell is a pair of numbers: (row, col).# A pair can be a dict key, exactly like a string can.# ================================================================def in_bounds(grid, cell): # TODO 1 # Input: grid, a list of strings; cell, a pair (row, col) # Return: True when the cell is still inside the grid, otherwise False # Change: nothing return Falsedef is_open(grid, cell): # TODO 2 # Input: grid; cell, a pair (row, col) that is already inside the grid # Return: True when you can walk on it, False when it is a wall "#" # Change: nothing return Falsedef neighbors(grid, cell): # TODO 3 # Input: grid; cell, a pair (row, col) # Return: a list of the walkable cells directly up, down, left and right # Keep them in DIRECTIONS order. # Change: nothing return []# ================================================================# THE ONE LINE THAT SEPARATES BFS FROM DFS# ================================================================def take_next(frontier, mode): # TODO 4 # Input: frontier, a list of cells waiting to be explored; mode, "bfs" or "dfs" # Return: one cell, REMOVED from frontier # "bfs" -> take the cell that has been waiting the LONGEST (a queue) # "dfs" -> take the cell that was added MOST RECENTLY (a stack) # Change: frontier loses exactly one cell return Nonedef search(grid, start, goal, mode, film=None): frontier = [start] came_from = {start: None} order = [] while len(frontier) > 0: current = take_next(frontier, mode) order.append(current) # Provided: one snapshot per step, so the animation can replay your search. if film is not None: film.append((current, frontier.copy(), came_from.copy())) if current == goal: return came_from, order # TODO 5 # For every neighbour of current: # if it is NOT already a key of came_from, # remember that we reached it FROM current, # and add it to the end of frontier. # Being a key of came_from is how we know a cell was already reached. return came_from, orderdef rebuild_path(came_from, goal): # TODO 6 # Input: came_from, the dict search() returned; goal, a pair (row, col) # Return: the list of cells from start to goal, in walking order # Return [] when goal was never reached. # Change: nothing # # came_from[goal] is the cell just before goal. # came_from[start] is None, which is where you stop. return []Project Template
Copy this whole file once so the maze can run. During class, work in the Student Work Area above and search by TODO number.
maze_search.py
python
import reimport sysfrom time import sleepESC = chr(27) + "["RESET = f"{ESC}0m"USE_COLOR = sys.stdout.isatty()ANIMATE = sys.stdout.isatty()ANSI_RE = re.compile(re.escape(ESC) + r"[0-9;]*m")# The maze. '#' is a wall, '.' is open floor, 'S' is the start, 'G' is the goal.MAZE = [ "################", "#S.............#", "#....######....#", "#....#....#....#", "#....#.##.#....#", "#....#.#..#....#", "#....###.##....#", "#..............#", "#.############.#", "#.............G#", "################",]# up, down, left, rightDIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]# 24-bit colours: (background, foreground, two characters of text)PALETTE = { "wall": ((44, 48, 66), (44, 48, 66), " "), "empty": ((18, 20, 30), (70, 76, 98), "· "), "visited": ((32, 68, 128), (140, 190, 255), " "), "frontier": ((236, 178, 46), (60, 40, 0), " "), "current": ((232, 74, 196), (255, 255, 255), " "), "path": ((58, 222, 138), (10, 40, 24), " "), "start": ((72, 226, 255), (8, 24, 34), "S "), "goal": ((255, 96, 96), (40, 8, 8), "G "),}PLAIN = { "wall": "##", "empty": ". ", "visited": "+ ", "frontier": "? ", "current": "@ ", "path": "o ", "start": "S ", "goal": "G ",}def paint_cell(kind): if not USE_COLOR: return PLAIN[kind] background, foreground, text = PALETTE[kind] return ( f"{ESC}48;2;{background[0]};{background[1]};{background[2]}m" f"{ESC}38;2;{foreground[0]};{foreground[1]};{foreground[2]}m" f"{text}{RESET}" )def rgb(text, red, green, blue, bold=False): if not USE_COLOR: return str(text) weight = "1;" if bold else "" return f"{ESC}{weight}38;2;{red};{green};{blue}m{text}{RESET}"def dim(text): if not USE_COLOR: return str(text) return f"{ESC}2m{text}{RESET}"def gradient_text(text, start=(90, 220, 255), end=(200, 110, 255)): if not USE_COLOR or len(text) <= 1: return str(text) out = "" steps = len(text) - 1 for index, character in enumerate(text): ratio = index / steps red = round(start[0] + (end[0] - start[0]) * ratio) green = round(start[1] + (end[1] - start[1]) * ratio) blue = round(start[2] + (end[2] - start[2]) * ratio) out += rgb(character, red, green, blue) return outdef visible_len(text): return len(ANSI_RE.sub("", str(text)))def pad_visible(text, width): return str(text) + " " * max(0, width - visible_len(text))def center_visible(text, width): spaces = max(0, width - visible_len(text)) left = spaces // 2 return " " * left + str(text) + " " * (spaces - left)def clear_screen(): if sys.stdout.isatty(): print(f"{ESC}2J{ESC}H", end="")def hide_cursor(): if sys.stdout.isatty(): print(f"{ESC}?25l", end="")def show_cursor(): if sys.stdout.isatty(): print(f"{ESC}?25h", end="")def find_cell(grid, letter): for row in range(len(grid)): for col in range(len(grid[row])): if grid[row][col] == letter: return (row, col) return NoneSTART = find_cell(MAZE, "S")GOAL = find_cell(MAZE, "G")def open_cell_count(grid): total = 0 for line in grid: for character in line: if character != "#": total += 1 return totalTOTAL_OPEN = open_cell_count(MAZE)def grid_lines(grid, visited, frontier, current, path): """Turn one moment of the search into a list of printable rows.""" frontier_set = {} for cell in frontier: frontier_set[cell] = True path_set = {} for cell in path: path_set[cell] = True lines = [] for row in range(len(grid)): line = "" for col in range(len(grid[row])): cell = (row, col) character = grid[row][col] if character == "#": kind = "wall" elif cell == START: kind = "start" elif cell == GOAL: kind = "goal" elif cell == current: kind = "current" elif cell in path_set: kind = "path" elif cell in frontier_set: kind = "frontier" elif cell in visited: kind = "visited" else: kind = "empty" line += paint_cell(kind) lines.append(line) return linesLEGEND = [ ("start", "start"), ("goal", "goal"), ("frontier", "in the frontier"), ("current", "being explored"), ("visited", "already reached"), ("path", "final path"), ("wall", "wall"),]def legend_line(): parts = [] for kind, label in LEGEND: parts.append(paint_cell(kind) + " " + dim(label)) return " ".join(parts)# ================================================================# A cell is a pair of numbers: (row, col).# A pair can be a dict key, exactly like a string can.# ================================================================def in_bounds(grid, cell): # TODO 1 # Input: grid, a list of strings; cell, a pair (row, col) # Return: True when the cell is still inside the grid, otherwise False # Change: nothing return Falsedef is_open(grid, cell): # TODO 2 # Input: grid; cell, a pair (row, col) that is already inside the grid # Return: True when you can walk on it, False when it is a wall "#" # Change: nothing return Falsedef neighbors(grid, cell): # TODO 3 # Input: grid; cell, a pair (row, col) # Return: a list of the walkable cells directly up, down, left and right # Keep them in DIRECTIONS order. # Change: nothing return []# ================================================================# THE ONE LINE THAT SEPARATES BFS FROM DFS# ================================================================def take_next(frontier, mode): # TODO 4 # Input: frontier, a list of cells waiting to be explored; mode, "bfs" or "dfs" # Return: one cell, REMOVED from frontier # "bfs" -> take the cell that has been waiting the LONGEST (a queue) # "dfs" -> take the cell that was added MOST RECENTLY (a stack) # Change: frontier loses exactly one cell return Nonedef search(grid, start, goal, mode, film=None): frontier = [start] came_from = {start: None} order = [] while len(frontier) > 0: current = take_next(frontier, mode) order.append(current) # Provided: one snapshot per step, so the animation can replay your search. if film is not None: film.append((current, frontier.copy(), came_from.copy())) if current == goal: return came_from, order # TODO 5 # For every neighbour of current: # if it is NOT already a key of came_from, # remember that we reached it FROM current, # and add it to the end of frontier. # Being a key of came_from is how we know a cell was already reached. return came_from, orderdef rebuild_path(came_from, goal): # TODO 6 # Input: came_from, the dict search() returned; goal, a pair (row, col) # Return: the list of cells from start to goal, in walking order # Return [] when goal was never reached. # Change: nothing # # came_from[goal] is the cell just before goal. # came_from[start] is None, which is where you stop. return []WIDTH = 78INSIDE = WIDTH - 4GRID_WIDTH = len(MAZE[0]) * 2MODE_TITLE = { "bfs": "BREADTH-FIRST SEARCH", "dfs": "DEPTH-FIRST SEARCH",}MODE_SUBTITLE = { "bfs": "queue - take the cell that waited longest", "dfs": "stack - take the cell added most recently",}def rule(left="+", right="+"): return left + "-" * (WIDTH - 2) + rightdef row(text): return "| " + pad_visible(text, INSIDE) + " |"def centered(text): return "| " + center_visible(text, INSIDE) + " |"def cell_label(cell): return f"({cell[0]},{cell[1]})"def frontier_strip(frontier, mode): """Two lines: the waiting list, and an arrow under the end we take from.""" if len(frontier) == 0: return ["frontier (empty)", ""] labels = [cell_label(cell) for cell in frontier] if len(labels) > 7: shown = labels[:3] + ["..."] + labels[-3:] else: shown = labels body = " ".join(shown) line = "frontier [ " + body + " ]" arrow_column = len("frontier [ ") if mode == "bfs": marker = " " * arrow_column + "^ BFS takes this end (oldest)" else: end_column = arrow_column + len(body) - len(shown[-1]) marker = " " * end_column + "^ DFS takes this end (newest)" return [line, dim(marker)]def stats_line(mode, step, total_steps, frontier_size, reached, path_length): parts = [ rgb(mode.upper(), 120, 220, 255, bold=True), f"step {step}/{total_steps}", f"frontier {frontier_size}", f"reached {reached}/{TOTAL_OPEN}", ] if path_length is None: parts.append(dim("path -")) else: parts.append(rgb(f"path {path_length}", 60, 230, 140, bold=True)) return " ".join(parts)def legend_lines(): first = [] for kind, label in LEGEND[:4]: first.append(paint_cell(kind) + " " + dim(label)) second = [] for kind, label in LEGEND[4:]: second.append(paint_cell(kind) + " " + dim(label)) return [" ".join(first), " ".join(second)]def draw_single(mode, visited, frontier, current, path, step, total_steps, path_length): clear_screen() lines = [ rule(), centered(gradient_text(MODE_TITLE[mode])), centered(dim(MODE_SUBTITLE[mode])), rule(), row(""), ] for grid_row in grid_lines(MAZE, visited, frontier, current, path): lines.append(centered(grid_row)) lines.append(row("")) lines.append(rule()) lines.append(row(stats_line(mode, step, total_steps, len(frontier), len(visited), path_length))) for strip in frontier_strip(frontier, mode): lines.append(row(strip)) lines.append(rule()) for legend in legend_lines(): lines.append(row(legend)) lines.append(rule()) print("\n".join(lines))def run_search(mode): film = [] came_from, order = search(MAZE, START, GOAL, mode, film) path = rebuild_path(came_from, GOAL) return film, order, pathdef animate(mode, delay=0.05): film, order, path = run_search(mode) total = len(film) hide_cursor() try: for index in range(total): current, frontier, came_from = film[index] draw_single(mode, came_from, frontier, current, [], index + 1, total, None) if ANIMATE: sleep(delay) # Walk the finished path back out, one cell at a time. current, frontier, came_from = film[-1] for grown in range(1, len(path) + 1): draw_single( mode, came_from, [], None, path[:grown], total, total, len(path) ) if ANIMATE: sleep(0.05) finally: show_cursor() return order, pathdef draw_race(bfs_state, dfs_state, step, done): clear_screen() gap = " " lines = [ rule(), centered(gradient_text("BFS vs DFS - same maze, same start, same goal")), rule(), row(""), ] left_title = center_visible(rgb("BFS (queue)", 120, 220, 255, bold=True), GRID_WIDTH) right_title = center_visible(rgb("DFS (stack)", 255, 170, 90, bold=True), GRID_WIDTH) lines.append(centered(left_title + gap + right_title)) lines.append(row("")) left_grid = grid_lines(MAZE, bfs_state["visited"], bfs_state["frontier"], bfs_state["current"], bfs_state["path"]) right_grid = grid_lines(MAZE, dfs_state["visited"], dfs_state["frontier"], dfs_state["current"], dfs_state["path"]) for index in range(len(left_grid)): lines.append(centered(left_grid[index] + gap + right_grid[index])) lines.append(row("")) left_stats = center_visible( f"reached {len(bfs_state['visited'])} frontier {len(bfs_state['frontier'])}", GRID_WIDTH, ) right_stats = center_visible( f"reached {len(dfs_state['visited'])} frontier {len(dfs_state['frontier'])}", GRID_WIDTH, ) lines.append(centered(left_stats + gap + right_stats)) if done: left_done = center_visible( rgb(f"path {len(bfs_state['path'])}", 60, 230, 140, bold=True), GRID_WIDTH ) right_done = center_visible( rgb(f"path {len(dfs_state['path'])}", 255, 140, 90, bold=True), GRID_WIDTH ) lines.append(centered(left_done + gap + right_done)) else: lines.append(centered(dim(f"step {step}"))) lines.append(rule()) for legend in legend_lines(): lines.append(row(legend)) lines.append(rule()) print("\n".join(lines))def race(delay=0.05): bfs_film, _, bfs_path = run_search("bfs") dfs_film, _, dfs_path = run_search("dfs") longest = max(len(bfs_film), len(dfs_film)) hide_cursor() try: for index in range(longest): states = {} for mode, film in (("bfs", bfs_film), ("dfs", dfs_film)): position = min(index, len(film) - 1) current, frontier, came_from = film[position] finished = index >= len(film) states[mode] = { "visited": came_from, "frontier": [] if finished else frontier, "current": None if finished else current, "path": [], } draw_race(states["bfs"], states["dfs"], index + 1, False) if ANIMATE: sleep(delay) longest_path = max(len(bfs_path), len(dfs_path)) for grown in range(1, longest_path + 1): states = {} for mode, film, path in (("bfs", bfs_film, bfs_path), ("dfs", dfs_film, dfs_path)): current, frontier, came_from = film[-1] states[mode] = { "visited": came_from, "frontier": [], "current": None, "path": path[:grown], } draw_race(states["bfs"], states["dfs"], longest, False) if ANIMATE: sleep(0.045) states = {} for mode, film, path in (("bfs", bfs_film, bfs_path), ("dfs", dfs_film, dfs_path)): current, frontier, came_from = film[-1] states[mode] = { "visited": came_from, "frontier": [], "current": None, "path": path, } draw_race(states["bfs"], states["dfs"], longest, True) finally: show_cursor()def compare_numbers(): clear_screen() rows = [] results = {} for mode in ("bfs", "dfs"): film, order, path = run_search(mode) came_from = film[-1][2] results[mode] = (len(came_from), len(order), len(path)) bfs_reached, bfs_steps, bfs_path = results["bfs"] dfs_reached, dfs_steps, dfs_path = results["dfs"] rows.append(rule()) rows.append(centered(gradient_text("THE NUMBERS"))) rows.append(rule()) rows.append(row("")) rows.append(row(f"{'':<30}{'BFS':>10}{'DFS':>10}")) rows.append(row(f"{'cells reached (yellow+blue)':<30}{bfs_reached:>10}{dfs_reached:>10}")) rows.append(row(f"{'cells fully explored (blue)':<30}{bfs_steps:>10}{dfs_steps:>10}")) rows.append(row(f"{'path length':<30}{bfs_path:>10}{dfs_path:>10}")) rows.append(row(f"{'open cells in the maze':<30}{TOTAL_OPEN:>10}{TOTAL_OPEN:>10}")) rows.append(row("")) rows.append(rule()) rows.append(row("BFS explored more cells, and found the SHORTEST path.")) rows.append(row(f"DFS explored fewer cells, but its path is {dfs_path - bfs_path} steps longer.")) rows.append(row("")) rows.append(row(dim("BFS is worth the extra work whenever 'shortest' matters."))) rows.append(rule()) print("\n".join(rows))def is_walk(path, start, goal): """A real path: starts at start, ends at goal, every step moves one cell.""" if len(path) == 0: return False if path[0] != start or path[-1] != goal: return False for index in range(1, len(path)): previous = path[index - 1] current = path[index] distance = abs(previous[0] - current[0]) + abs(previous[1] - current[1]) if distance != 1: return False return TrueTINY = [ "#####", "#S..#", "#.#.#", "#..G#", "#####",]def run_build_checks(): assert in_bounds(TINY, (0, 0)) is True, ( "TODO 1 failed: (0, 0) is inside a 5x5 grid." ) assert in_bounds(TINY, (-1, 0)) is False, ( "TODO 1 failed: a negative row is outside the grid." ) assert in_bounds(TINY, (5, 0)) is False, ( "TODO 1 failed: row 5 is past the last row of a 5-row grid." ) assert in_bounds(TINY, (0, 5)) is False, ( "TODO 1 failed: column 5 is past the last column." ) assert is_open(TINY, (1, 1)) is True, ( "TODO 2 failed: the start cell is walkable." ) assert is_open(TINY, (0, 0)) is False, ( "TODO 2 failed: '#' is a wall." ) assert is_open(TINY, (2, 2)) is False, ( "TODO 2 failed: (2, 2) is a wall in the small test maze." ) assert neighbors(TINY, (1, 1)) == [(2, 1), (1, 2)], ( "TODO 3 failed: from (1,1) only down and right are open, in DIRECTIONS order." ) assert neighbors(TINY, (2, 1)) == [(1, 1), (3, 1)], ( "TODO 3 failed: check that walls and the grid edge are both rejected." ) waiting = [10, 20, 30] assert take_next(waiting, "bfs") == 10 and waiting == [20, 30], ( "TODO 4 failed: bfs must remove and return the OLDEST cell." ) waiting = [10, 20, 30] assert take_next(waiting, "dfs") == 30 and waiting == [10, 20], ( "TODO 4 failed: dfs must remove and return the NEWEST cell." ) tiny_start = find_cell(TINY, "S") tiny_goal = find_cell(TINY, "G") for mode in ("bfs", "dfs"): came_from, order = search(TINY, tiny_start, tiny_goal, mode) assert tiny_goal in came_from, ( f"TODO 5 failed: {mode} never reached the goal in the small test maze." ) assert came_from[tiny_start] is None, ( "TODO 5 failed: do not overwrite came_from[start], it must stay None." ) assert order[0] == tiny_start, ( "TODO 5 failed: the search must explore the start cell first." ) path = rebuild_path(came_from, tiny_goal) assert is_walk(path, tiny_start, tiny_goal), ( f"TODO 6 failed: the {mode} path must start at S, end at G, and step one cell at a time." ) came_from, order = search(TINY, tiny_start, tiny_goal, "bfs") assert len(rebuild_path(came_from, tiny_goal)) == 5, ( "TODO 5 or 6 failed: the shortest route in the small test maze is 5 cells long." ) assert rebuild_path({tiny_start: None}, tiny_goal) == [], ( "TODO 6 failed: return [] when the goal was never reached." ) bfs_came, _ = search(MAZE, START, GOAL, "bfs") dfs_came, _ = search(MAZE, START, GOAL, "dfs") bfs_path = rebuild_path(bfs_came, GOAL) dfs_path = rebuild_path(dfs_came, GOAL) assert is_walk(bfs_path, START, GOAL), "TODO 6 failed: the BFS path is not a real walk." assert is_walk(dfs_path, START, GOAL), "TODO 6 failed: the DFS path is not a real walk." assert len(bfs_path) <= len(dfs_path), ( "TODO 4 failed: BFS should never find a longer path than DFS. Check the pop rule." )MENU = [ "[1] Watch BFS find the path", "[2] Watch DFS find the path", "[3] Race them side by side", "[4] Compare the numbers", "[q] Quit",]def show_menu(): clear_screen() lines = [ rule(), centered(gradient_text("MAZE SEARCH LAB")), centered(dim("one maze, one algorithm, one line of difference")), rule(), row(""), ] for grid_row in grid_lines(MAZE, {}, [], None, []): lines.append(centered(grid_row)) lines.append(row("")) lines.append(rule()) for entry in MENU: lines.append(row(entry)) lines.append(rule()) print("\n".join(lines))def wait_for_enter(): try: input("\nPress Enter to return to the menu: ") except EOFError: passdef main(): try: run_build_checks() except (AssertionError, AttributeError, TypeError, KeyError, IndexError, ValueError) as error: detail = str(error) if str(error) else "A required result was incorrect." print(rule()) print(centered("BUILD CHECK FAILED")) print(rule()) print(row("Finish TODO 1-6 before the maze will open.")) print(row("")) print(row(detail)) print(row("")) print(row("Fix one TODO, then run the file again.")) print(rule()) return while True: show_menu() try: choice = input("Choose: ").strip().lower() except EOFError: return if choice == "1": animate("bfs") wait_for_enter() elif choice == "2": animate("dfs") wait_for_enter() elif choice == "3": race() wait_for_enter() elif choice == "4": compare_numbers() wait_for_enter() elif choice in ("q", "quit", "exit"): show_cursor() returnif __name__ == "__main__": main()Build rule: The maze only opens after all six build checks pass. One of them fails if BFS ever finds a longer path than DFS — that is almost always a wrong pop rule.
Run Checklist
Start it
bash
python3 maze_search.py# The build check runs first. The maze only opens after TODO 1-6 pass.# [1] Watch BFS find the path# [2] Watch DFS find the path# [3] Race them side by side# [4] Compare the numbers# [q] Quit01Choose [1]. The magenta cell should move outward in rings, never jumping far away.
02Watch the frontier line at the bottom. The arrow must point at the end BFS takes from.
03Let it finish. The green path must connect S to G with no gaps.
04Choose [2]. The magenta cell should dive in one direction, then jump back when stuck.
05Choose [3] and let both finish. The BFS path is visibly shorter.
06Choose [4]. Read the two path lengths out loud: 22 and 54.
07Break it on purpose: change pop(0) to pop() inside take_next and rerun [1].
08Put it back. A build check should complain if BFS ever finds a longer path than DFS.
Optional Upgrades
Choose exactly one. Before writing any code, name the single function it changes.
Redraw the maze
Edit MAZE. Keep the outer wall, keep one S and one G. Nothing else has to change.
Allow diagonal moves
Add four more pairs to DIRECTIONS. Only neighbors changes. Watch the wave turn into a square.
Count the distance
Add a steps dict alongside came_from: steps[step] = steps[current] + 1.
Stop early
Return the moment a neighbour IS the goal, instead of waiting for it to be taken out.
Teacher Checkpoints
After TODO 3: ask why neighbors calls in_bounds BEFORE is_open. Reversing them crashes on the edge.
After TODO 4: cover the screen and ask which word means pop(0) — queue or stack.
After TODO 5: ask what would happen without the "if step not in came_from" line. The frontier would never stop growing.
After TODO 6: ask why the list has to be reversed at the end.
At the end: ask the student to change ONE line to turn BFS into DFS, without looking at the notes.