Comparing Maze-Solving Algorithms

Students trace two maze-solving algorithms, measure their performance, and use test evidence to argue which algorithm works best under a stated constraint.

Define the Maze-Solving Problem

A maze-solving problem has a start, a goal, open passages, and walls that cannot be crossed. Before comparing algorithms, state the rules and the constraint. For example, imagine a robot that begins at cell S and must reach cell G. From S, one branch leads through A to dead-end C. Another branch leads through B and D to G. The robot may move only between neighboring open cells. A useful constraint might be, “Find a route using the fewest moves,” or “Always reach the goal when a route exists.” Define what counts as a move, how the robot recognizes the goal, and whether it can remember visited cells. These details make the test fair and repeatable.

Trace Two Algorithms

Trace each algorithm by following its instructions exactly. The right-hand wall follower keeps its right side against a wall. At every choice, it tries right, straight, left, and then back, in that order. In the example maze, it enters branch A, reaches dead-end C, returns to S, and then follows B and D to G. Breadth-first search, or BFS, uses a queue and memory. It examines S, records both A and B, and then examines recorded cells in first-in, first-out order. With A recorded before B, it checks A, B, C, and D. When D reveals G, BFS uses parent links to reconstruct S-B-D-G. Mark every action during a trace so another student can verify that no instruction was skipped.

Count Steps and Record Results

Use a data table instead of judging an algorithm by appearance. Record movement and search work separately because BFS plans before the robot follows its route. In the example, the wall follower travels S-A-C-A-S-B-D-G, for 7 moves. It uses little memory because it mainly tracks direction. BFS expands S, A, B, C, and D before discovering G, for 5 cell expansions. Its final route S-B-D-G requires 3 robot moves, but it must store discovered cells and parent links. Repeat the procedure on several mazes, including a straight corridor, a maze with dead ends, and a maze with a loop. Use the same neighbor order and stopping rule every time. Record every result, even when an algorithm fails or repeats positions.

Compare Efficiency and Reliability

Efficiency describes the resources an algorithm uses, such as moves, processing work, time, or memory. Reliability describes whether it succeeds under the tested conditions. In the example, BFS produces a 3-move route, while the wall follower makes 7 moves because it explores a dead end. BFS is more efficient when the main constraint is shortest route length, although it uses more memory. A wall follower may perform well in a simple corridor and needs little stored information. However, in a maze with a loop around an isolated wall, it can circle repeatedly and never reach the goal. BFS systematically visits reachable cells and will find a route in a finite maze if one exists. Compare averages across tests, but also examine failures because one failure can matter more than a small difference in speed.

Defend the Best Solution

Choose the best algorithm only after stating the constraint. Build an argument with a claim, evidence, and reasoning. For example: “BFS is the better solution when the robot must use the shortest available route and has enough memory.” Evidence can include the traced example, where BFS found a 3-move route and the wall follower used 7 moves, plus results from the corridor, dead-end, and loop tests. Explain that BFS checks routes in order of their distance from the start, so the first route it finds to the goal is a shortest route in an unweighted maze. Also address a competing view: the wall follower may be better when memory is extremely limited and the maze structure guarantees success. A strong conclusion names the conditions, cites multiple test results, and does not claim that one algorithm is always best.