Can You Cross the River with the Tiger, the Goat and the Grass?

The first crossing

Press Start again and look at the first crossing. The farmer can cross alone, or take the tiger, the goat or the grass.

The trick

After the goat is across, the farmer rows back alone. Now he can take the tiger or the grass. Say he takes the tiger. On the far bank, the tiger and the goat are together. The farmer can’t leave them there, and he can’t take both back. What can he do?

Build the map

Every time the four are on the banks in a new way, that is a new position. Here is the puzzle again with a map under it. Each time you reach a safe position for the first time, its card appears on the map. Each crossing you make between two positions draws a line between their cards.

A position in four letters

To give a position to a computer, write it in four letters, in a fixed order: the farmer, the tiger, the goat and the grass. Each letter is L if that one is on the left bank, where they start, or R if it is on the right bank. The boat is always with the farmer, so it needs no letter.

A position is safe unless the goat has the same letter as the tiger (or the grass) and the farmer has the other letter. In RLLL the farmer is across alone, and the tiger, the goat and the grass are left together: not safe.

A map of positions

Now draw every safe position as a dot (a card, in the widget) and every crossing as a line joining two dots. A crossing changes the farmer’s letter, and the letter of at most one other, which must have been on the farmer’s bank. This drawing is the map you built:

Look at its shape. From the start there is only one line out, to RLRL (the goat crosses), and one line on, to LLRL (the farmer comes back). Then the map splits into a ring of six: going round it one way, the tiger crosses next; the other way, the grass. Both ways meet again at RRLR, and from there one line leads to LRLR and one more to the goal. Every way across must go from LLLL to RRRR along these lines.

So the puzzle has become a question about a map: is there a path from the start to the goal, and which is the shortest? Count the lines along either side of the ring: 2 to reach the ring, 3 round it, 2 more to the goal. 7 crossings, and no path is shorter.

In computing, each position is called a state, and the map of every state and every move between them is a state graph: dots (states) joined by lines (moves). You will meet graphs again in Grade 10, with towns as dots and roads as lines.

Searching the map, ring by ring

For a map of 10 dots you can find the path by looking. A computer can’t look; it must search. Here is a way that never misses the shortest path. Start at LLLL and call it ring 0. Every position one crossing away that you haven’t seen is ring 1. Every position one crossing from ring 1, not seen yet, is ring 2. Keep going, like ripples spreading out from a stone dropped in a pond, until the goal turns up. Its ring number is the fewest crossings, because a position is always reached first in the smallest ring it can be in.

This is called breadth-first search: search the whole width of one ring before moving on to the next.

With blocks: is the bank safe?

Before a computer can search, it needs the rules. Think about the bank the farmer has just left. Make three true-or-false variables: tiger is true if the tiger is on that bank, goat if the goat is, grass if the grass is. Then trouble should be true when someone will be eaten.

The program below only knows half the rule: it says there is trouble when the tiger and the goat are both there. The table under it runs the program for all 8 ways of setting the three variables and marks each row against what it should be.

In Python (from Grade 8): every safe position

Now the same rule in Python, for a whole position. In Python, the letters of a piece of text can be read by their places like the items of a list: if pos is 'RLRL', then pos[0] is 'R' (the farmer), pos[1] is 'L' (the tiger), and so on. Joining text with + builds a position from its four letters.

The program tries all 16 positions with four loops, one inside the other, and keeps the safe ones in a list. safe.append(pos) adds pos to the end of the list safe.

def is_safe(pos):    farmer = pos[0]    tiger = pos[1]    goat = pos[2]    grass = pos[3]    if goat == tiger and farmer != goat:        return False    if goat == grass and farmer != goat:        return False    return True safe = []for farmer in 'LR':    for tiger in 'LR':        for goat in 'LR':            for grass in 'LR':                pos = farmer + tiger + goat + grass                if is_safe(pos):                    safe.append(pos)                else:                    print(pos, 'someone gets eaten')print(len(safe), 'safe positions:')print(safe)

