Water Jug problem using BFS

Problem Statement

Given two jugs with J1 and J2 litres of capacities which are initially empty. Using these jugs you have to measure L litres of water (L < J2).
The (x, y) is the state where x and y are the amount of water in J1 and J2 respectively.

The task is to find the path from initial state (0, 0) to final state (d, 0) or (0, d).

Operations that can performed are as follows:

1. Fill any of the jugs completely with water, like (x, y)->(0, y).
2. Empty any of the jugs, (0, 0)->(x, 0).
3. Pour water from one jug into another till the other jug is completely full or the first jug itself is empty, (x, y) -> (x-d, y+d).

Example Input

J1 = 2, J2 = 5 , L = 4

Expected Output

Path is as Follow:
(0, 0)
(0, 5)
(2, 0)
(2, 5)
(2, 3)
(0, 2)
(2, 2)
(0, 4)

Approach

The Approach is to use memoization and recursion.

This approach do the following, using Recursion, visit all the given operations one by one until condition satisfied and true value is returned. For every return value, it is stored using memoization. Memorisation is done to stop the recursive calling.

Implementation in Python

from collections import defaultdict 
  
visited = defaultdict(lambda: False) 

# To store J1, J2 and Litre
J1, J2, L = 0, 0, 0
  
def Water_Jug_problem(X, Y):  
    
    global J1, J2, L
  
    if (X == L and Y == 0) or (Y == L and X == 0): 
        print("(",X, ", ",Y,")", sep ="") 
        return True
      
    if visited[(X, Y)] == False: 
        print("(",X, ", ",Y,")", sep ="") 
      
        visited[(X, Y)] = True
      
        return (Water_Jug_problem(0, Y) or
                Water_Jug_problem(X, 0) or
                Water_Jug_problem(J1, Y) or
                Water_Jug_problem(X, J2) or
                Water_Jug_problem(X + min(Y, (J1-X)), 
                Y - min(Y, (J1-X))) or
                Water_Jug_problem(X - min(X, (J2-Y)), 
                Y + min(X, (J2-Y)))) 
    else: 
        return False
  
# Main Code

J1 = 2 
J2 = 5 
L = 3
print("Path is as Follow:") 
  
Water_Jug_problem(0, 0)