Water Jug Problem Artificial Intelligence
/* Water Jug Problem
This problem is basically asking you to perform a Breadth First Search on
a directed graph. The nodes in the graph corresponds to a “state”, and
a state is basically a pair (n, m) where n and m are the volume of water
in the jugs. There’s an edge from (n, m) to (n1, m1) if a valid operation
exists such that the result of the operation is (n1, m1).
The implementation for BFS is done by using queue. Also, a state (n, m)
is translated into an integer i for convenience.
*/
Code For Water Jug Problem
#include
#include
#include
class Queue
{
public:
Queue()
: head(NULL), tail(NULL)
{
}
void enqueue(int i)
{
if (head == NULL)
head = tail = new Node(i, NULL);
else
tail = tail->next = new Node(i, NULL);
}
int dequeue()
{
Node* old = head;
head = head->next;
int i = old->i;
delete old;
return i;
}
int isEmpty()
{
return (head == NULL);
}
~Queue()
{
while (!isEmpty())
dequeue();
}
private:
struct Node
{
int i;
Node* next;
Node(int iP, Node* nextP)
: i(iP), next(nextP)
{
}
} *head, *tail;
} iQueue;
const int MAX = 100;
const int MAX_I = (MAX + 1) * (MAX + 1);
int N, M, k, n, m;
int distance[MAX_I];
int prev[MAX_I];
int nmToI(int n, int m)
{
return n * (M + 1) + m;
}
int iToN(int i)
{
return i / (M + 1);
}
int iToM(int i)
{
return i % (M + 1);
}
void trace(int i)
{
if (i > 0)
trace(prev[i]);
cout <<" "<
}
void test(int n, int m, int n1, int m1)
{
if (n1 < 0 || n1 > N || m1 < 0 || m1 > M)
return;
int i1 = nmToI(n1, m1);
if (distance[i1] != 0)
return;
int i = nmToI(n, m);
distance[i1] = distance[i] + 1;
prev[i1] = i;
iQueue.enqueue(i1);
}
int solve()
{
n = m = 0;
distance[0] = 1;
iQueue.enqueue(0);
while (!iQueue.isEmpty())
{
int i = iQueue.dequeue();
int n = iToN(i);
int m = iToM(i);
if (n == k || m == k || n + m == k)
return i;
// empty out a jug
test(n, m, 0, m);
test(n, m, n, 0);
// fill a jug
test(n, m, N, m);
test(n, m, n, M);
// pour one to another until source is empty
test(n, m, 0, n + m);
test(n, m, n + m, 0);
// pour one to another until destination is full
test(n, m, n – M + m, M);
test(n, m, N, m – N + n);
}
return -1;
}
void main()
{
clrscr();
cout<<"Please enter the number of gallons in first jug: ";
cin>>N;
cout<<"Please enter the number of gallons in second jug: ";
cin>>M;
cout<<"Please enter the vol. of water to be left finally: ";
cin>>k;
int i = solve();
cout<<" JUG 1 "<<" JUG 2 \n";
cout<<"----------------\n";
if (i == -1)
cout << 0 << "\n";
else
{
cout << distance[i] << "\n";
trace(i);
}
cout << -1 << "\n";
getch();
}
OUTPUT
Please enter the number of gallons in first jug: 5
Please enter the number of gallons in second jug: 3
Please enter the vol. of water to be left finally: 4
JUG 1 JUG 2
—————-
7
0 | 0
5 | 0
2 | 3
2 | 0
0 | 2
5 | 2
4 | 3
-1
