Frogs and Toads Change Places

  • Hard
  • River crossing puzzles
  • Tests: Counting slides and jumps separately

The puzzle

Seven stones lie in a row. Three frogs occupy the left three, facing right; three toads occupy the right three, facing left; the middle stone is empty. A creature may step forward onto the empty stone, or jump forward over exactly one creature onto the empty stone. Nothing ever moves backwards.

The frogs and toads must end up having swapped sides. What is the fewest moves?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Every frog must end up past every toad, and only a jump moves a frog past a toad.

Hint 2

So the jumps are forced in number. Count them, then count the slides.

Show the answer Hide the answer

Fifteen moves: nine jumps and six slides.

How to get there

Each of the three frogs must get past each of the three toads, and the only move that takes one creature past another is a jump. So there are exactly 3 x 3 = 9 jumps, no more and no fewer.

Now count stones travelled. Each of the six creatures must move four places, so the total advance is 24 stones. A slide advances one stone and a jump advances two, so slides + 2 x 9 = 24, giving exactly 6 slides. Total moves: 9 + 6 = 15.

In general, with n on each side the count is n^2 + 2n: n^2 jumps because every frog passes every toad once, and 2n slides. For n = 3 that is 9 + 6 = 15, and for n = 4 it would be 16 + 8 = 24. The sequence itself alternates in a rhythm - slide, jump, jump, slide, jump, jump, jump - which is easier to find once you know you are looking for exactly nine jumps.

The technique worth keeping

When one kind of move is the only way to make a required change, count those moves first - they are fixed by the problem, not by your strategy. The rest of the solution is then arranging the cheaper moves around a known skeleton.