Can a Robot Get Out of Any Maze?

Keep your hand on the wall

Here is a trick many people know. Put your right hand on the wall beside you, and walk, never letting go. When the wall turns, you turn with it. When you reach a dead end, your hand leads you round it and back out.

For a robot that moves in squares, the trick becomes a rule with three parts, tried in order at every square:

1. If there is no wall on your right, turn right and step forward.
2. Otherwise, if there is no wall ahead, step forward.
3. Otherwise, turn left (and try again).

That is all. The robot below follows it.

One long wall

Why does the right hand get out of the Temple, which has loops and walls standing alone in the middle, but not when the robot starts inside it? Look at the Temple’s walls by piece: a piece is a set of wall squares that touch each other, at a side or a corner.

The robot’s hand is always on one piece of wall: it never lets go, so it can never jump to another piece. Starting at the gate, its hand is on the gray piece, which runs along the edge of the maze, past the exit. Imagine pulling that gray wall straight, like unrolling a rope: the robot is walking along one long wall, and the exit is a gap in it. Walking along it, the robot must reach the gap.

That is the whole secret. The loops don’t matter: in the Temple, the robot never even touches the blue, purple and amber walls.

A wall that stands alone, joined to nothing, is called an island. A maze whose walls all join up has no islands, and the right-hand rule gets out of it from anywhere. With islands, it depends on the wall the hand starts on: from a gate, the outside wall leads to any exit in the outside wall; beside an island, the robot circles it forever (Figure 5.2); and an exit beside an island, as in the maze with the exit in the middle, is never reached from the outside wall.

Chalk on the floor: Trémaux’s marks

To escape any maze, the robot must remember something. In the 1880s a French telegraph engineer, Charles Trémaux, gave a method that works in every maze. You carry a piece of chalk, and you mark every doorway you walk through (a doorway is the gap between two squares). Then, at every square:

1. If you have just come in through a doorway with only one mark (you have never come this way before) to a square you have been to before, turn round and go back the way you came.
2. Otherwise, take a doorway with no marks if there is one.
3. Otherwise, take one with one mark. Never walk through a doorway with two marks.

A doorway with two marks has been walked both ways, so what lies behind it has been explored. The first rule stops you going round a loop: come back to a place you know, and the path you came by is treated as a dead end.

Trémaux’s marks get out of every maze, from anywhere: they explore it, every passage at most twice, until they find the exit. The price is chalk, a memory of what the robot has done; the right-hand rule needs none.

With blocks: one maze, one plan

First, the way a Grade 6 program would do it: a list of steps for one maze. The program below starts the Garden: five squares forward, turn right, two forward. Finish it, so the robot reaches the flag.

With blocks: the rule

A program that works in any maze can’t be a list of moves: it has to look at the walls and choose. The blocks below have three new kinds: wall on the right? and wall ahead? (true when there is a wall there), at the exit?, and repeat until, which repeats the blocks inside it until its condition becomes true. The program is the right-hand rule, with one part missing: what to do when there is no wall on the right.

The Test can say “going round forever” because the program keeps a note each time repeat until starts a round: where the robot is, which way it faces, and the value of every variable. If the same note ever comes up twice, the program is in exactly the same situation as before, and nothing can ever make it act differently.

In Python (from Grade 8)

Step 1: the robot in Python

A maze is a list of strings, one per row: # is a wall, . a floor square, S the start and E the exit. The robot’s direction is a number: 0 north (up), 1 east, 2 south, 3 west. Turning right adds 1, and % 4 brings 4 back to 0; turning left adds 3, which is the same as taking away 1 and going round. STEP says how the row and column change for one step in each direction.

The picture at the end comes from show_grid, part of the page’s own pixels module (on your own computer you would draw it with a library such as Pillow). It colors one square for each letter.

from pixels import show_grid GARDEN = ['###########',          'S.....#...#',          '#####.###.#',          '#...#...#.#',          '#.#.###.#.#',          '#.#.#...#.#',          '#.###.###.#',          '#.........E',          '###########'] # north, east, south, west: how the row and column change for one stepSTEP = [(-1, 0), (0, 1), (1, 0), (0, -1)] def wall(maze, r, c):    # outside the maze counts as a wall    if r < 0 or r >= len(maze) or c < 0 or c >= len(maze[0]):        return True    return maze[r][c] == '#' def wall_on(maze, r, c, facing):    # is there a wall next to square (r, c) on the side `facing`?    return wall(maze, r + STEP[facing][0], c + STEP[facing][1]) def right_hand(maze, r, c, facing):    path = [(r, c)]    while maze[r][c] != 'E':        right = (facing + 1) % 4        if not wall_on(maze, r, c, right):            facing = right                     # turn right, then step            r = r + STEP[facing][0]            c = c + STEP[facing][1]            path.append((r, c))        elif not wall_on(maze, r, c, facing):            r = r + STEP[facing][0]            # straight on            c = c + STEP[facing][1]            path.append((r, c))        else:            facing = (facing + 3) % 4          # turn left    return path def picture(maze, path):    rows = []    for r in range(len(maze)):        row = ''        for c in range(len(maze[0])):            if (r, c) in path and maze[r][c] != 'E':                row = row + 'o'            else:                row = row + maze[r][c]        rows.append(row)    return rows COLORS = {'#': '#6f6a55', '.': '#fbf8ec', 'S': '#fbf8ec',          'E': '#5e8f5f', 'o': '#8fb0e0'} path = right_hand(GARDEN, 1, 0, 1)        # start at S, facing eastprint('Out in', len(path) - 1, 'moves')show_grid(picture(GARDEN, path), COLORS)

