Every visualiser in this course uses the same four marks. They'll make sense properly in lesson 2, but it helps to know them now.

Each lesson is a control on the course line down the side of the page. Work through them in order, because each algorithm fixes a problem the previous one couldn't handle.

1. Grids are graphs. Turn a map into something a computer can search.
2. Blind search. Depth-first and breadth-first search, and why one of them guarantees the fewest steps.
3. Weighted terrain. When steps cost different amounts, Dijkstra's algorithm finds the cheapest route.
4. Heuristics and A*. Give the search a sense of direction without losing the guarantee.
5. Measuring efficiency. Race every algorithm and back your conclusions with data.
6. Challenge arena. Apply everything to harder problems of your own choosing.

You'll write Python in your usual editor (Thonny, IDLE or VS Code). Each lesson has code to build, checkpoint questions that mark themselves, and a short quiz. Finishing a quiz with every answer correct ticks off that control. Your progress is saved in this browser.

Start with the problem, not the theory. Plot Scout's route across this small map by tapping cells one at a time, starting next to the triangle. Scout can only move up, down, left or right, one cell per move.

A graph is a collection of nodes (also called vertices) joined by edges. Graphs don't care about shapes or distances on a page; they only record what connects to what. That makes them perfect for describing any problem that involves moving between places: train stations, web pages linking to each other, friends on social media, or cells on a map.

A grid map becomes a graph with two simple rules:

• every cell Scout can stand on becomes a node
• every pair of cells Scout can move directly between gets an edge

Rock cells become nothing at all. They simply disappear from the graph, which is how the graph "knows" Scout can't go there.

Some vocabulary you'll use for the rest of the course:

• Two nodes are neighbours if an edge joins them.
• A path is a sequence of nodes where each one is a neighbour of the next.
• The length of a path is the number of edges (moves) in it. A route through 13 cells has length 12.
• In lesson 3, edges get a weight: a cost for crossing them. Then the shortest path is the one with the smallest total weight.

The simplest way to store a map in Python is a list of strings. Each string is a row, and each character is a cell. We'll use # for rock, . for open ground, S for the start and G for the goal.

Every search algorithm needs to ask one question over and over: from this cell, where can Scout go next? That's the job of neighbours(). For a cell at (row, col), the four candidate moves are:

• up: (row - 1, col)
• down: (row + 1, col)
• left: (row, col - 1)
• right: (row, col + 1)

A candidate only counts if it's on the map and not rock. Try it below: tap any open cell and the explorer shows what neighbours() should return, and why each rejected candidate was rejected.

Complete the function below. Replace each TODO with working code.

Run your code and answer these. The page works out the correct answers from the same map, so if yours differ, your function has a bug.

At any moment during a search, every cell on the map is in one of three states:

• Explored: Scout has visited it and already looked at all its neighbours. (Yellow in the visualisers.)
• Frontier: Scout knows it exists, because it was seen next to an explored cell, but hasn't visited it yet. (Blue dots.)
• Unknown: not seen at all yet.

The frontier is the boundary between what Scout has explored and what it hasn't. Every search algorithm in this course runs the same loop:

1. Put the start cell in the frontier.
2. Take one cell out of the frontier. This is the current cell (magenta ring).
3. If it's the goal, stop.
4. Otherwise, add each of its neighbours that hasn't been seen before to the frontier.
5. Go back to step 2.

That's the whole idea. The only thing that changes between algorithms is which cell step 2 takes out. And that depends entirely on what kind of container the frontier is.

A stack works like a pile of plates: you add to the top and take from the top, so the last thing in is the first thing out (LIFO). A queue works like the line at the canteen: you join at the back and get served from the front, so the first thing in is the first thing out (FIFO).

If the frontier is a stack, Scout always continues from the cell it discovered most recently. It charges down one corridor as far as it can go, and only backs up when it hits a dead end. That's depth-first search (DFS).

Press Step a few times and watch the frontier panel on the right. Then press Play.

Now change one thing: make the frontier a queue. Scout always takes the oldest cell in the frontier. The start's neighbours were added first, so they're all explored before any of their neighbours. The search spreads out evenly in every direction, like ripples from a stone dropped in a pond. This is breadth-first search (BFS).

Turn on Show step counts to see how many moves each cell is from the start.

This is the most important idea of the lesson, so it's worth following carefully.

1. BFS explores every cell 1 step away before any cell 2 steps away, every cell 2 steps away before any cell 3 steps away, and so on. The queue forces this, because cells are added in the order they were discovered.
2. Suppose the goal is really d steps away. BFS can't reach it earlier than ring d, because no route that short exists.
3. And it can't reach it later, because it finishes ring d before starting ring d + 1.
4. So the first time BFS reaches the goal, it has used the fewest possible steps. No cleverness needed; the order does the proving.

This proof only works if every step costs the same. Hold that thought for lesson 3.

When BFS reaches the goal, it knows the goal is reachable, but it hasn't stored the route. The fix is simple: whenever a cell is discovered, write down which cell it was discovered from. We store this in a dictionary called came_from.

In the visualisers, Show came_from arrows draws these links as small arrows pointing back toward the cell each one came from. Once the goal is found, follow the arrows backward from the goal to the start, then reverse the list. That's the route.

Here's breadth-first search in Python. Read it line by line and match each part to the loop from the top of the lesson. deque is Python's fast queue: append() joins the back and popleft() serves the front.

To turn this into depth-first search, you change exactly one line: replace frontier.popleft() with frontier.pop(). Now it takes from the back, which makes the deque behave like a stack. Try it and compare the results.

From now on, entering a cell costs energy: 1 for open ground, 3 for scrub and 5 for marsh. The cost of a route is the total energy for every cell it enters (the start is free, since Scout is already there).

