DFS stackoverflow error

Question

I'm doing an 8 piece puzzle game in java, and the assignment commands that i do a DFS to find the solution, starting at a random state.

i have a Node class, each Node object knows what state it is in using int[][] and what it's parent node is. Also it knows what direction it can move in (left, right, up, down)

     goal state:     start state (random):
     [0 1 2]         [1 8 0]
     [3 4 5]         [3 7 4]
     [6 7 8]         [2 5 6]

starting with a single node, the start node, my program creates a node for all of its possible children. It checks to see what available directions the blank square can move in, it checks that it is not going back to a state already belonging to another node. So in the example case above the start node would expand as follows:

          [1 8 0]
      A)  [3 7 4]
          [2 5 6]
         /       \
    [1 0 8]     [1 8 4]
B)  [3 7 4]     [3 7 0]  C)
    [2 5 6]     [2 5 6]
   /   /       /       \
...  ...  [1 8 4]     [1 8 4]
      D)  [3 0 7]     [3 7 6]  E)
          [2 5 6]     [2 5 0]
         /  /  /       /    \
     ... ... ... [1 8 4]     NO
             F)  [3 7 6]     CHILD
                 [2 0 5]
                /       \
             ...         ...

The way i handle this is that i explore the first node and push all of it's children to a stack, this happens in a recursive method which loops expanding each node until the goal state is reached or the cutoff is reached (a number i provide to avoid looping forever)

stack = [A]
pop()
stack = []
A -> B
push(B)
stack = [B]
A -> C
push(C)
stack = [C|B]
A -> NO MORE CHILDREN
pop()
stack = [B]
C -> D
push(D)
stack = [D|B]
C -> E
push(E)
stack = [E|D|B|]
C -> NO MORE CHILDREN
pop()
stack = [D|B|]
E -> F
push(F)
stack = [F|D|B]
E -> NO MORE CHILDREN
pup()
stack = [D|B]

The code works fine as long as my cutoff is not too high, if it is than i get the error: java.lang.StackOverflowError

What am i doing wrong?

public void expand(Node parent, int cutoff){
  cutoff--;

  int[][] currentState = parent.getState();

  if(Arrays.deepEquals(currentState, goalState)){
    found = true;
    goalNode = parent;
  }


  if(cutoff>0 && !found){
    if(parent.up){
      Node child = createUPnode();
      child.setParent(parent);
      stack.push(child);
      parent.up = false;
      expand(parent, cutoff)
    }
    else if(parent.right){
      Node child = createRIGHTnode();
      child.setParent(parent);
      stack.push(child);
      parent.right = false;
      expand(parent, cutoff)
    }
    else if(parent.down){
      Node child = createDOWNnode();
      child.setParent(parent);
      stack.push(child);
      parent.down = false;
      expand(parent, cutoff)
    }
    else if(parent.left){
      Node child = createLEFTnode();
      child.setParent(parent);
      stack.push(child);
      parent.left = false;
      expand(parent, cutoff)
    }
    else{
      Node nextNode = stack.pop();
      expand(nextNode, cutoff);
    }
  }
  else{
    System.out.println("CUTOFF REACHED");
  }
}

Answer 1

The post 'What is a stack overflow error?' contains a lot of information on what can cause a StackOverflowError in Java. The most common cause for this kind of error is a bad recursive call (causing an infinite loop). It seems you have already guarded against this by introducing a cutoff value for your recursive calls of expand().

But even with this delimiter the stack size may be to small to handle the recursive calls. I belief you have two options:

1) Use a 'small enough' value for your cutoff (this actually works, as you already wrote) but this limits your search depth.

2) Increase the stack size of the JVM. You can do this by adding the flag -Xss1024k as a VM argument. For more information on how to increase the stack size, read Java stack overflow error - how to increase the stack size in Eclipse?

Answer 2

It's simple to implement DFS or BFS using a Dequeue, without any recursion, just loop, reading from the head of the dequeue and generating new solutions to the tail (BFS). To use DSF add the children to the head.

I think you should use a Breadth-first search to find the shortest possible solution, right?

If you are certain about the depth first search (which makes little sense, i think) you can do away with the recursion and just use the dequeue you have created (not the call stack). The recusive calls are not needed. Just loop: start each loop by popping a node, generate its childs and push them on the dequeue's head, then start over. If the dequeue is empty there is no solution...

In most cases it's best to check if a generated solution already have been generated before adding them to the end of the queue, to reduce memory usage. Using plain Collections, a HashSet is probably quicker than a TreeSet- Remember to implement Node.equals() and Node.hashCode() properly.

I suppose that an ordinary LinkedList would be the most efficient Dequeue in this case - but why not test yourself.