LLRR someone gets eatenLRRL someone gets eatenLRRR someone gets eatenRLLL someone gets eatenRLLR someone gets eatenRRLL someone gets eaten10 safe positions:['LLLL', 'LLLR', 'LLRL', 'LRLL', 'LRLR', 'RLRL', 'RLRR', 'RRLR', 'RRRL', 'RRRR']

for farmer in 'LR' runs twice, once with 'L' and once with 'R': a loop over text goes through its letters. Four loops inside each other make 2 × 2 × 2 × 2 = 16 positions.

The crossings

Next, the lines of the map. can_cross(a, b) says whether one crossing takes position a to position b. The farmer must change banks (he rows). Every other letter that changes must have been on the farmer’s bank, and at most room of them may change, because that is all the boat holds.

def is_safe(pos):    farmer = pos[0]    tiger = pos[1]    goat = pos[2]    grass = pos[3]    if goat == tiger and farmer != goat:        return False    if goat == grass and farmer != goat:        return False    return True def can_cross(a, b):    if a[0] == b[0]:        return False    moved = 0    for i in range(1, 4):        if a[i] != b[i]:            if a[i] != a[0]:                return False            moved = moved + 1    return moved <= room room = 1safe = []for farmer in 'LR':    for tiger in 'LR':        for goat in 'LR':            for grass in 'LR':                pos = farmer + tiger + goat + grass                if is_safe(pos):                    safe.append(pos) lines = 0for i in range(len(safe)):    for j in range(i + 1, len(safe)):        if can_cross(safe[i], safe[j]):            print(safe[i], '-', safe[j])            lines = lines + 1print(lines, 'crossings on the map')

LLLL - RLRLLLLR - RLRRLLLR - RRLRLLRL - RLRLLLRL - RLRRLLRL - RRRLLRLL - RRLRLRLL - RRRLLRLR - RRLRLRLR - RRRR10 crossings on the map

The loop over j starts at i + 1, so each pair of positions is looked at once: a crossing can go either way, so LLLL - RLRL and RLRL - LLLL are the same line. Check a few against the map above.

Search, ring by ring

Now the search. seen is the list of every position found so far, and ring the positions found in the last ring. Each time round the while loop, the program looks at every position in ring and every safe position it can cross to; one not seen before goes into next_ring. Then next_ring becomes the ring, and the count goes up by one. b not in seen is True when b isn’t in the list seen.

def is_safe(pos):    farmer = pos[0]    tiger = pos[1]    goat = pos[2]    grass = pos[3]    if goat == tiger and farmer != goat:        return False    if goat == grass and farmer != goat:        return False    return True def can_cross(a, b):    if a[0] == b[0]:        return False    moved = 0    for i in range(1, 4):        if a[i] != b[i]:            if a[i] != a[0]:                return False            moved = moved + 1    return moved <= room room = 1safe = []for farmer in 'LR':    for tiger in 'LR':        for goat in 'LR':            for grass in 'LR':                pos = farmer + tiger + goat + grass                if is_safe(pos):                    safe.append(pos) seen = ['LLLL']ring = ['LLLL']crossings = 0while 'RRRR' not in seen and len(ring) > 0:    next_ring = []    for a in ring:        for b in safe:            if can_cross(a, b) and b not in seen:                seen.append(b)                next_ring.append(b)    ring = next_ring    crossings = crossings + 1    print('Ring', crossings, ring)if 'RRRR' in seen:    print('Everyone across in', crossings, 'crossings')else:    print('No way across')

Ring 1 ['RLRL']Ring 2 ['LLRL']Ring 3 ['RLRR', 'RRRL']Ring 4 ['LLLR', 'LRLL']Ring 5 ['RRLR']Ring 6 ['LRLR']Ring 7 ['RRRR']Everyone across in 7 crossings

