Water Jug Problem: Solutions Step by Step
See each classic answer one pour at a time, or enter your jugs to get the fewest steps.
Play the Water Jug Puzzle (free)Keep pouring in one direction to reach the goal
- If the jug you pour into is full, empty it
- If the jug you pour from is empty, fill it
- Otherwise pour from it into the other jug
3 and 5 gal jugs + tap: make 4 gal
0
3 gal0
5 galStarting point
This way takes 6 steps (the fewest)
Try both orders. The shorter one is the fewest steps.
Die Hard riddle: 3 and 5 make 4 in 6 steps
In Die Hard with a Vengeance (1995), the heroes need exactly 4 gallons from a fountain.
| Step | 3 gal | 5 gal | Action |
|---|---|---|---|
| 0 | 0 | 0 | Start |
| 1 | 0 | 5 | Fill 5 gal |
| 2 | 3 | 2 | 5 gal → 3 gal |
| 3 | 0 | 2 | Empty 3 gal |
| 4 | 2 | 0 | 5 gal → 3 gal |
| 5 | 2 | 5 | Fill 5 gal |
| 6 | 3 | 4 | 5 gal → 3 gal |
Filling the 3-gallon jug first takes 8 steps.
4 and 3 gallons: 2 gallons in the 4-gallon jug takes 6 steps
This one is a classic exercise in AI courses. Fill the 3-gallon jug first:
| Step | 4 gal | 3 gal | Action |
|---|---|---|---|
| 0 | 0 | 0 | Start |
| 1 | 0 | 3 | Fill 3 gal |
| 2 | 3 | 0 | 3 gal → 4 gal |
| 3 | 3 | 3 | Fill 3 gal |
| 4 | 4 | 2 | 3 gal → 4 gal |
| 5 | 0 | 2 | Empty 4 gal |
| 6 | 2 | 0 | 3 gal → 4 gal |
If either jug can hold the 2 gallons, stop at step 4.
8, 5 and 3: split 8 gallons in half in 7 steps
There is no tap: the 8-gallon jug starts full, and you fill from it and empty into it.
| Step | 8 gal | 5 gal | 3 gal | Action |
|---|---|---|---|---|
| 0 | 8 | 0 | 0 | Start |
| 1 | 3 | 5 | 0 | 8 gal → 5 gal |
| 2 | 3 | 2 | 3 | 5 gal → 3 gal |
| 3 | 6 | 2 | 0 | 3 gal → 8 gal |
| 4 | 6 | 0 | 2 | 5 gal → 3 gal |
| 5 | 1 | 5 | 2 | 8 gal → 5 gal |
| 6 | 1 | 4 | 3 | 5 gal → 3 gal |
| 7 | 4 | 4 | 0 | 3 gal → 8 gal |
Going 8 → 3 → 5 → 8 instead takes 8 steps.
It’s solvable when the target is a multiple of the greatest common divisor
- Two jugs and a tap make every multiple of the GCD, up to the bigger jug
- 3 and 5 (GCD 1) can make 1, 2, 3, 4 or 5
- 4 and 6 (GCD 2) can’t make 1, 3 or 5
- Every amount is full jugs added and taken away: 4 = 5 + 5 − 3 − 3 (Bézout’s identity)
Enter your jugs to get the fewest steps
Up to 4 jugs of up to 30 gallons. Handy for checking homework answers.
| Jug | Size | Start | Goal |
|---|---|---|---|
| A | |||
| B | |||
| C | |||
| D |
gallons in any jug
- Leave a size blank to skip that jug
- In Split, a blank goal means any amount
The solver uses breadth-first search
- A state is the amount in each jug. 3 and 5 with a tap start at (0, 0)
- Each step is one of 6 moves: fill A or B, empty A or B, or pour one into the other
- BFS looks at every state 1 step away, then 2 steps away, and so on
- So the first path it finds to the goal is a shortest one
- 3 and 5 can reach only 16 states. Even 4 jugs of 30 gallons have under a million
FAQ
- Can I pour only part of a jug?
- No. With no markings, you pour until one jug is empty or the other is full
- Do filling and emptying count as steps?
- Yes, one step each (in the game and the solver too)
- Is the shorter order always the fewest steps?
- Yes with two jugs and a tap (705 checked) and for splitting in half (864). Other goals can be quicker
- Does it work in liters?
- Yes. Only the numbers matter, so the steps are the same in any unit
- How do I solve LeetCode 365, Water and Jug Problem?
- Water in both jugs counts, so it’s possible when the target is at most x + y and a multiple of gcd(x, y)
- Can I practice?
- The game has 60 puzzles and a daily puzzle. Hint shows the next step of a shortest solution
