Moving Counter Problems

Every puzzle in this chapter is a set of counters and a rule for moving them, with a target position and, usually, a demand for the fewest moves. That is the kind of question a patient machine answers completely. Start from the given position, list every position one move away, then every position two moves away that has not been seen, and so on; the first time the target appears, its distance is the fewest possible, and no cleverer route can exist, because every route has been counted. Where the positions are few enough this settles Dudeney’s claims outright, and often counts his rivals too.

A few puzzles are too large for that, or are not about fewest moves at all, and for those the answers say what was checked and how.

No. 214. The Six Frogs

No. 215. The Grasshopper Puzzle

No. 216. The Educated Frogs

No. 217. The Twickenham Puzzle

No. 218. The Victoria Cross Puzzle

No. 219. The Letter Block Puzzle

No. 220. A Lodging-House Difficulty

No. 221. The Eight Engines

No. 222. A Railway Puzzle

No. 223. A Railway Muddle

No. 224. The Motor-Garage Puzzle

No. 225. The Ten Prisoners

No. 226. Round the Coast

No. 227. Central Solitaire

No. 228. The Ten Apples

No. 229. The Nine Almonds

No. 230. The Twelve Pennies

No. 231. Plates and Coins

No. 232. Catching the Mice

No. 233. The Eccentric Cheesemonger

No. 234. The Exchange Puzzle

No. 235. Torpedo Practice

No. 236. The Hat Puzzle

No. 237. Boys and Girls

No. 238. Arranging the Jampots

The Six Frogs

Watch the empty square rather than the frogs. In the shortest play it sweeps along the row a leap at a time, from one end to the other, and turns round at each end with a single step; every leap carries one frog past another, and the steps only turn the sweep. Move the frogs in the order 2, 4, 6, 5, 3, 1, three times over, then 2, 4, 6: twenty-one moves. Each frog has only one possible move at any time, so naming the frog names the move.

Dudeney’s general rule is that $n$ frogs need $\tfrac12(n^2 + n)$ moves when $n$ is even and $\tfrac12(n^2 + 3n) - 4$ when $n$ is odd. For the even case, write the even numbers up and the odd numbers down, repeat that $\tfrac12 n$ times, and finish with the even numbers up once more; for fourteen frogs this gives 105 moves. The odd case is a little more intricate: for eleven frogs, $2, 4, \ldots, 10, 11, 9, \ldots, 1$ five times, then $2, 4, 6, 8, 11, 9, 7, 5, 3$, then $2$ to $10$ in order, 73 moves in all.

A complete search of every position confirms that his formula gives the fewest moves for every number of frogs from two to nine, and his recipe, played out, is legal and exactly that long for every number from two to fourteen.

He calls this complete general solution “published here for the first time.”

Answer Twenty-one moves; $\tfrac12(n^2+n)$ for $n$ even, $\tfrac12(n^2+3n)-4$ for $n$ odd

The Grasshopper Puzzle

Replay the proposed moves first, then separate the construction from the claim that it is shortest. Dudeney reverses the twelve grasshoppers in forty-four moves: 12, 1, 3, 2, 12, 11, 1, 3, 2, then 5, 7, 9, 10, 8, 6, 4 four times over, then 3, 2, 12, 11, 2, 1, 2. The program plays it through and the grasshoppers end reversed.

He gives a general answer. Two, three and four grasshoppers need 3, 3 and 6 moves; beyond that, $m$ grasshoppers need $\tfrac14(m^2 + 4m - 16)$ moves when $m$ is even and $\tfrac14(m^2 + 6m - 31)$ when it is odd. For twelve that is 44. A complete search confirms the formula for every number from two to eleven.

Twelve grasshoppers have 6.2 billion positions, and that search has not been run here, so for twelve the formula and the forty-four moves are Dudeney’s, with every smaller case behind them.

Answer Forty-four moves

The Educated Frogs

This is a puzzle of order rather than principle, and the tool that makes ten jumps possible is the long jump over two frogs: five of the ten below use it. Jump 2 to 1, 5 to 2, 3 to 5, 6 to 3, 7 to 6, 4 to 7, 1 to 4, 3 to 1, 6 to 3, 7 to 6. A search of every position shows that ten jumps is the fewest, and that there are just two ways of doing it in ten.

Answer 2–1, 5–2, 3–5, 6–3, 7–6, 4–7, 1–4, 3–1, 6–3, 7–6

The Twickenham Puzzle

Black counters go only clockwise and white only anticlockwise, so no counter can ever undo a move; the puzzle is to find an order in which the gap is always where the next counter needs it, and only a search can say how short that order can be. Play the counters in this order: K C E K W T C E H M K W T A N C E H M I K C E H M T. The position always settles whether a counter steps or leaps. Twenty-six moves is the fewest, and the search finds that this is the only way to do it in twenty-six.

