Can One Random Choice Draw a Maze?

Look at the maze above for a while.

• a.Find two lines that meet at the top, like a roof: ╱╲. And two that meet at the bottom, like a cup: ╲╱.
• b.Find a small closed room, a diamond made of four squares. Can anything get in or out of it?
• c.Press New maze a few times. Is any maze the same as one before?

Pour water in

A maze is only a maze if there is a way through. Here is a square maze, 10 squares by 10. Water comes in at the left side and flows along the passages. Can it get out on the right?

• a.How many of your mazes had a way through?
• b.When the water stopped, look at the red line. Where does it start and where does it end?
• c.Tap one square of the red wall to flip it, and pour again. What happens?

Two characters and a coin

The Commodore 64’s screen showed 40 letters across and 25 rows down. Among its letters were two diagonal lines, number 205 (╲) and number 206 (╱). Its program was one line of the language BASIC:

10 PRINT CHR$(205.5+RND(1)); : GOTO 10

• RND(1) is a random number from 0 up to (but not reaching) 1, like 0.73 or 0.08.
• 205.5 + RND(1) is then between 205.5 and 206.5. CHR$ keeps only the whole number part, so it is 205 if the random number was under 0.5 and 206 if it was 0.5 or more: a fair coin toss.
• PRINT puts that character on the screen, and the ; says “don’t start a new line”, so the next one goes beside it. At the end of a row, the screen goes on to the next row by itself.
• GOTO 10 goes back to line 10, forever (until you press the STOP key).

That is the whole program: one random choice, repeated. There is no maze anywhere in it. The maze is made by your eyes, from lines that happen to touch.

Why the walls join up

Two neighbors in a row can sit four ways:

Lines in rows above and below touch at the corners too. So, by chance, short lines join end to end into long, winding walls. Where four squares make ╱╲ above ╲╱, the four lines close into a diamond, a room with no door at all.

What stops the water

When the water in the widget stopped, there was always a red wall: lines joined end to end, from the top side of the maze to the bottom side. Water can’t get past a wall like that, so it can never reach the right.

And the other way round: if no wall reaches from top to bottom, there is always a gap somewhere, and the water finds it. So every maze is one of two kinds, never both and never neither:

• a way through from left to right, or
• a wall from top to bottom.

In a square maze, a wall from top to bottom happens about 4 times in 5. One reason it is so common: the corners of the squares fall into two sets, like the black and white squares of a chessboard, and every line joins two corners of the same set. So there are two separate families of walls that never touch each other, and either family can block the water.

With blocks

The turtle can draw the maze. It starts each square on the square’s bottom-left corner, facing right, with the pen up, and picks a number, 1 or 2:

• 1 (╱): pen down, turn 45° left and move along the diagonal to the top-right corner. Pen up, turn and hop down to the bottom-right corner.
• 2 (╲): hop up to the top-left corner, pen down, and move down the diagonal to the bottom-right corner. Pen up.

Either way it ends on the bottom-right corner, which is the next square’s bottom-left corner, facing right again. The squares are 25 steps wide, so the diagonal is 35.36 steps (25 × 1.414, by Pythagoras). After 20 squares the turtle hops up a row and back to the left.

In Python (from Grade 8)

Step 1: the one line

Python’s random.choice('╱╲') picks one of the two characters at random. Printed again and again, they make the maze as text.

import random random.seed(10)for row in range(10):    line = ''    for col in range(30):        line = line + random.choice('╱╲')    print(line)

╱╲╲╱╱╲╲╲╱╱╲╲╱╱╲╱╲╱╲╲╲╲╲╲╱╲╲╱╲╱╲╲╱╱╱╱╱╲╲╱╲╲╲╲╱╲╱╱╲╱╱╱╲╲╱╱╱╲╲╱╱╱╲╱╱╲╲╲╲╱╲╱╱╱╲╲╲╱╱╱╲╲╲╲╱╱╱╲╲╱╱╲╲╲╱╲╲╱╲╲╲╱╱╲╲╲╱╲╲╲╲╱╲╱╲╱╱╲╱╱╲╱╱╱╲╲╱╲╲╲╲╲╲╲╲╱╱╲╱╱╲╱╱╲╲╱╲╱╱╱╲╱╲╱╲╲╱╲╱╱╱╲╱╱╲╲╲╲╱╲╲╱╱╱╲╲╲╱╱╲╱╱╲╲╲╲╲╱╲╲╲╲╲╲╲╲╲╲╲╲╲╲╱╲╲╱╲╱╲╱╲╲╱╲╲╲╱╱╱╲╱╱╱╱╲╱╲╱╲╱╲╱╲╱╱╱╲╲╲╱╱╱╲╱╱╲╱╲╲╲╱╱╲╲╲╲╱╲╲╲╲╲╱╱╲╱╱╱╱╲╲╲╱╱╱╲╱╱╱╱╲╱╲╱╲╲╱╲╱╲╱╱╲╲╲╱╱╱╲╱

random.seed(10) makes Python pick the same “random” characters each time, so your run matches this one; change the 10 for a new maze. The real 10 PRINT never stops; in Python that is one line too, while True: print(random.choice('╱╲'), end=''), but the page stops any program after 10 seconds.

