lesson 3.14.6 solving mazes
An introduction to pathfinding algorithms.
Have you ever wondered how mapping apps instantly calculate the fastest route to your destination, or how video game enemies know exactly how to chase you through a complex level? They certainly don't just guess! Software Developers and Systems Architects use powerful search algorithms to navigate digital worlds. Today, we are stepping into the shoes of a routing engineer to solve the ultimate puzzle: escaping a maze. We will start by investigating what happens when we just guess (a "random walk") before discovering how the professionals do it systematically. Let's get routing!
Learning Outcomes
The Building Blocks (Factual Knowledge)
The Connections and Theories (Conceptual Knowledge)
The Skills and Methods (Procedural Outcomes)
Recall that algorithms require specific, step-by-step instructions to navigate spatial problems like mazes.
Describe the core difference between a random walk and a systematic search algorithm.
The Connections and Theories (Conceptual Knowledge)
Analyse why a random walk is an inefficient and unreliable method for finding a guaranteed route.
Evaluate the Depth-First Search (DFS) strategy, focusing on its use of memory and backtracking to explore possible paths.
The Skills and Methods (Procedural Outcomes)
Apply the rules of a Depth-First Search algorithm to successfully trace a route out of a provided maze.
Create a logical comparison between basic search strategies and the advanced algorithms used in modern mapping applications.
Digital Skill Focus: Develop your information literacy by using search engines effectively to research how modern navigation systems process and handle complex routing data.
The Problem with Guessing
Before we can build a highly efficient routing app like Google Maps, we need to understand the fundamental challenge of navigating a network or a maze. Imagine being dropped into the centre of a massive corn maze with no map and no memory of where you have just walked. If you reach a junction and just flip a coin to decide whether to go left or right, you are performing a Random Walk Algorithm.
While a random walk is very easy to program (because the computer doesn't need to remember anything), it is incredibly inefficient. You might find the exit by pure luck in two minutes, or you might walk in circles until the corn rots!
Task 1 The Confused Little Turtle (Random Walk)
Let's see what happens when a computer tries to find its way out of a space using pure guesswork! You are going to experiment with a small Python script that uses the Turtle graphics library to perform a "random walk".
1
Get Organised!
Open up your Python IDE, Thonny.
If it's the first time you've used Thonny today, you will be greeted with a blank script. Otherwise, make sure you create a new one.
Organise your workspace.
2
Construct the random walk
A stage at a time, read the explanation then copy and paste the code snippet into Thonny but DON'T run it yet...
1
First, let's import some useful libraries
import turtle
import random
2
Spin up the Turtle and make him fly!
t = turtle.Turtle()
t.speed(0)
3
Tell him which ways he is allowed to turn
directions = [0, 90, 180, 270]
4
Now, make him take 100 steps into oblivion.
for _ in range(100):
t.setheading(random.choice(directions))
t.forward(20)
5
Finally, put him to sleep
t.hideturtle()
turtle.done()
3
Predict
Before you press run, discuss with your partner: What pattern do you expect the turtle to draw? Will it draw a straight line, a circle, or a messy scribble?
4
Run & Investigate
Run the script. Watch the turtle. Was your prediction correct? Look closely at the code. Can you find the line that makes the turtle choose a completely random direction?
5
Modify
Change the loop from
range(100)range(500)6
Faster workers...
Click the carefully crafted AI prompt below to read about the ways in which real satellite navigation systems handle routefinding.
What does it tell you about the random walk algorithm?
Act as a supportive, expert computer science teacher. Generate a short explanation (30 words or less) which explains why satellite navigation systems don't use a random-walk algorithm. Generate a second short paragraph (30 words or less) which explains the potential strategies that they do use. Tailor your response to suite a 13 year old student studying computing, keep the tone encouraging, clear and authoritative but avoid using overly academic jargon. Contrains: No deviation, no intro, no outro, no follow up questions.
What does it tell you about the random walk algorithm?
Outcome: You should now have empirical evidence that a random walk is a terrible algorithm for escaping a maze quickly!
The Systematic Solution (Depth-First Search)
Clearly, guessing isn't going to work for an app like Google Maps. We need an algorithm that has a memory. Enter the Depth-First Search (DFS).
The DFS algorithm works on a simple principle: pick a path and go as deep into the maze as you possibly can. Keep going until you hit a dead end. When you hit a wall, you backtrack (reverse your steps) to the last intersection you passed, and try a different path. Crucially, the algorithm leaves a digital 'breadcrumb trail' so it knows which paths it has already explored and never visits the same dead end twice.
Think of it like keeping your right hand continuously touching the wall of a maze. Eventually, following the wall into every corner and out again, you will find the exit!
Task 2 The Breadcrumb Trail (Tracing DFS)
It is time to act like a computer! You are going to manually execute a Depth-First Search algorithm on a paper maze. You must follow the algorithm's rules exactly - no human intuition allowed!
1
Research first!
Firstly, I want you to perform some research into the concept of 'backtracking' using Google AI mode search. Simply click the prompt below and then read the explanation.
Act as an expert computer science tutor. Explain the concept of "backtracking" in a Depth-First Search algorithm. Explain it simply so a 13-year-old KS3 student can understand. Limit your response to 1 short paragraph. No intro. No outro. No follow up questions.
Did you find it helpful? Look carefully at the prompt. Maybe you can use a prompt like this in the future when you have to perform some research?
2
Get Organised!
You need your printed maze worksheet (ask your teacher) and two different coloured pens (e.g., Blue for searching forward, Red for backtracking).
3
The Rules of the Algorithm
Start at the entrance (at the top) with your Blue pen.
Rule 1: Walk forward until you hit a junction or a dead end.
Rule 2: At a junction, ALWAYS turn left first. If left is blocked or already explored, go straight. If straight is blocked, go right.
Rule 3: If you hit a dead end, switch to your Red pen. Trace your path backwards until you reach a junction that has an unexplored path. Switch back to your Blue pen and explore it!
4
Execute!
Follow the rules exactly. Do not look ahead to find the exit. Just follow the rules one step at a time. Continue until you do find the exit - if you follow the rules properly, you will always find your way out, eventually...
Outcome: A fully traced maze showing exactly how an algorithm explores every necessary path, using memory (backtracking) to guarantee success.
Extension - Finding the BEST Route
You might have noticed something during the last task. A Depth-First Search is brilliant at finding a way out of a maze, but it does not guarantee finding the fastest or shortest way out. It might take you on a massive detour just because that happened to be the first path it explored!
For a mapping app like Google Maps, providing a route that is 40 miles longer than necessary is useless. This is where advanced algorithms like Dijkstra's Algorithm come in. While DFS blindly explores deep down a single path, Dijkstra explores outward evenly like a ripple in a pond, calculating the 'cost' (distance or time) of every step to ensure it finds the absolute shortest, optimal path to the destination.
Out of Lesson Learning
Last modified: March 4th, 2026