Out in 44 moves

Picture

path is the list of squares the robot stood on, so the number of moves is one less than its length. The right hand leads into the dead end at the lower left, round, and out again.

Step 2: every maze, and knowing when to stop

In a maze with an island, Step 1’s while loop would never end. So the robot keeps a list, been, of every square it has stood on together with the way it faced, and stops as soon as one comes up again. The mazes and the functions from Step 1 are in a file the page keeps for you, maze_robot.py.

from pixels import show_gridfrom maze_robot import GARDEN, TEMPLE, MIDDLE, STEP, wall_on, picture, COLORS def right_hand(maze, r, c, facing):    path = [(r, c)]    been = []                    # every (row, column, facing) so far    while maze[r][c] != 'E':        if (r, c, facing) in been:            return path          # been here, facing this way: stuck        been.append((r, c, facing))        right = (facing + 1) % 4        if not wall_on(maze, r, c, right):            facing = right            r = r + STEP[facing][0]            c = c + STEP[facing][1]            path.append((r, c))        elif not wall_on(maze, r, c, facing):            r = r + STEP[facing][0]            c = c + STEP[facing][1]            path.append((r, c))        else:            facing = (facing + 3) % 4    return path TRIES = [['Garden', GARDEN, 1, 0, 1],         ['Temple, from the gate', TEMPLE, 1, 0, 1],         ['Temple, from inside', TEMPLE, 5, 3, 0],         ['Exit in the middle', MIDDLE, 1, 0, 1]] for name, maze, r, c, facing in TRIES:    path = right_hand(maze, r, c, facing)    end = path[-1]    if maze[end[0]][end[1]] == 'E':        print(name + ': out in', len(path) - 1, 'moves')    else:        print(name + ': stuck after', len(path) - 1, 'moves')        show_grid(picture(maze, path), COLORS)

Garden: out in 44 movesTemple, from the gate: out in 46 movesTemple, from inside: stuck after 24 movesExit in the middle: stuck after 58 moves

Picture

The first picture is the trap of Figure 5.2: 24 moves round the middle block, and back to the start. The second is the robot walking all the way round the outside and back to the gate, without once touching the walls round the exit.

Step 3: Trémaux’s chalk

The chalk marks are a list, chalk, with one entry for every mark: chalk.count(d) says how many marks doorway d has. A doorway between two squares must have the same name from both sides, or the robot coming back would not see its own mark. So door names a doorway by the square above it or to its left, and the side it is on (2 for below, 1 for the right).

from pixels import show_gridfrom maze_robot import GARDEN, TEMPLE, MIDDLE, STEP, wall_on, picture, COLORS def door(r, c, d):    # the doorway from square (r, c) towards d, with the same    # name from both sides: (square above or left, 2 or 1)    if d == 0:        return (r - 1, c, 2)    if d == 3:        return (r, c - 1, 1)    return (r, c, d) def tremaux(maze, r, c, facing):    chalk = []                   # one entry for every chalk mark    path = [(r, c)]    while maze[r][c] != 'E':        back = (facing + 2) % 4        ways = []                # open doorways: right, ahead, left        for d in [(facing + 1) % 4, facing, (facing + 3) % 4]:            if not wall_on(maze, r, c, d):                ways.append(d)        been_here = False        for d in ways:            if chalk.count(door(r, c, d)) > 0:                been_here = True        if len(path) > 1 and been_here and chalk.count(door(r, c, back)) == 1:            go = back            # a new path into an old square: go back        else:            go = -1            for d in ways:       # a doorway with no mark                if go == -1 and chalk.count(door(r, c, d)) == 0:                    go = d            for d in ways:       # else one with one mark                if go == -1 and chalk.count(door(r, c, d)) == 1:                    go = d            if go == -1:         # a dead end: go back                go = back        chalk.append(door(r, c, go))        facing = go        r = r + STEP[go][0]        c = c + STEP[go][1]        path.append((r, c))    return path TRIES = [['Garden', GARDEN, 1, 0, 1],         ['Temple, from the gate', TEMPLE, 1, 0, 1],         ['Temple, from inside', TEMPLE, 5, 3, 0],         ['Exit in the middle', MIDDLE, 1, 0, 1]] for name, maze, r, c, facing in TRIES:    path = tremaux(maze, r, c, facing)    print(name + ': out in', len(path) - 1, 'moves')show_grid(picture(MIDDLE, path), COLORS)