The rows of text have gaps between them, so the lines don’t quite touch. A picture is better.

Step 2: a picture of the maze

A list of strings, one string a row, holds the maze: maze[2][5] is the square in row 2, column 5 (counting from 0). The function to_picture turns each square into 3 × 3 pixels, 1 for the line and 0 for space. In ╲ the line is on the pixels where the row and the column are the same (i == j): top-left, middle, bottom-right. In ╱ they add up to 2 (i + j == 2): top-right, middle, bottom-left.

show_grid is part of the page’s own pixels module: it draws a list of rows of numbers as squares. (On your own computer you would use a library such as Pillow.)

import randomfrom pixels import show_grid def make_maze(rows, cols):    maze = []    for r in range(rows):        line = ''        for c in range(cols):            line = line + random.choice('╱╲')        maze.append(line)    return maze def to_picture(maze):    # each square becomes 3 × 3 pixels: 1 for the line, 0 for space    picture = []    for line in maze:        for i in range(3):            # the square's 3 rows of pixels            row = []            for tile in line:                for j in range(3):    # and its 3 columns                    if tile == '╱' and i + j == 2:                        row.append(1)                    elif tile == '╲' and i == j:                        row.append(1)                    else:                        row.append(0)            picture.append(row)    return picture random.seed(10)maze = make_maze(10, 16)for line in maze[:3]:    print(line)picture = to_picture(maze)print('The picture is', len(picture[0]), 'pixels across and', len(picture), 'down')show_grid(picture, ['white', 'navy'])

╱╲╲╱╱╲╲╲╱╱╲╲╱╱╲╱╲╱╲╲╲╲╲╲╱╲╲╱╲╱╲╲╱╱╱╱╱╲╲╱╲╲╲╲╱╲╱╱The picture is 48 pixels across and 30 down

Picture

The lines are now pixels that touch corner to corner, so the walls join as they do on the Commodore’s screen.

Step 3: pour water in

Now the water. Every space (0) on the left edge gets wet (2). Then, round by round, every space next to the newest water gets wet: above, below, left or right, never across a corner, because two pixels of a line that touch only at their corners still make a wall. When a round wets nothing new, the water has gone everywhere it can. Every three rounds the program keeps a picture, so you can watch it spread.

import randomfrom pixels import show_frames def make_maze(rows, cols):    maze = []    for r in range(rows):        line = ''        for c in range(cols):            line = line + random.choice('╱╲')        maze.append(line)    return maze def to_picture(maze):    picture = []    for line in maze:        for i in range(3):            row = []            for tile in line:                for j in range(3):                    if tile == '╱' and i + j == 2:                        row.append(1)                    elif tile == '╲' and i == j:                        row.append(1)                    else:                        row.append(0)            picture.append(row)    return picture random.seed(32)picture = to_picture(make_maze(10, 10))height = len(picture)width = len(picture[0]) # water (2) comes in at every space on the left sidenewest = []for r in range(height):    if picture[r][0] == 0:        picture[r][0] = 2        newest.append([r, 0]) frames = []rounds = 0while len(newest) > 0:    # each round, every space next to the newest water gets wet    wet_now = []    for p in newest:        r = p[0]        c = p[1]        for n in [[r, c + 1], [r + 1, c], [r, c - 1], [r - 1, c]]:            if 0 <= n[0] < height and 0 <= n[1] < width:                if picture[n[0]][n[1]] == 0:                    picture[n[0]][n[1]] = 2                    wet_now.append(n)    newest = wet_now    rounds = rounds + 1    if rounds % 3 == 0 or len(newest) == 0:        copy = []        for row in picture:            copy.append(row[:])        frames.append(copy) through = Falsefor r in range(height):    if picture[r][width - 1] == 2:        through = Trueprint('The water spread for', rounds, 'rounds.')print('Did it get across to the right side?', through)show_frames(frames, ['white', 'navy', 'skyblue'])

The water spread for 109 rounds.Did it get across to the right side? True

Picture

Press Run, then Play under the picture. This maze (seed 32) has a way through, but only just: the water winds for 109 rounds before it gets out. Now change the seed to 1, 2 or 3 and run it again.

(row[:] makes a copy of a row. Without the copies, every picture in frames would be the same list, changed to the very last state.)

Step 4: a thousand pours

A program can do in a second what would take you an afternoon with the widget. Step 3’s pouring goes into a function, way_through(maze), which gives back True or False. Then the program pours water into hundreds of mazes of three sizes, and into some wide ones.