Answer K C E K W T C E H M K W T A N C E H M I K C E H M T

The Victoria Cross Puzzle

The word could not be made to read round with the V moved one place if every letter were different: the two I’s must change places, the first travelling to the seventh place and the second to the second. Moving the letters in the order of the words “A VICTOR! A VICTOR! A VICTOR I!” solves it in twenty-two moves, and the program confirms that this works.

The fewest moves is eighteen, and a search of every position finds exactly six solutions of that length, as Dudeney says. One of them, the two I’s being numbered by their starting places, is I(1), V, A, I(2), R, O, T, I(1), I(2), A, V, I(2), I(1), C, I(2), V, A, I(1). His remarks about all six hold: C, T, O and R each move once, one of the I’s moves four times, and the V always ends on the right arm of the cross.

Answer Eighteen moves, in just six ways

The Letter Block Puzzle

Here there is no shortcut: the box is a small cousin of the fifteen puzzle, and the fewest moves can only be found by trying them. Move the blocks A, B, F, E, C, A, B, F, E, C, A, B, D, H, G, A, B, D, H, G, D, E, F. Twenty-three moves is the fewest, and a search of all the positions finds that this is the only way to do it in twenty-three.

Answer Twenty-three moves, in one way only

A Lodging-House Difficulty

Move piano, bookcase, wardrobe, piano, cabinet, chest of drawers, piano, wardrobe, bookcase, cabinet, wardrobe, piano, chest of drawers, wardrobe, cabinet, bookcase, piano: seventeen removals. That is the fewest, and there are two ways of doing it in seventeen.

Dudeney adds that the landlady could then move the chest, the wardrobe and the cabinet back, leaving only the wardrobe and the chest of drawers exchanged, which Mr Dobson did not mind. He could not have had everything else back in place. Colour the rooms like a chessboard; the empty room changes colour at every removal, so it can return to room 2 only after an even number of removals. Each removal swaps a piece with the gap, and an even number of swaps can never add up to a single exchange of two pieces. Some other pair must be exchanged too.

Answer Seventeen removals

The Eight Engines

The question hides a second one: which engine can be left out of the play at all. The only way to answer it is to try each engine as the fixed one and search for the fewest moves. The engine that cannot move is No. 5. Move the others in the order 7, 6, 3, 7, 6, 1, 2, 4, 1, 3, 8, 1, 3, 2, 4, 3, 2, and the engines stand in order round the circle with the middle empty. A search finds that with No. 5 fixed there are just three ways in seventeen moves, Dudeney’s and the “two other slightly different solutions” he mentions. No other engine will do: with No. 2 fixed the fewest is nineteen, with No. 8 twenty-five, with No. 3 twenty-three, and with any of the rest it cannot be done.

Answer No. 5 stays; seventeen moves

A Railway Puzzle

With nine engines on ten places there is only ever one empty place, so every move fills it and opens another, and a search of every position settles how few will do. Nine moves: from 9 to 10, 6 to 9, 5 to 6, 2 to 5, 1 to 2, 7 to 1, 8 to 7, 9 to 8 and 10 to 9. A search confirms that nine is the fewest and that this is the only way to do it in nine.

Answer Nine moves

A Railway Muddle

Dudeney needs six reversals. The train going from A to D is divided into three parts: the engine with seven wagons, eight wagons, and one wagon. The other train never uncouples. The black train runs forward past the loop, then backs, leaving the eight wagons on the loop, and the white engine goes on towards D with its seven (the first reversal). The black train returns to fetch the single wagon (the second), pushes the eight off the loop and leaves the single wagon there, going on its way (the third and fourth). The white train then backs onto the loop, picks up the single wagon and goes right away to D (the fifth and sixth).

A program replayed these moves on a plain model of the line: a loop whose sides each hold eight vehicles, single line beyond it at both ends, an engine moving only what is coupled to it, and nothing allowed to run into or through anything else. Every move is legal, both trains leave with their engines in front, and the black engine reverses four times and the white twice. The loop’s size matters: with room for only seven, the white engine and its seven wagons would stick out past B, and the black train could not get by. The replay confirms that six reversals suffice. That six is the fewest, as Dudeney claims, it does not show.

Answer Six reversals

The Motor-Garage Puzzle

Each car must cross from one row to the other, and the cars can only pass one another in the few spare squares, so the puzzle is one of traffic; the fewest moves comes only from a search. Forty-three moves: 6–G, 2–B, 1–E, 3–H, 4–I, 3–L, 6–K, 4–G, 1–I, 2–J, 5–H, 4–A, 7–F, 8–E, 4–D, 8–C, 7–A, 8–G, 5–C, 2–B, 1–E, 8–I, 1–G, 2–J, 7–H, 1–A, 7–G, 2–B, 6–E, 3–H, 8–L, 3–I, 7–K, 3–G, 6–I, 2–J, 5–H, 3–C, 5–G, 2–B, 6–E, 5–I, 6–J. Here “6–G” means that car 6 goes to square G.

