Solution:
First, fill the n litre jug and empty all its contents in the â€śmâ€ť litre jug. As soon as the n litre jug becomes vacant, refill it. As soon as the â€śmâ€ť litre jug becomes full, empty it. Repeat the first three steps until either the n litre jug or the m litre jug, has exactly d litres of water in it
Numerous source codes have been devised for solving Water Jug problems using recursion, searching and sorting algorithms. The solution written using BreadthFirst Search is considered to be one of the most optimum solutions. Letâ€™s first understand, â€śWhat is BreadthFirst Search (BFS)?â€ť.
Breadthfirst search is also known as â€śLevel order traversalâ€ť. It is a graph traversal algorithm, in which the graph traversal begins from the root node and explores the entire range of adjacent nodes. Then the nearest node is picked up and all the unexplored/unvisited nodes are explored/visited. The same steps are followed until the goal node is reached.
Breadthfirst search is usually compared with the depthfirst search (DFS Algorithm) algorithm. For solving the Water Jug Puzzle, we prefer the Breadthfirst search over the Depthfirst search as it is not necessary that the depthfirst search will find the shortest path. BFS will not lead to an infinite loop and finds the shortest possible path between the root node and the goal via other accessible nodes.
In Graph theory, the Breadthfirst search is used to solve a wide range of problems. For example Cheneyâ€™s algorithm, Peer to Peer Networks, Copying garbage collection, Crawlers in Search Engines, Finding Minimum Spanning Tree, GPS tracking system, Finding the shortest path between two given nodes u and v, by measuring the path length by the number of edges and so on.
Worst case time complexity of BFS : O(E) = O(b^d)
Space complexity of BFS : O(V) = O(b^d)
What is the State Space?
The set of all possible configurations available for a given problem and its environment variables is known as its state space. The state contains Static information related to the system at any point. Each distinct configuration of the problem is known as its state. While iterating through the solutions one state can be achieved more than once.
The statespace for the water jug problem is usually represented as a set of ordered pairs of integers (X, Y), where X= 1,2,3,â€¦..m and Y=1,2,3,â€¦â€¦n. Where X is the number of gallons/litres of water in Jug A and Y is the number of gallons/litres of water in Jug B. The highest possible value of X is m which is the actual capacity of the gallon. Similarly, for Y, the highest possible value is n, which is its maximum capacity.
Also See, Fibonacci Series in Python
Implementation of the BFS Algorithm:
The belowmentioned four steps are followed to solve the water jug problem:
 Define a state space that contains all possible configurations of the water jugs and even some of the unreachable ones.
 Specify one or multiple states within that space that describe all the possible situations from which we can initiate the problemsolving process. These states are referred to as the initial states.
 Specify one or more states which are regarded as the acceptable solutions to the problem. These states are known as goal states.

Specify a set of rules also known as predictions that describe the actions (operators) allowed and a welldefined control strategy for aligning the order of application of these predictions.
We make some assumptions for solving the Water Jug Problem:
 You can fill any Jug from the pump.
 You are allowed to pour water from a jug into the ground/bucket.
 You are allowed to pour water from one jug to another.
 You can not use any other measuring device or parameters.
Source Code for Water Jug Problem in CPP:
The solution given below is a C++ code for solving the Water Jug problem using BreadthFirst Search and Queue. All the intermediary operations are written using ifelseif conditions. The output is given in the form of state configuration representations.
#include <bits/stdc++.h>
using namespace std;
class nodes{
public:
pair<int,int> p;
int first;
int second;
string s;
};
string makestring(int a,int b){
std::stringstream out1;
std::stringstream out2;
string t1,t2,str;
out1 << a;
t1 = out1.str();
out2 << b;
t2 = out2.str();
str = "("+t1+","+t2+")";
return str;
}
int main()
{
int counter = 0;
ios::sync_with_stdio(false);
//pair<int,int> cap,ini,final;
nodes cap,ini,final;
ini.p.first=0,ini.p.second=0;
ini.s = makestring(ini.p.first,ini.p.second);
//Input initial values
cout<<"Enter the capacity of 2 jugs\n";
cin>>cap.p.first>>cap.p.second;
//input final values
cout<<"Enter the required jug config\n";
cin>>final.p.first>>final.p.second;
//Using BFS to find the answer
queue<nodes> q;
q.push(ini);
nodes jug;
while(!q.empty()){
//Base case
jug = q.front();
if(jug.p.first == final.p.first){// && jug.p.second == final.p.second){
cout<<jug.s<<endl;
// counter++;
// if(counter==5)
return 0;
}
nodes temp = jug;
//Fill 1st Jug
if(jug.p.first<cap.p.first){
temp.p = make_pair(cap.p.first,jug.p.second);
temp.s = jug.s + makestring(temp.p.first,temp.p.second);
q.push(temp);
}
//Fill 2nd Jug
if(jug.p.second<cap.p.second){
temp.p = make_pair(jug.p.first,cap.p.second);
temp.s = jug.s + makestring(temp.p.first,temp.p.second);
q.push(temp);
}
//Empty 1st Jug
if(jug.p.first>0){
temp.p = make_pair(0,jug.p.second);
temp.s = jug.s + makestring(temp.p.first,temp.p.second);
q.push(temp);
}
//Empty 2nd Jug
if(jug.p.second>0){
temp.p = make_pair(jug.p.first,0);
temp.s = jug.s + makestring(temp.p.first,temp.p.second);
q.push(temp);
}
//Pour from 1st jug to 2nd until its full
if(jug.p.first>0 && (jug.p.first+jug.p.second)>=cap.p.second){
temp.p = make_pair((jug.p.first(cap.p.secondjug.p.second)),cap.p.second);
temp.s = jug.s + makestring(temp.p.first,temp.p.second);
q.push(temp);
}
//Pour from 2nd jug to 1st until its full
if(jug.p.second>0 && (jug.p.first+jug.p.second)>=cap.p.first){
temp.p = make_pair(cap.p.first,(jug.p.second(cap.p.firstjug.p.first)));
temp.s = jug.s + makestring(temp.p.first,temp.p.second);
q.push(temp);
}
//Pour all water from 1st to 2nd
if(jug.p.first>0 && (jug.p.first+jug.p.second)<=cap.p.second){
temp.p = make_pair(0,jug.p.first+jug.p.second);
temp.s = jug.s + makestring(temp.p.first,temp.p.second);
q.push(temp);
}
//Pour from 2nd jug to 1st until its full
if(jug.p.second>0 && (jug.p.first+jug.p.second)<=cap.p.first){
temp.p = make_pair(jug.p.first+jug.p.second,0);
temp.s = jug.s + makestring(temp.p.first,temp.p.second);
q.push(temp);
}
q.pop();
}
return 0;
}
Example:
Input: 4 3 2 3
Output: (0,0) (4,0) (1,3) (1,0) (0,1) (4,1) (2,3)
Code Courtesy: Anirudh Bagri
Issues in the Water Jug Problem :
Although we have multiple feasible solutions for the water jug problem, yet there are several issues faced by the programmers and knowledge engineering experts. Such issues include :
 Throwing the water in the ground should not be allowed as this leads to waste of water.
 Before filling any jug, we have to check if it is filled or not. This leads to extra space complexity as a variable has to be created for tracking this condition.
 Many times, intermediate states are redundant and therefore, leads to repetitive operations, leading to an additional computational time.
 The state representation can be confusing for beginners, especially if there are more than ten jugs available.
 In the output, only the configuration states are displayed, it will be very difficult to display the operations carried out on each state. In the case of larger inputs, this becomes uninferable.
