Water Jug Problem using Depth First Search

Problem Statement:

In a Water Jug Problem you are given two jugs, one 4-gallon and one 3-gallon, a pump which has unlimited water which you can use to fill the jug, and the ground on which water may be poured. Neither jug has any measuring markings on it. How can you get exactly 2 gallons of water in the 4-gallon jug?

This problem can be solve using multiple techniques of Artificial Intelligence (AI). Here we are going to solve the Water Jug Problem using the Depth First Search (DFS) Algorithm. To solve the problem with Breath First Search (BFS), check it here.

Here is the code for the current problem statement.

Firstly, let include all the header files. Now we have to define a structure for the nodes which we are going to use it for the further process. Below code snippet of code is for the same.

#include<stdio.h>
#include<conio.h>
struct node
{
 int x, y;
 struct node *next;
}*root, *left, *right;

Now we have to check weather the node which is generated previously or not. If it is generated early we have to skip that node because it will generate a cycle in the structure which will behave as a graph and not a tree and it will be not acceptable as the desired result.

int isNodePresent(struct node *nextState, int maxJug1, int maxJug2, int reqJug1, int reqJug2)
{
 struct node *temp;
 if((nextState->x == reqJug1) && (nextState->y == reqJug2))
  return(0);
 if((nextState->x == maxJug1) && (nextState->y == maxJug2))
  return(1);
 if((nextState->x == 0) && (nextState->y == 0))
  return(1);
 temp = left;
 while(1)
 {
  if((temp->x == nextState->x) && (temp->y == nextState->y))
   return(1);
  else if(temp->next == NULL)
   break;
  else
   temp = temp->next;
 } 
 temp = right;
 while(1)
 {
  if((temp->x == nextState->x) && (temp->y == nextState->y))
   return(1);
  else if(temp->next == NULL)
   break;
  temp = temp->next;
 }
 return(0);
}

As we had already define the structure of our required node, we have to just simply use that structure and generate a node to store the value of the manipulated gallons and use it to generate a tree.

struct node* genNewState(struct node *crntState, int maxJug1, int maxJug2, int reqJug1, int reqJug2)
{
 int d;
 struct node *nextState;
 nextState = (struct node*)malloc(sizeof(struct node));
 nextState->x = maxJug1;
 nextState->y = crntState->y;
 if(isNodePresent(nextState, maxJug1, maxJug2, reqJug1, reqJug2) != 1)
  return(nextState);
 nextState->x = crntState->x;
 nextState->y = maxJug2;
 if(isNodePresent(nextState, maxJug1, maxJug2, reqJug1, reqJug2) != 1)
  return(nextState);
 nextState->x = 0;
 nextState->y = crntState->y;
 if(isNodePresent(nextState, maxJug1, maxJug2, reqJug1, reqJug2) != 1)
  return(nextState);
 nextState->y = 0;
 nextState->x = crntState->x;
 if(isNodePresent(nextState, maxJug1, maxJug2, reqJug1, reqJug2) != 1)
  return(nextState);
 if((crntState->y < maxJug2) && (crntState->x != 0))
 {
  d = maxJug2 - crntState->y;
  if(d >= crntState->x)
  {
   nextState->x = 0;
   nextState->y = crntState->y + crntState->x;
  }
 else
 {
  nextState->x = crntState->x - d;
  nextState->y = crntState->y + d;
 }
 if(isNodePresent(nextState, maxJug1, maxJug2, reqJug1, reqJug2) != 1)
  return(nextState);
 }
 if((crntState->x < maxJug1) && (crntState->y != 0))
 {
  d = maxJug1 - crntState->x;
  if(d >= crntState->y)
  {
   nextState->y = 0;
   nextState->x = crntState->x + crntState->y;
  }  
  else
  { 
   nextState->y = crntState->y - d;
   nextState->x = crntState->x + d;
  }
  if(isNodePresent(nextState, maxJug1, maxJug2, reqJug1, reqJug2) != 1)
   return(nextState);
 }
 return(NULL);
}

As all the nodes are ready by there values stored in it, we have to now assemble all the nodes and generate the tree of the give problem statement.

void generateTree(int maxJug1, int maxJug2, int reqJug1, int reqJug2)
{
 int flag1, flag2;
 struct node *tempLeft, *tempRight;
 root  = (struct node*)malloc(sizeof(struct node));
 root->x = 0; root->y = 0; root->next = NULL;
 left = (struct node*)malloc(sizeof(struct node));
 left->x = 0; left->y = maxJug2; left->next = NULL;
 right = (struct node*)malloc(sizeof(struct node));
 right->x = maxJug1; right->y = 0; right->next = NULL;
 tempLeft = left;
 tempRight = right;
 while(1)
 {
  flag1 = 0; flag2 = 0;
  if((tempLeft->x != reqJug1) || (tempLeft->y != reqJug2))
  {
   tempLeft->next = genNewState(tempLeft, maxJug1, maxJug2, reqJug1, reqJug2);
   tempLeft = tempLeft->next;
   tempLeft->next = NULL;
   flag1 = 1;
  }
  if((tempRight->x != reqJug1) || (tempRight->y != reqJug2))
  {
   tempRight->next = genNewState(tempRight, maxJug1, maxJug2, reqJug1, reqJug2);
   tempRight = tempRight->next;
   tempRight->next = NULL;
   flag2 = 1;
  }
  if((flag1 == 0) && (flag2 == 0))
   break;
 }
}

Now we have to display the result of the give value of the gallons to the problem statement which can be done from the following way.

void DFS() 
{
 struct node *temp;
 temp = left;
 printf("DFS ANSWER IS==>\nStart State:(%d , %d)\n", root->x, root->y);
 printf("DFS Result 1:\n");
 while(1)
 {
  printf("(%d , %d)\n", temp->x, temp->y);
  if(temp->next == NULL)
   break;
  temp = temp->next;
 }
 temp = right;
 printf("DFS Result 2:\n");
 while(1)
 {
  printf("(%d , %d)\n", temp->x, temp->y);
  if(temp->next == NULL)
   break;
  temp = temp->next;
 }
}

Finally we are writing a main() method by which all these functions are called and get the output of the give input values in the form of the litre of the gallons.

int main()
{
 int maxJug1, maxJug2, reqJug1, reqJug2;
 printf("Enter the maximum capacity of jug1:");
 scanf("%d", &maxJug1);
 printf("Enter the maximum capacity of jug2:");
 scanf("%d", &maxJug2);
 printf("Enter the required water in jug1:");
 scanf("%d", &reqJug1);
 printf("Enter the required water in jug2:");
 scanf("%d", &reqJug2);
 generateTree(maxJug1, maxJug2, reqJug1, reqJug2);
 DFS();
 getch();
 return 0;
}

Happy Coding :)