bryann.net

Welcome to bryann.net

Questions? Comments? Contact me at web [at] bryann.net.

Bryan Newell's Water Jug Castle

A method for solving logic puzzles.

The Water Jug Castle by Bryan Newell

I once read a very fascinating book which I believe was called "Mathematical Mazes." It's been too long since I read it, I can barely remember. One of the chapters was devoted to solving puzzles by graphing them out. The example in the book was the famous "pig, porridge and fox" puzzle.

I decided to try graphing out a puzzle myself, and chose to do the "Water Jug" problem. It's the one where you have three jugs (an eight gallon, a five gallon, and a three gallon) and you start out with the eight gallon full and the other two empty, and you have to figure out how to pour the jugs in order to end up with exactly four gallons in the eight and five gallon jugs.

Notation is as follows: [8 gallon jug][5 gallon jug][3 gallon jug], so that you start at 800 (8 gallons of water in the 8 gallon jug, no water in the other two) and want to end up at 440 (4 gallons of water in both the 8 gallon and 5 gallon jugs, no water in the 3 gallon).

First of all, I made a list of every valid move possible when solving the problem. This resulted in Fig 1. (a dash ('-') indicates 'not a valid move').

I then spent well over two hours trying to convert this list of moves into a valid graph/maze.

At some point, I was struck at the resemblence of my best effort of graphing it out to a castle. The resulting map, shown below, shows every valid move in the Water Jug Problem.

The green arrows located in the corners of the interior rooms indicate one-way "secret passages" (in keeping with the castle theme) leading toward the appropriate Corner Tower (ie, a northwest secret passage always leads one-way to Room 503, regardless of which room the passage is in).

To find the fastest solution to the puzzle, just trace the shortest path through the above maze.