The garage has almost twenty million positions, and a complete search confirms that forty-three is the fewest. Dudeney says there are other ways in forty-three; there are 99,264 sequences of that length.

Answer Forty-three moves

The Ten Prisoners

Move the four men as the arrows show.

That gives sixteen even rows: all four across, all four down, five diagonals one way and three the other. A program tried every placing of ten men in the sixteen cells. At the start there are twelve even rows, as Dudeney says, and sixteen is the most possible, reached by just four arrangements. Only one of them keeps the corner man and moves no more than four, and it is this one.

Answer Move the four men as shown

Round the Coast

The word must have repeated letters in the right places, because a letter can then be written in a circle belonging to its twin. The answer is “Swansea”, whose first and fifth letters are the same and whose third and seventh are the same: 2–5, 7–2, 4–7, 1–4, 6–1, 3–6, 8–3, the first number in each pair being the circle touched and the second the circle written in.

A program tried every order of writing. No word of seven different letters can be placed, nor one with a single repeated pair, which is the trouble with “Glasgow”. With two repeated pairs, just three patterns work: the first letter repeated as the fifth and the third as the seventh, as in Swansea; the second as the fourth and the third as the seventh, as in Dudeney’s other example, “Tarapur”; and the second as the sixth and the fifth as the seventh, which he does not mention. He believed Swansea to be the only port that fits.

Answer Swansea

Central Solitaire

Dudeney’s solution takes nineteen moves: 19–17, 16–18, (29–17, 17–19), 30–18, 27–25, (22–24, 24–26), 31–23, (4–16, 16–28), 7–9, 10–8, 12–10, 3–11, 18–6, (1–3, 3–11), (13–27, 27–25), (21–7, 7–9), (33–31, 31–23), (10–8, 8–22, 22–24, 24–26, 26–12, 12–10), 5–17. The jumps in brackets make one move. The program plays it and the last counter stands in the centre.

“I do not think the number of moves can be reduced,” he wrote. It can, by one. Ernest Bergholt published an eighteen-move solution in 1912, and John Beasley proved in 1964 that eighteen cannot be beaten.

In the numbering here Bergholt’s moves are 5–17, 8–10, 1–9, 16–4, 11–9, 28–16, 21–23, 24–22, 13–11, (7–21, 21–23), (26–24, 24–22, 22–8, 8–10, 10–12), 33–25, 18–30, (27–13, 13–11), (31–33, 33–25), (3–1, 1–9, 9–23), (6–18, 18–16, 16–28, 28–30, 30–18), 19–17.

The program plays these too, and they finish in the centre.

Answer Nineteen by Dudeney; eighteen is the fewest possible

The Ten Apples

Number the plates 1 to 16 in rows from the top. The apples stand on the border plates except 14 and 15. Move the apple from 8 to 10 and jump 9–11, 1–9, 13–5, 16–8, 4–12, 12–10, 3–1, 1–9, 9–11, leaving one apple, on plate 11. A program tried every first transfer and every sequence of jumps. Eight transfers lead to a clearance, in four mirror-image pairs: 2 to 7 or 3 to 6, 8 to 10 or 5 to 11, 13 to 10 or 16 to 11, 13 to 11 or 16 to 10.

Answer Move 8 to 10, then nine jumps

The Nine Almonds

The almond that ends in the centre starts there too, so let it do most of the work: one long run of jumps clears half the board in a single move. Four moves: 5 over 8, 9, 3 and 1; 7 over 4; 6 over 2 and 7; 5 over 6. Almond 5 is left alone on the centre square where it began. A search of every position confirms that four moves is the fewest.

Answer Four moves

The Twelve Pennies

Six moves must make six pairs, so every move puts a single penny on another single one and no pair is ever disturbed; the art is to leave the single pennies spaced so that the later moves still have two coins to pass over. Move 12 to 3, 7 to 4, 10 to 6, 8 to 1, 9 to 5 and 11 to 2. This is, as Dudeney says, one of several solutions: a program finds twelve ways of making the six pairs on places 1 to 6, among 14,592 six-move sequences that pair all twelve pennies somewhere.

Answer 12–3, 7–4, 10–6, 8–1, 9–5, 11–2

Plates and Coins

