Everyone Can Learn Program
中文 Start learning
Course 1 · Zero to codingLesson 10 of 10Free to read

Final: any maze · Robot Quest

Can you write one program that solves mazes it has never seen?

Course contents

Why you need it

This is the final challenge, and it uses everything: functions, while, if, and the sensors. More importantly it introduces the idea of an algorithm: a general method that works for a whole family of problems, not just one.

The intuition

Lost in a maze? Put your right hand on the wall and never take it off. You will eventually walk out (for mazes where all the walls are connected). This is the right-hand rule.

For Bit, "keep the right hand on the wall" becomes one step:

  1. Turn right (try to follow the wall).
  2. While the way ahead is blocked, turn left.
  3. Move forward.

Repeat that step until the flag. Pick up gems along the way.

Definition

Algorithm

An algorithm is a finite, step-by-step method for solving a whole class of problems.

Examples

One step of the rule

Run it in the lesson

Run it and watch Bit hug the right wall around the corner.

def step():
    turn_right()
    while not front_clear():
        turn_left()
    move()

while not at_goal():
    step()
Step by step
  1. L7Not on the flag yet: take one step.
  2. L2Try turning right first.
  3. L3Blocked? Turn left until the way is clear.
  4. L5Move forward one square.
  5. L7Repeat until the flag, through both corners.

A whole maze

Run it in the lesson

The same algorithm, plus picking gems. It also solves the mazes in the exercises.

def step():
    turn_right()
    while not front_clear():
        turn_left()
    move()

while not at_goal():
    step()
    if on_gem():
        pick()
Step by step
  1. L8Loop until the flag.
  2. L9One step of the right-hand rule.
  3. L10After every step, check for a gem.

Common mistakes

Spinning on the spot

If Bit is completely walled in, while not front_clear(): turn_left() never ends. The maps here always have a way out.

Checking the flag too late

Check at_goal() in the while condition so Bit stops the moment it arrives.

Quick quiz

1. Where does Bit end up?

def step():
    turn_right()
    while not front_clear():
        turn_left()
    move()

step()
step()
  1. ABottom-left: on the flag
  2. BTop-right corner
  3. CMiddle of the top row
Show the answer

Answer: A

2. Why is the right-hand rule called an algorithm?

  1. AIt works for a whole family of mazes, step by step
  2. BIt is very short
  3. CIt uses a while loop
Show the answer

Answer: A

An algorithm is a general method, not a solution for one map.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

  1. PredictTrace the rule

    Predict where Bit ends up after three steps.

  2. ModifyDon't forget the gems

    This solver reaches the flag but leaves the gems behind. Fix it so it collects every gem in both mazes.

  3. WriteGraduation maze

    Write the full maze solver from scratch: a step() function for the right-hand rule, a while loop until the flag, and gem picking. It must solve all 3 mazes.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

TermChineseDefinition
Algorithm算法A finite, step-by-step method that solves a whole class of problems.
Right-hand rule右手法则A maze algorithm: keep the wall on your right and follow it.