Problem:

Sim’eon Denis Poisson (1781–1840), a famous French mathematician and physicist, is said to have become interested in mathematics after encountering some version of the following old puzzle: Given an 8-gallon jug full of water and two empty jugs of 5- and 3-gallon capacity, get exactly 4 gallon of water in one of the jugs by completely filling up and/or emptying jugs into others.
We will generalize this problem to work with 3 jugs of varying capacity. Let’s say that we have 3 jugs, namely A, B, and C. Jug C will always start out completely full. Furthermore, we will define a goal state where jug A will contain a gallons, B will contain b gallons, and C will contain c gallons upon completion of the search. You need to find the minimum number of moves to go from the initial state to the goal state.

Display:

$ ./waterjugpuzzle
Usage: ./waterjugpuzzle <cap A> <cap B> <cap C> <goal A> <goal B> <goal C>

$ ./waterjugpuzzle 3 5 8 0 2 6
Initial state. (0, 0, 8)
Pour 5 gallons from C to B. (0, 5, 3)
Pour 3 gallons from B to A. (3, 2, 3)
Pour 3 gallons from A to C. (0, 2, 6)

$ ./waterjugpuzzle 5 7 10 3 3 4
No solution.

Solution:

• In this solution, we use tree data structure and BFS (breadth-first search) to solve the problem.
• Root node is initial state.
• Each node in the tree corresponds to the state after pouring water and has only 1 parent
• From each node, append maximum of 6 children representing 6 different ways to pour water.
• When a new state is created, it’s marked as visited. We also enqueue it into a queue.
• Dequeue each node in queue and continue to append tree from that node.
• When the goal state reached, find the path from this node to root. The path representing the steps for filling the jugs required by input.

Example:

Take a look at this example:

$ ./waterjugpuzzle 3 5 8 0 2 6
Initial state. (0, 0, 8)
Pour 5 gallons from C to B. (0, 5, 3)
Pour 3 gallons from B to A. (3, 2, 3)
Pour 3 gallons from A to C. (0, 2, 6)

• Capacity in 3 jugs A, B, C is 3, 5, 8 gallons respectively.
• Our goal is get exactly 2 gallons in jug B and 6 gallons in jug C.
• We start with initial state (0, 0, 8), as root, that means
  • Jug A and jub B are empty
  • Jug C contains 8 gallons
• Append 2 children as 2 ways to pour water. We also enqueue them:

                Tree                        Queue
                (0, 0, 8)                   |0, 5, 3| <
                /       \                   |3, 0, 5|
               /         \
        (0, 5, 3)       (3, 0, 5)
  

• Dequeue and take (0, 5, 3) state. Keep append children from this node and enqueue new states:

                            (0, 0, 8)
                            /       \
                           /         \
                   (0, 5, 3)         (3, 0, 5)
                   /       \
                  /         \
          (3, 2, 3)         (3, 5, 0)
  

• Keep going, and we’ll have this:

                            (0, 0, 8)
                            /       \
                           /         \
                   (0, 5, 3)         (3, 0, 5)
                   /       \                 \
                  /         \                 \
          (3, 2, 3)         (3, 5, 0)         (0, 3, 5)
           /                                  /
          /                                  /
  (0, 2, 6)                          (3, 3, 2)
  

• We can easily see the path from root (0, 0, 8) to goal state (0, 2, 6). Those are the steps to solve the problem.

Pseudo code:

bool BFS(int a, int b, int c) 

    enqueue new State(a, b, c) 
    dequeue a state from the Queue
    
    while (queue is not empty)
        if current_state equals goal_state
            print the backtracked solution
            return true

        if current_state has already been seen
            continue

        mark current as having been visited
        try 6 ways to pour water, enqueue new states to queue
    
    return false

Note: Source code available here. Give me ⭐ if you enjoy it!