The hand may only go forwards, so every pass round the table costs a revolution, and the question is how many coins can be paired on each pass. Number the plates 1 to 12 in the direction of travel and start at 1: move the coin in 1 to 4, 5 to 8, 9 to 12, 3 to 6, 7 to 10 and 11 to 2, then go on round to 1. That takes three revolutions. Or start at 4: 4 to 7, 8 to 11, 12 to 3, 2 to 5, 6 to 9, 10 to 1. A program tried every starting plate and every choice of moves; three revolutions is the fewest, and there are 324 ways to do it in three, Dudeney’s two among them.

Answer Three revolutions

Catching the Mice

Number the mice in the direction the cat goes, the white mouse being 1. Counting by thirteen, the cat must start at mouse 7, and the program confirms that no other start works. Dudeney points out that no trial is needed: start anywhere, see where the last mouse eaten stands, and shift the start to match.

Starting at the white mouse, the smallest count that eats it last is 21, and the smallest that makes it the third eaten is 100. Dudeney adds that 1,000 also works, and that seventy-two numbers between them do so as well; the program confirms both. Any multiple of 360,360, the least common multiple of 1 to 13, simply eats the mice from the thirteenth backwards.

Answer Start at mouse 7; count 21; count 100

The Eccentric Cheesemonger

The numbers are the cheeses, and “7–2” puts cheese 7 on cheese 2. For piles on 1, 2, 15 and 16: 7–2, 8–7, 9–8, 10–15, 6–10, 5–6, 14–16, 13–14, 12–13, 3–1, 4–3, 11–4. For three piles on 13, 14 and 15: 9–4, 10–9, 11–10, 6–14, 5–6, 12–15, 8–12, 7–8, 16–5, 3–13, 2–3, 1–2, the fourth pile ending on 4. For piles on 3, 5, 12 and 14: 8–3, 9–14, 16–12, 1–5, 10–9, 7–10, 11–8, 2–1, 4–16, 13–2, 6–11, 15–4. The program checks every move carries a single cheese over exactly four others, and that each game ends with four piles of four where stated.

Answer The three games above

The Exchange Puzzle

The fourteen lines of the diagram join exactly the pairs of places a knight’s move apart on a board of three rows of four, and every exchange moves one black counter and one white counter one knight’s move each. The black counters have to travel seventeen knight’s moves in all to reach their places, so seventeen exchanges is the least possible; the white counters need only eleven, and waste the rest. Seventeen are enough: H–K, H–E, H–C, H–A, I–L, I–F, I–D, K–L, G–J, J–A, F–K, L–E, D–K, E–F, E–D, E–B, B–K. This is Dudeney’s argument, and the program checks both the distances and the exchanges.

Answer Seventeen exchanges

Torpedo Practice

Anchor the fleet as shown, on the points of a lattice, and fire the torpedoes in the order numbered; each numbered ship is the one sunk by that torpedo.

Ten ships go down. Taken literally, though, Dudeney’s rule is broken by his own answer: torpedoes 2 and 7 travel in the same direction along parallel lines, so do 4 and 10, and 1 and 2 run along one line from opposite ends. What his answer does keep is that no two torpedoes follow the same course, the same line in the same direction, and that is enough to rule out his thirteen ships in a row. Under that reading a program that tried every order of firing finds ten to be the most this fleet allows. If every direction must really differ, the same fleet gives only eight.

Answer Ten ships

The Hat Puzzle

Using S for silk and F for felt, move the pairs on pegs 2–3, 7–8, 4–5, 10–11 and 1–2:

Dudeney says there are other ways. There are not, in five moves: a complete search finds that this is the only one. There are forty-one ways in six moves.

Answer Move the pairs from pegs 2, 7, 4, 10 and 1

Boys and Girls

Each line shows the chairs after one move, a dot being an empty chair:

There are thirteen solutions in five moves, and five is the fewest. Dudeney’s remark that any neighbouring pair except 7–8 may be moved first is exactly right: the first move can be 1–2, 2–3, 3–4, 4–5, 5–6 or 6–7.

Answer Five moves, as shown

Arranging the Jampots

Pots 13 and 19 are already in place, so twenty-two exchanges would certainly do, one pot put right each time. But the others fall into closed groups, each a set of pots that must go round among themselves: the pots on the holes of 1, 2, 3; of 4, 15, 16; of 7, 17, 20; of 10, 11, 12, 24; and the nine on the holes of 5, 6, 8, 9, 14, 18, 21, 22, 23. A group of $k$ pots needs $k - 1$ exchanges, and no exchange can do better than split a group in two, so the fewest is $22 - 5 = 17$. In Dudeney’s order: 3–1, 2–3; 15–4, 16–15; 17–7, 20–17; 24–10, 11–24, 12–11; 8–5, 6–8, 21–6, 23–21, 22–23, 14–22, 9–14, 18–9.

Answer Seventeen exchanges