Frequently Asked Questions
Why is DFS not used for solving a water jug problem?
DFS is also known as DepthFirst Search sometimes turns out to be an incomplete algorithm and may end up abruptly, giving a NonOptimal Solution. The solution generated by the depthfirst search may be incomplete as this algorithm goes on to the deepest possible point in the first path. In case, that first path leads to infinity, the algorithm will turn into an infinite loop and will never give any correct solution.
If many consecutive solutions give the same answer, usually that is considered to be the optimal solution but actually, it isnâ€™t. If the target Goal State is not present in that path, then the Goal State will never be reached as the prior loop is an infinite one.
Are there more problems similar to The Water Jug problem?
There are several other knowledge engineeringdriven daily life problems that can be solved by writing Artificial Intelligencebased algorithms. Most of these are solved by using the BreadthFirst Search (BFS) or Depth First Search (DFS).
Nowadays, to reduce the time complexity algorithm developers have devised several combinations of BFS and DFS along with other binary treebased programming strategies. Some of the commonly studied Artificial intelligencebased problems include:
 Missionaries and Carnivals Problem
 Chess Problem
 8 Queen Problem
 8 Puzzle Problem
 Monkey Banana Problem
 Tower of Hanoi Problem
 Cryptarithmetic Problem
You can check out How to Solve 8 Queens Problem Using Backtracking here.
What is the time complexity of the Water Jug problem?
In the water jug problem, we carry multiple operations on the previous state of the system and try to reach the goal state. Most of the algorithms that are written down to solve the water jug problem include the following four steps:
Assuming that you are given two unlabelled jugs m and n, and the desired quantity of water is d litres.
Step One: Fill the m litre jug and empty its contents into the n litre jug.
Step Two: If at any instant the m litre jug becomes empty fill it with water.
Step Three: If at any instant the n litre jug becomes full empty it.
Step Four: Repeat steps one, two, and three till any of the jugs among the n litre jug and the m litre jug contains exactly d litres of water.
The time complexity of the solutions is usually O (m*n).
Do we have a Heuristic Function for solving the Water Jug Problem?
We usually add a heuristic function while solving problems to estimate how close we are to our goal. The closer the goal, the lower is the value of the heuristic function, it is often known as the estimated cost. The bestestimate function of the problem is admitted as its heuristic function. In the water jug problem, there is a constraint that only certain amounts of water can be added to a gallon of water.
The heuristic function proposed for a water jug problem, h(x,y) = (x * a) + (y * b), and has the lowest value at (0,0). This function is definitely feasible and consistent, as in practice it is the amount that is required to get to the goal from that node in one step, assuming that one step is possible. As soon as, you reach the goal node, this value becomes zero.
Conclusion
The BFS approach for solving the water jug problem has been one of the most feasible solutions. Although, various programmers have solved the Water Jug problem in O (m*n) using recursion and other tree exploitation strategies. This can be written in any of the programming languages including developmentbased languages such as JavaScript, Swift, etc.
Algorithms are updated very swiftly, still, Artificial Intelligence experts are working to find a better solution for solving the Water Jug problem. Analytically, a better solution would be a hybrid algorithm, devised by combining the properties of breadthfirst search, depthfirst search, recursive function calls, priority approach.
Check out this problem  No of Spanning Trees in a Graph
To solve more problems on data structure and algorithm please visit our problem section.