Two jugs and a tap, step by step
A 6L jug, an 11L jug, a tap, and no markings on either.
What is the fewest steps that leave exactly 9L in a jug?
Map every move to find the shortest route
- You start with two empty, unmarked jugs: 7L and 23L. The goal is to leave exactly 9L in either jug. You cannot guess a level by eye, so every amount has to come from a legal fill, empty, or pour.
- At any point you may fill either jug, empty either jug, or pour in either direction. That gives six possible moves. There is no seventh kind of move, so the search is small enough to check completely.
- Write the amount in the 7L jug first and the amount in the 23L jug second. The starting state is (0, 0), and every legal move takes one pair to another. The puzzle is now a small map of states.
- Check every state one move from (0, 0), then every new state two moves away, and continue in that order. The first time 9L appears, no shorter route can exist, because every shorter state was already checked.
- It first appears after 4 steps, with the 9L standing in the 23L jug.
How it works.
- 01
You start with two empty, unmarked jugs: 7L and 23L. The goal is to leave exactly 9L in either jug. You cannot guess a level by eye, so every amount has to come from a legal fill, empty, or pour.
- 02
At any point you may fill either jug, empty either jug, or pour in either direction. That gives six possible moves. There is no seventh kind of move, so the search is small enough to check completely.
- 03
Write the amount in the 7L jug first and the amount in the 23L jug second. The starting state is (0, 0), and every legal move takes one pair to another. The puzzle is now a small map of states.
- 04
Check every state one move from (0, 0), then every new state two moves away, and continue in that order. The first time 9L appears, no shorter route can exist, because every shorter state was already checked.
- 05
It first appears after 4 steps, with the 9L standing in the 23L jug.