import random def make_maze(rows, cols):    maze = []    for r in range(rows):        line = ''        for c in range(cols):            line = line + random.choice('╱╲')        maze.append(line)    return maze def to_picture(maze):    picture = []    for line in maze:        for i in range(3):            row = []            for tile in line:                for j in range(3):                    if tile == '╱' and i + j == 2:                        row.append(1)                    elif tile == '╲' and i == j:                        row.append(1)                    else:                        row.append(0)            picture.append(row)    return picture def way_through(maze):    # pour water in on the left; True if it reaches the right side    picture = to_picture(maze)    height = len(picture)    width = len(picture[0])    newest = []    for r in range(height):        if picture[r][0] == 0:            picture[r][0] = 2            newest.append([r, 0])    while len(newest) > 0:        wet_now = []        for p in newest:            r = p[0]            c = p[1]            for n in [[r, c + 1], [r + 1, c], [r, c - 1], [r - 1, c]]:                if 0 <= n[0] < height and 0 <= n[1] < width:                    if picture[n[0]][n[1]] == 0:                        picture[n[0]][n[1]] = 2                        wet_now.append(n)        newest = wet_now    for r in range(height):        if picture[r][width - 1] == 2:            return True    return False random.seed(1)for size in [5, 10, 20]:    tries = 500    if size == 20:        tries = 200    count = 0    for t in range(tries):        if way_through(make_maze(size, size)):            count = count + 1    print(size, 'by', size, ':', count, 'of', tries, 'mazes have a way through') count = 0for t in range(200):    if way_through(make_maze(10, 30)):        count = count + 1print('10 rows of 30 squares:', count, 'of 200 have a way across')

5 by 5 : 106 of 500 mazes have a way through10 by 10 : 86 of 500 mazes have a way through20 by 20 : 38 of 200 mazes have a way through10 rows of 30 squares: 0 of 200 have a way across

It takes a few seconds on a phone: it pours water into 1,400 mazes.

• Most of these mazes have no way through. In square mazes, only about 1 in 5 does.
• The size of the square hardly matters. A 20 by 20 maze has four times as many squares as a 10 by 10 one, yet again about 1 in 5 had a way through. Bigger mazes have more places for a wall to cross, but a wall needs to be longer too, and the two balance out.
• A wide maze is almost never crossed. In 200 mazes of 10 rows and 30 squares, the water never once got from the left side to the right.

So one random choice can draw a pattern that looks just like a maze, but it isn’t a puzzle anyone could solve: most of the time there is no way through, and it is full of rooms with no doors. A real maze needs a plan, and a program can make one, but with a different rule (see Where to go next).

In 1987 the metallurgist and historian of science Cyril Stanley Smith drew Truchet’s tiles in another way: two quarter circles in each square, joining the middles of neighboring sides. There are again only two ways to turn the tile, so one coin toss a square still decides everything. Try it, and pour water into it.

• a.With arcs, the lines no longer have corners. What do they look like now?
• b.Does the water get through the arcs more often or less often than through the lines?

A maze with a way through, every time. Could you change the program so it always makes a maze with a way through? One way: make a maze, pour water, and if it doesn’t get through, make another. How many tries does that take on average? A cleverer way builds the maze from the start so that every room is joined to every other by exactly one path: that is a perfect maze, and it is the topic How do games build a new maze every time? in Grades 9–12.

Bigger and bigger. Your program found about 1 in 5 for square mazes of three sizes. Try 40 by 40 (use fewer tries: it takes longer). Does it stay near 1 in 5? A maze twice as wide as it is tall almost never had a way across; what about one twice as tall as it is wide?

★ Pieces of wall in one row (blocks)

A row of 8 squares is typed in, one square at a time: 1 for ╱, 2 for ╲. The program should say how many separate pieces of wall the row has. Two neighbors that are different (╱╲ or ╲╱) touch, so they are one piece; two the same (╱╱ or ╲╲) are two pieces. Add the blocks it needs, then press Test.

★★ Count the diamonds (Python, from Grade 8)

A diamond is four squares in a 2 by 2 block: ╱╲ on top of ╲╱. Write diamonds(maze) that gives back how many diamonds a maze has. The maze is a list of strings, as in Step 2.

def diamonds(maze):    # maze is a list of strings of '╱' and '╲'    return 0 print(diamonds(['╱╲', '╲╱']))

★★★ Rooms with no door (Python, from Grade 8)

A closed room is a passage that doesn’t touch any side of the maze, so water poured in from outside can never reach it. Write closed_rooms(maze) that counts them. The starting program has Step 2’s to_picture.

def to_picture(maze):    picture = []    for line in maze:        for i in range(3):            row = []            for tile in line:                for j in range(3):                    if tile == '╱' and i + j == 2:                        row.append(1)                    elif tile == '╲' and i == j:                        row.append(1)                    else:                        row.append(0)            picture.append(row)    return picture def closed_rooms(maze):    picture = to_picture(maze)    return 0 print(closed_rooms(['╱╲', '╲╱']))

• Grade 6, Pen up, pen down: moving the turtle without drawing.
• Grade 7, A scoring game: the random number block.
• Grade 10, Painting a picture, ring by ring: the water’s rounds are breadth-first search.
• Can a robot get out of any maze? One rule, followed without a map, gets a robot out of almost any maze. Try it on a maze that has a way out.
• How do games build a new maze every time? Random choices again, but with a rule that never closes a loop, so there is always exactly one way through.
• Why does a turtle’s star close up? Turn the same angle again and again: sometimes the turtle comes home with a star, sometimes it never does. (Coming soon.)