len(ring) > 0 stops the loop if a ring comes out empty: then every position that can be reached has been seen, and the goal isn’t among them.

Now change one number: room = 1 to room = 2, a boat for the farmer and two more, and run it again.

• Only 10 of the 16 positions are safe, and only 10 crossings join them. That small map is the whole puzzle: anything you could do with the boat is a walk along its lines.
• The goal is in ring 7. No path is shorter, and your program knows it without trying every possible order of crossings, of which there are endless many (you can go round the ring of six as often as you like).
• Ring 3 has two positions, and ring 4 two. That is the ring of six: two shortest ways across, mirror images of each other, one where the tiger crosses before the grass and one where the grass crosses first. In both, the goat crosses three times.
• With a boat for two, your program says 3 crossings: the farmer takes the tiger and the grass, comes back alone, and takes the goat. A bigger boat makes a different map, and the same program solved it without a single change to the search.

That last point is the big idea. The program never used the words tiger, goat or grass in its search. It needs only three things: a way to write a state (four letters), a rule for which states are allowed (is_safe) and a rule for moves (can_cross). Change those, and the same search solves a different puzzle. Computers plan a robot’s movements and find routes on maps the same way: a graph of states, then a search.

Change the puzzle. Add a fifth one to the farmer’s load, a dog that chases the goat but not the tiger. Change is_safe and the loops (five letters now) and run the search. How many safe positions are there, and can it be done with a boat for one? With a boat for two?

Three goats and three tigers. Six animals must cross in a boat that holds two, and any animal can row. If on either bank there are goats and more tigers than goats, the tigers eat them. This is Amarel’s puzzle in a new coat. A state needs only three things: how many goats and how many tigers are on the left bank, and which bank the boat is on. ★★★ below asks you to search it.

The smallest boat. Give the farmer more things, with a list of who eats whom, and ask: how big must the boat be? Mathematicians call that size the puzzle’s Alcuin number. For a few things your search finds it at once. For hundreds, no one knows a fast way: finding the Alcuin number has been proved to be among the hardest kind of problems a computer can be asked (it is NP-hard), where every method known slows down enormously as the puzzle grows.

★ The ferry judge (blocks)

The program below asks which bank each of the four is on, L or R. Finish it so that it says The tiger eats the goat, The goat eats the grass or Safe. If both could happen (the goat left with the tiger and the grass), say the tiger one. Then press Test.

★★ Show me the way (Python, from Grade 8)

Write route(start, goal) that gives back the list of positions on a shortest way from start to goal, both included, or None if there is no way (for example, if goal isn’t safe). The ring search found how many crossings; now it must remember where each position came from.

def route(start, goal):    # a list of positions from start to goal, or None    return None print(route('LLLL', 'RRRR'))

★★★ Three goats and three tigers (Python, from Grade 8)

n goats and n tigers are on the left bank with a boat that holds room animals. Any animal can row, but the boat can’t cross empty. After every crossing, on each bank, if there is at least one goat there must be at least as many goats as tigers. Write fewest_crossings(n, room) that gives back the fewest crossings that get them all to the right bank, or None if it can’t be done.

A state is a list of three things: goats on the left bank, tigers on the left bank, and the boat’s bank, 'L' or 'R'. The start is [n, n, 'L'].

def fewest_crossings(n, room):    # search the states ring by ring, from [n, n, 'L']    return None print(fewest_crossings(3, 2))

• Grade 7, True or False: Logic: and, or and not, which make the safety rule.
• Grade 8, Searching and Sorting: lists, which hold the positions seen.
• Grade 10, Graphs: Maps, Routes and Networks: breadth-first search on a map of real towns, and the shortest route between them.
• How do you find the fake coin in three weighings? Another puzzle solved by listing every case a program can check.
• Can a robot get out of any maze? A maze is a graph too: its squares are the states.
• Can four colors paint any map of Nepal? Another graph, with districts as dots and borders as lines.