Water pouring puzzle

Starting state of the standard puzzle; a jug filled with 8 units of water, and two empty jugs of sizes 5 and 3. The solver must pour the water so that the first and second jugs both contain 4 units, and the third is empty.

Water pouring puzzles (also called water jug problems, decanting problems,[1][2] measuring puzzles, or Die Hard with a Vengeance puzzles) are a class of puzzle involving a finite collection of water jugs of known integer capacities (in terms of a liquid measure such as liters or gallons). Initially each jug contains a known integer volume of liquid, not necessarily equal to its capacity.

Puzzles of this type ask how many steps of pouring water from one jug to another (until either one jug becomes empty or the other becomes full) are needed to reach a goal state, specified in terms of the volume of liquid that must be present in some jug or jugs.[3]

By Bézout's identity, such puzzles have solution if and only if the desired volume is a multiple of the greatest common divisor of all the integer volume capacities of jugs.

  1. ^ Weisstein, Eric W. "Three Jug Problem". mathworld.wolfram.com. Retrieved 2020-01-21.
  2. ^ "Solving Decanting Problems by Graph Theory". Wolfram Alpha.
  3. ^ "Decanting Problems and Dijkstra's Algorithm". Francisco Blanco-Silva. 2016-07-29. Retrieved 2020-05-25.