Breadth-First Search heuristics to find solution to Water Jug Challenge I started learning AI recently. In AI, searches should be avoided and everything in AI is a search problem.

One of the easiest problem where we could use general AI search techniques is the water jug problem which states:


  You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring markers on it. There is a tap that can be used to fill the jugs with water. How can you get exactly 2 gallons of water into the 4-gallon jug?


I solved it using the BFS technique:

#include &lt;bits/stdc++.h&gt;

using namespace std;

vector &lt;pair&lt;int,int&gt; &gt; newStatesSet(pair&lt;int,int&gt; state){
  //generating all possible states from a given initial state
  vector&lt;pair&lt;int,int&gt; &gt; newStates;
  if(state.first==0 &amp;&amp; state.second==0){
    newStates.push_back(make_pair(3,0));
    newStates.push_back(make_pair(0,4));
    newStates.push_back(make_pair(3,4));
  }
  if(state.first!=0 &amp;&amp; state.second==0){
    newStates.push_back(make_pair(state.first,4));
    newStates.push_back(make_pair(0,state.first));
    if(state.first&lt;3){
      newStates.push_back(make_pair(3,0));
      newStates.push_back(make_pair(3,4));
    }
  }
  if(state.first==0 &amp;&amp; state.second!=0){
    int transferQuantity;
    if(state.second&gt;3)
      transferQuantity=3;
    else
      transferQuantity=state.second;
    newStates.push_back(make_pair(transferQuantity,state.second-transferQuantity));
    newStates.push_back(make_pair(3,state.second));
  }
  if(state.first!=0 &amp;&amp; state.second!=0){
    newStates.push_back(make_pair(0,state.second));
    newStates.push_back(make_pair(state.first,0));
    if(state.second&lt;4){
      int transferQuantity1=state.second+state.first;
      int transferQuantity2;
      if(transferQuantity1&gt;4){
        transferQuantity2=transferQuantity1-4;
        transferQuantity1=4;
      }
      else
        transferQuantity2=0;
      newStates.push_back(make_pair(transferQuantity2,transferQuantity1));
    }
    if(state.first&lt;3){
      int transferQuantity1=state.second+state.first;
      int transferQuantity2;
      if(transferQuantity1&gt;3){
        transferQuantity2=transferQuantity1-3;
        transferQuantity1=3;
      }
      else
        transferQuantity2=0;
      newStates.push_back(make_pair(transferQuantity1,transferQuantity2));
    }
  }
  return newStates;
}

bool checkGoal(pair&lt;int,int&gt; x,int sum){
  if(x.second==sum)
    return true;
  return false;
}

void reverseTraversal(map &lt;pair&lt;int,int&gt;,pair&lt;int,int&gt; &gt; parent,pair&lt;int,int&gt; initialState,pair&lt;int,int&gt; goalState){
  if(initialState != goalState){
    reverseTraversal(parent,parent[initialState],goalState);
  }
  cout&lt;&lt;"("&lt;&lt;initialState.first&lt;&lt;","&lt;&lt;initialState.second&lt;&lt;")"&lt;&lt;endl;
}

int main()
{
  //capacity (3,4)  
  //open list
  queue &lt;pair&lt;int,int&gt; &gt; Q;
  pair &lt;int,int&gt; parNode;
  //contains all the states
  map &lt; pair&lt;int,int&gt; ,int &gt; occured;
  //contains parent
  map &lt; pair&lt;int,int&gt;,pair&lt;int,int&gt; &gt; parent;

  Q.push(make_pair(0,0));
  while(Q.empty()!=true){
    parNode=Q.front();
    Q.pop();
    if(checkGoal(parNode,2))
      break;
    occured[parNode]++;
    vector &lt;pair&lt;int,int&gt; &gt; leafs = newStatesSet(parNode);
    for(int i=0;i&lt;leafs.size();i++){
      if(occured[leafs[i]]==0){
        Q.push(leafs[i]);
        parent[leafs[i]]=parNode;
      }
    }
  }
  reverseTraversal(parent,parNode,make_pair(0,0));
}


What do you think is wrong with this code, and how can it be improved? What corner case have I overlooked, if any? How can I make it less complicated?



Improvements based on suggestion can be found here
I think that the function that computes new states could be simplified in this way:

vector &lt;pair&lt;int,int&gt; &gt; newStatesSet(pair&lt;int,int&gt; state){
  //generating all possible states from a given initial state
  vector&lt;pair&lt;int,int&gt; &gt; newStates;

  if (state.first &lt; 3) {
    newStates.push_back(make_pair(3, state.second));
  }
  if (state.second &lt; 4) {
    newStates.push_back(make_pair(state.first, 4));
  }
  if (state.first &gt; 0) {
    newStates.push_back(make_pair(0, state.second));
  }
  if (state.second &gt; 0) {
    newStates.push_back(make_pair(state.first, 0));
  }
  if (state.second &gt; 0 &amp;&amp; state.first &lt; 3) {
    newStates.push_back(make_pair(std::min(3, state.first + state.second),
                        std::max(state.second - (3 - state.first), 0)));
  }
  if (state.first &gt; 0 &amp;&amp; state.second &lt; 4) {
    newStates.push_back(make_pair(std::max(state.first - (4 - state.second), 0),
                        std::min(4, state.second + state.first)));
  }

  return newStates;
}


Note that with this function a new state is generated from the previous state by considering a single operation. So, for instance, from the state (0, 0) it produces (3, 0) and (0, 4), but not (3, 4) (which will be generated later) as in your function. I think that this reflect more correctly the idea that each state is derived from the previous one with a single step.