Share with others

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


Share with others