Water Jug Puzzle Using BFS and DFS

Our happy farmers:)

There once were two lovely farmers Jane and Mike who love to play games during their spare time, “I have got a fun puzzle for you to solve”, said Jane.

You have two jugs of water. One holds five liters and the other holds three liters. Neither jug has any markings so the only amount you can measure accurately is when a jug is full.

How can you measure out exactly four liters?

After a decent amount of time, Mike finally came up with the solutions!

Depth-First-Search and Breath-First-Search Node Traversing Concept

Traverse all the way to along the branch until find the dead end then backtrack

Depth First Search Concept:

The core concept of DFS is that we explore the route by consistently traversing downwards from one node to another means through the subtrees, without backtracking until a dead end is reached. When it comes to multiple adjacent neighbors, DFS selects one path and continues to traverse downwards, delving as deeply as possible through left branches, until either reaching a dead end or a previously visited leaf node as we can see in the figure.

And now the reasonable question might be, how can we potentially solve this problem using this algorithm?

First we use DFS to explore all possible states of our jug and the transition actions we might take until we eventually achieve our desired liter of water in the jug

• Firstly, we have a stack to keep track of the jug states.
• Start by putting the initial state (both jugs empty) onto a stack

The DFS algorithm iterates as follow:

1. Remove or pop state current state from a stack
2. Check if the current state is the goal state (For example, the desired quantity of water). If it is, we stop and return the solution
3. If the current state is not the goal, proceed to generate all possible next states from the current state
4. Push the next state onto our stack

Indeed, this will we our recurring theme:)

For this puzzle another key point of it is we can do 3 operations:

1. Fill the jug (Let’s suppose we fill jug A (3,0) and if we fill jug B (0,5))
2. Empty the jug (If we empty jug A then (0,B) would be our state)
3. Transfer (Pouring water from one jug to another, it could be from A to B (A - D, B + D) D represents amount of pouring water)

Initialization: We start with both jugs empty, denoted as (0,0) where the first value represents the amount of water in jug A and the second value represents the amount of water in jug B.

Traversal: We begin exploring from the initial state (0,0). From here, we can perform operations to transition to new states, as we mentioned above. we keep generate new state until we reached the desired goal state

Backtracking: If we reach a state where we cannot perform any more operations (e.g., both jugs are full or both jugs are empty), or if we encounter a state we have visited before, we backtrack to the previous state and try a different operation.

Stack demonstration

and here is the solution:

Input Jug A capacity 3 liters, Jug B capacity 5 liters the desired amount is 4L

Output: {(0,0) (3,0) (3,5) (0,5) (3,2) (0,2) (2,0) (2,5) (3,4) (0,4)}

Python Code:

from collections import defaultdict

# jug1 and jug2 contain the value 
# for max capacity in respective jugs 
# and aim is the amount of water to be measured. 
jug1, jug2, aim = 3, 5, 4

visited = defaultdict(lambda: False)


def waterJugSolver(amt1, amt2): 

 # Checks for our goal and 
 # returns true if achieved.
 if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0):
  print(amt1, amt2)
  return True
 
 # Checks if we have already visited the
 # combination or not. If not, then it proceeds further.
 if visited[(amt1, amt2)] == False:
  print(amt1, amt2)
 
  # Changes the boolean value of the combination as it is visited. 
  visited[(amt1, amt2)] = True
 
  # Check for all the 6 possibilities and 
  # see if a solution is found in any one of them.
  return (waterJugSolver(0, amt2) or
    waterJugSolver(amt1, 0) or
    waterJugSolver(jug1, amt2) or
    waterJugSolver(amt1, jug2) or
    waterJugSolver(amt1 + min(amt2, (jug1-amt1)),
    amt2 - min(amt2, (jug1-amt1))) or
    waterJugSolver(amt1 - min(amt1, (jug2-amt2)),
    amt2 + min(amt1, (jug2-amt2))))
 
 # Return False if the combination is 
 # already visited to avoid repetition otherwise
 # recursion will enter an infinite loop.
 else:
  return False

print("Steps: ")
waterJugSolver(0, 0)

And yes here we go using DFS to systematically solve the puzzle. Now let’s jump into the conclusion of DFS a little

Common Cases of Using DFS

1. Graph Traversal:

• DFS is commonly used for graph traversal, visiting all the vertices of a graph in a depthward motion.
• It can be used to find paths between two vertices, detect cycles, and explore connected components.
• Applications include maze solving, network analysis, and topological sorting.

2. Check for BST(Binary Search Tree):

• Using Depth-First Search (DFS), we perform an in-order traversal of the tree. During this traversal, we track the previously visited node’s value. At each step, we compare the value of the current node with the value of the previous node. If the current node’s value is less than or equal to the previous node’s value, the tree is not a BST

3. Path Finding:

• DFS is a handy algorithm for finding paths in graphs or trees. It’s great for figuring out how to get from one point to another. DFS digs deep into the graph, uncovering different routes to reach the destination node

