The Soldiers and the Boys

  • Medium
  • River crossing puzzles
  • Tests: Finding the repeatable unit of progress

The puzzle

An army reaches a river. A small boat is there with two boys in it. The boat carries either the two boys, or one soldier - never a soldier and a boy, and never two soldiers.

How does the whole army get across, and how many trips does each soldier cost?

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

Find a sequence that moves exactly one soldier and leaves everything else as it was.

Hint 2

The boys have to end up back on the near bank with the boat before the next soldier can go.

Show the answer Hide the answer

Four trips per soldier: both boys cross, one rows back, a soldier crosses, the other boy rows back. Repeat for each soldier.

How to get there

Both boys cross. One boy rows back. The near bank now has the army plus one boy, and the boat.

One soldier crosses alone. The boy waiting on the far side rows back, restoring the exact starting position - except that one soldier is now across.

That four-trip cycle is repeatable without limit, so an army of n soldiers takes 4n trips, after which the boys cross one final time.

The technique worth keeping

Look for a cycle that nets one unit of progress and returns everything else to where it started. Once you have that, the size of the problem stops mattering - which is the same idea as a loop invariant.