title: Depth first search infinite loop code
body: <p>I'm trying to solve the missionaries and cannibals problem and I'm trying to implement a DFS algorithm to find the best solution. Unfortunately this code takes me to an infinite loop and I don't understand why. Can anyone help? Thank you!  </p>
  
  <pre><code>import java.util.*;
  
  public class DFS3 { 
  
      public State2 exec(State2 root) {       
          if (root==null)
              return null;
  
          Stack&lt;State2&gt; stack = new Stack&lt;State2&gt;();
          Set&lt;State2&gt; visitedNodes = new HashSet&lt;State2&gt;();
          //Add the root to the stack
          stack.push(root);
  
          while(!stack.isEmpty()) 
          {
              State2 n = stack.pop();
              //Check to see if node n is the requested node
              if(n.isGoal())          
                  return n;
              else
              {
                  //Create an array of the leaf nodes to node n
                  List&lt;State2&gt; children = n.generateSuccessors();
                  for(int i =0; i&lt;children.size(); i++)
                  {
                      //Add the leaf nodes to the stack
                      if ( !visitedNodes.contains(children.get(i)) ) {
                          stack.push(children.get(i));
                          visitedNodes.add(children.get(i));
                      }                
                      System.out.println(stack.peek());
                  }
              }
          }
          //Not found so return null
          return null;
     }
  }
  </code></pre>
  
  <p>And this is how I generate new succesors. </p>
  
  <pre><code>public List&lt;State2&gt; generateSuccessors() {
          List&lt;State2&gt; successors = new ArrayList&lt;State2&gt;();
          if (boat == Position.LEFT) {//la dreapta
              testAndAdd(successors, new State2(cL, mL - 2, Position.RIGHT,
                      cR, mR + 2)); // 2 misionari stanga-dreapta
              testAndAdd(successors, new State2(cL - 2, mL, Position.RIGHT,
                      cR + 2, mR)); // doi canibali stanga-dreapta
              testAndAdd(successors, new State2(cL - 1, mL - 1, Position.RIGHT,
                      cR + 1, mR + 1)); // un misionar si un canibal stanga-dreapta
              testAndAdd(successors, new State2(cL, mL - 1, Position.RIGHT,
                      cR, mR + 1)); // un misionar stanga-dreapta
              testAndAdd(successors, new State2(cL - 1, mL, Position.RIGHT,
                      cR + 1, mR)); //un canibal
          } else { //la stanga
              testAndAdd(successors, new State2(cL, mL + 2, Position.LEFT,
                      cR, mR - 2)); 
              testAndAdd(successors, new State2(cL + 2, mL, Position.LEFT,
                      cR - 2, mR)); 
              testAndAdd(successors, new State2(cL + 1, mL + 1, Position.LEFT,
                      cR - 1, mR - 1)); 
              testAndAdd(successors, new State2(cL, mL + 1, Position.LEFT,
                      cR, mR - 1)); 
              testAndAdd(successors, new State2(cL + 1, mL, Position.LEFT,
                      cR - 1, mR)); 
          }
          return successors;
      }
  
      private void testAndAdd(List&lt;State2&gt; successors, State2 newState) {
          if (newState.isValid()) {
              newState.setParentState(this);
              successors.add(newState);
          }
      }
  </code></pre>