4. Backtracking:

• We can systematically explore all possible solutions in backtracking, DFS is used to search through the solution space, trying different options at each step and if a dead end is reached, it backtracks to the previous decision point and explores alternative paths. Yes as we did previously:)

Breath First Search Concept

Let’s stick out mind to what would be the alternatives direction that DFS could make in order to traverse down the branches visually, it will help you to actually understand BFS quite faster.

We explore nodes layer by layer. It starts at the root node (or any arbitrary node) and systematically explores all the neighbor nodes at the current depth level before moving on to the nodes at the next depth level.

Superficially, I mean when we first read it we might instantly sense the difference, and why is that? Well it is because we are a genius and we remember that DFS traverses down as deep as possible through each branches but in the other hand, our BFS search all the nodes, traversing down level by level or layer by later and yes that makes it BFS!

As we can see we traverse through nodes layer by later

Traverse through all nodes that are in the same layer before moving forward

The BFS algorithm iterates as follows:

1. Initialize: Start with an empty queue to store states.
2. Enqueue Initial State: Add the initial state (both jugs empty) to the frontier.
3. While Queue is Not Empty:

• Remove a state from the front of the frontier.
• Check if the removed state represents the desired quantity. If so, stop and return the solution.
• Generate all possible next states from the current state
• Add the next states onto the frontier

Hm…,now after observing the graph visualization for a moment, I feel like somehow BFS seems to take less time to find the goal or in our case to reach the goal state. Oh wait, does it mean it’s faster to do so? the answer is YES! it is faster to use BFS in this case. So if it’s faster then why would we even bother to use DFS well here are the reasons why:

1. Speed: In general, BFS tends to be faster than DFS for finding the shortest path between two nodes in an smaller graph or tree because it systematically explores all neighbors at the current depth level before moving to the next depth level. However, in some cases, DFS might be faster, especially if the target node is closer to the starting node and the graph is dense.
2. Memory Usage: BFS typically requires more memory because it needs to store all the nodes at the current depth level in the frontier (queue). On the other hand, DFS uses less memory as it only needs to store the current path and backtrack when necessary.
3. Completeness: BFS is complete, meaning it will always find a solution if one exists, and it guarantees finding the shortest path in an unweighted graph. DFS, however, may not find a solution if the search space is infinite or if the graph contains cycles without proper cycle detection.

Yes, BFS is our favorite for shortest path finding and ensures completeness, while DFS is more memory efficient and suit more for exploring all solutions or delving deeply into a graph/tree. The choice between them depends on factors like problem structure, memory limits, and specific goals.

Okay this might not be so relevant specifically to our Jug Puzzle, now let’s implement code using BFS Algorithm and solve it let’s see if it takes less steps or not!

This is the step output we got after using BFS

Output: {(0,0) (0,5) (3,2) (0,2) (2,0) (2,5) (3,4)}

Perfect! Only 6steps now compared to the last it is definitely better right?

from collections import deque

def waterJugSolverBFS(jug1, jug2, aim):
    queue = deque([(0, 0)])
    visited = set([(0, 0)])
    parents = {}

    while queue:
        current_state = queue.popleft()
        amt1, amt2 = current_state

        if amt1 == aim or amt2 == aim:
            steps = []
            while current_state != (0, 0):
                steps.append(current_state)
                current_state = parents[current_state]
            steps.append((0, 0))
            steps.reverse()
            return steps

        next_states = [
            (jug1, amt2),  
            (amt1, jug2),  
            (0, amt2),     
            (amt1, 0),     
            (min(jug1, amt1 + amt2), max(0, amt1 + amt2 - jug1)),  
            (max(0, amt1 + amt2 - jug2), min(jug2, amt1 + amt2))   
        ]

        for state in next_states:
            if state not in visited:
                queue.append(state)
                visited.add(state)
                parents[state] = current_state

    return None

# Example usage:
jug1_capacity = 5
jug2_capacity = 3
desired_quantity = 4

solution = waterJugSolverBFS(jug1_capacity, jug2_capacity, desired_quantity)
if solution:
    for step in solution:
        print(step)
else:
    print("No solution found.")

Amazing! We finally did it:) as easy as it should be hehe, or at least I hope we learned something new here. Depth First Search and Breath First Search since this is just another way of using these two to solve this specific problem. As the matter of fact that these algorithm is interestingly well-known and widely used and so significant means that there are so much more for us to explore! As the result we now got a jug with 4 liters of water and Mike our farmer is happy now since we solved the puzzle!

Resources

These are videos I found them useful:)

1. https://youtu.be/by93qH4ACxo?si=JGWMI-eQRpaUH2Hp DFS Bro Code
2. https://youtu.be/7Cox-J7onXw?si=PTluPa6CMOpgVPa_ BFS Bro Code
3. https://youtu.be/5NgNicANyqM?si=PsuYXpwyDhX3pRa4 CS50 Course by Brian Yu for Harvard University.