Garden: out in 44 movesTemple, from the gate: out in 46 movesTemple, from inside: out in 63 movesExit in the middle: out in 129 moves

Picture

Where a doorway can be chosen, the robot tries right first, then ahead, then left. So in a maze with no surprises it walks exactly like the right-hand rule: the Garden and the Temple take 44 and 46 moves either way. The chalk only makes a difference where the right hand would go round in circles.

• One rule, no map, no memory: out of the Garden in 44 moves and the Temple in 46. The Temple’s loops and islands didn’t matter: the hand started on the outside wall.
• Dropped inside the Temple: 24 moves, then back where it started. Your program didn’t just give up after a while; it proved the robot would never get out, since back on the same square, facing the same way, it can only repeat itself.
• The exit in the middle: 58 moves round the outside, and back at the gate. The walls round the exit are an island.
• Trémaux’s chalk gets out of all four, 63 moves from inside the Temple and 129 to the middle. It needs memory, but it never fails.

Two rules, two kinds of power. The right-hand rule needs nothing but sensors; it works whenever the robot’s wall leads to the exit. Trémaux’s marks need memory, and work everywhere. That trade between a simple rule and remembering more is one you will meet again and again in computing.

Left or right? In your Step 2 program, make a left_hand that turns left first. From inside the Temple it gets out! Now start it on the same square facing south (facing 2). What happens?

A robot with no memory that never gets trapped. Give the robot a die instead of chalk: at every junction it chooses a way at random. This random mouse remembers nothing, yet it can’t be trapped forever: sooner or later the dice send it down every passage. The catch is how long it takes. Write a random_mouse in Python (random.choice(ways)), run it from inside the Temple a hundred times, and compare the average number of moves with Trémaux’s 63.

★ The left-hand rule (blocks)

Build the left-hand rule from the start: the same three parts, with left and right swapped. Press Test: your program must get out of the Garden, the Temple and from inside the Temple.

★★ Cut out the dead ends (Python, from Grade 8)

Write shorten(path). path is a list of squares, each a list [row, column], as a walk visits them. Give back the walk with every detour cut out: go through the squares in order, keeping a list route; when a square is already in route, it is a return, so take squares off the end of route until that square is last again; otherwise add it to the end.

def shorten(path):    # give back the walk with the detours cut out    return path print(shorten([[1, 0], [1, 1], [1, 2], [2, 2], [1, 2], [1, 3]]))

★★★ The 12-year-old’s rule (Python, from Grade 8)

This rule is named after Jon Pledge of Exeter, England, who is said to have found it when he was 12; it became known through Harold Abelson and Andrea diSessa’s book Turtle Geometry (1980). Choose a direction, north. Walk north until a wall is ahead. Then turn left and follow the wall with your right hand, as in Step 1, keeping a count: +1 for every right turn, −1 for every left turn. As soon as the count is back to 0 (you are facing north again, and have unwound every turn), leave the wall and walk north again.

Write pledge(maze, r, c): the robot starts at square (r, c) facing north with the count 0; give back the number of moves forward until it is on the exit. Count only moves forward, not turns. (A right turn always comes with a step, as in Step 1. wall_on and STEP are given.)

STEP = [(-1, 0), (0, 1), (1, 0), (0, -1)] def wall(maze, r, c):    if r < 0 or r >= len(maze) or c < 0 or c >= len(maze[0]):        return True    return maze[r][c] == '#' def wall_on(maze, r, c, facing):    return wall(maze, r + STEP[facing][0], c + STEP[facing][1]) TEMPLE = ['###############',          'S.......#.....#',          '#.#####.#.###.#',          '#.#.........#.#',          '#.#.#######.#.#',          '#...#######...#',          '###.#######.###',          '#...........#.#',          '#.#####.###.#.#',          '#.....#...#...E',          '###############'] def pledge(maze, r, c):    # count the moves forward until the robot is on the exit    return 0 print(pledge(TEMPLE, 5, 3))

• Grade 6, Programming with Blocks: loops, the repeat blocks that walked the Garden.
• Grade 7, Variables and Choices: if/else, the choice at the heart of the rule.
• Grade 8, Physical Computing: real sensors on a real board, the kind a maze robot uses to feel its walls.
• Grade 10, Graphs, Maps, Routes and Networks: breadth-first search, which finds the shortest way out when the whole maze is known.
• Can one random choice draw a maze? Draw / or \ at random in every square, and a maze appears. (Coming soon.)
• How does a robot know where it is? A robot that can’t see the whole room works out its place from what its sensors say. (Coming soon.)