Run BFS on Arena B below and look at the route cost when it finishes. Then switch to Dijkstra and run it again.

Edsger Dijkstra's idea was a small change to BFS with a big effect. Instead of taking the oldest cell from the frontier, take the one with the lowest total cost so far. We call that cost g.

BFS explored in rings of equal steps. Dijkstra explores in rings of equal cost. Cheap ground gets explored quickly, and expensive ground gets put off until everything cheaper has been tried.

There's one more change. With BFS, the first time we saw a cell was always by its shortest route. With costs, a cell might first be seen along an expensive route and later reached more cheaply. So Dijkstra checks every time: if the new route to a neighbour is cheaper than the best one recorded, it updates the cost and came_from. This update is called relaxing an edge.

Before coding, step through Dijkstra on a small graph. Numbers on the edges are costs. The yellow badges show each node's best known cost so far, and the magenta lines show the came_from links as they form. Step through slowly and read each explanation.

When Dijkstra takes a node out of the frontier, its cost is final. It will never find a cheaper route to that node later. Here's why:

1. The node taken out has the lowest cost of anything in the frontier. Call that cost g.
2. Any other route to it would have to leave the explored area through some frontier node, and every frontier node already costs at least g.
3. Costs can only go up as a route gets longer, because every cell costs at least something.
4. So no other route can come in under g. When the goal comes out of the frontier, its cost is the cheapest possible.

Step 3 is the catch: the proof needs every cost to be zero or more. If some cell gave back energy (a negative cost), Dijkstra could lock in an answer too early and be wrong.

Use the same method on this graph, starting from S. Work it out on paper with a table like the one above, then enter the final cheapest cost to each node.

Dijkstra needs a frontier that can always hand over the cheapest item quickly. That's a priority queue. Think of a hospital emergency department: patients aren't seen in the order they arrive, but in order of urgency.

Python's heapq module keeps a list arranged so the smallest item is always at the front. We store (cost, cell) pairs, so the smallest cost comes out first.

Turn on Show costs and run Dijkstra. Each number is the cheapest cost from the start to that cell. Watch the explored area stretch quickly across open ground and crawl through scrub and marsh. Try painting your own scrub and marsh with the tools, then run it again.

Dijkstra is BFS with a priority queue and a cost check. Add the terrain costs and Arena B to your file, then complete the TODO lines.

Run Dijkstra on the open field and count how much of the map it explores before reaching a goal that's in plain sight. Dijkstra is careful, but it isn't smart: it has no idea where the goal is until it trips over it.

A heuristic is a quick estimate of how far a cell is from the goal. It doesn't need to be exact; it just needs to be cheap to calculate and point roughly the right way. We call it h.

Because Scout moves in four directions, the natural estimate is Manhattan distance: count the rows and the columns between the cell and the goal, and add them. It's named after the grid of streets in Manhattan, where you can't cut diagonally through the buildings.

h = |row − goal_row| + |col − goal_col|

What if we swap Dijkstra's rule for the heuristic, and always expand the cell with the smallest h? This is greedy best-first search. It charges toward the goal and, on an open map, barely explores anything.

But instinct can be wrong. Try it on The long wall and on Forest run, and compare the route cost with Dijkstra's.

Dijkstra only looks backward at what has been spent (g). Greedy only looks forward at what's left (h). A* (say "A-star") adds them together:

f = g + h

f is an estimate of the total cost of the best route that goes through this cell. A* always expands the cell with the lowest f. Cells that are cheap to reach and look close to the goal get explored first, and cells heading the wrong way get put off.

Use the Inspect tool below, then tap cells during or after a run to see their g, h and f values.

A* is only guaranteed to find the cheapest route if the heuristic never overestimates the true remaining cost. A heuristic like that is called admissible.

Manhattan distance is admissible on our maps. Every move brings Scout at most one cell closer to the goal, and every move costs at least 1. So the real remaining cost can never be less than the Manhattan distance. The estimate might be too low (marsh makes the real cost higher), but it's never too high.

Why does overestimating break things? If h is too big for a cell that's actually on the best route, that cell's f looks worse than it really is. A* might finish along another route before it ever gets around to checking the good one.

A* is Dijkstra with one extra term in the priority. Copy your dijkstra() function, rename it, and change the priority you push onto the heap.

Timing code in seconds is tempting, but it depends on the computer, what else is running and even the room temperature. A fairer measure is nodes expanded: the number of cells taken out of the frontier and processed. It's the same on every computer, and it tracks how much work the algorithm really did.

We also care about the quality of the answer: route cost, and whether it matched the cheapest possible.

All five algorithms run side by side on the same map, one step each per tick. Choose a map and start the race. When every algorithm has finished, the results table and chart appear below.

Computer scientists usually describe an algorithm by its worst case: the most work it could ever have to do. For all five algorithms, the worst case is exploring every cell on the map. That happens when the goal is in the last place the search looks, or when there's no route at all (the search can't give up until the frontier is empty).

If a map has n open cells, BFS and DFS do work proportional to n, written O(n). Dijkstra and A* also have to keep their priority queue in order, which adds a little on top: roughly O(n log n). A good heuristic doesn't change A*'s worst case, but it makes the typical case far better, and that's what you see in the race.

Complete the table from memory, then check it. This is the whole course on one page.

Add a counter to each of your Python functions: set expanded = 0 before the loop, add 1 each time a cell comes out of the frontier and isn't skipped, and return it alongside the result. Then run all of them on both maps and chart the results.

Pick one challenge (or more, if you finish). Build it in Python using your own functions from lessons 1 to 4. Each one tests a different piece of theory.

Every algorithm, every tool, any map. Use this to test ideas and to build the maps you need for your challenge.

Answer in full sentences. When you're done, copy your answers and paste them into your submission.