Iterative deepening depth first search in a 2d array

Question

I am trying to implement iterative deepening search in a 2d array (a maze).

static void Run_Ids(int x, int y)
    {
        int depth_limit = 0;

        while(!cutoff)
        {   
            out.println("Doing search at depth: " + depth_limit);             
            depthLimitedSearch(x, y, depth_limit);
            depth_limit++;
        }      
    }

And here's my Limited depth first search using a stack. For some reason, it goes back and forth between two cells. It doesn't expand like it should. I think its something wrong with my DFS algorithm here.

static void depthLimitedSearch(int x, int y, int depth){        
    Pair successor;    //pair is the x, y co-ordinate
    successor = starting();  //set the successor to starting cell

    stack = new Stack<>();
    int i = 0;
    stack.push(successor);

    while (!stack.isEmpty())
    {
        out.println("i level: " + i);
        Pair parent = stack.peek();   //pop it here?

        if (parent.x == Environment.goal[0] && parent.y == Environment.goal[1]){  //check to see if it is the goal
            cutoff = true;
            out.println("goal found ");                
            break;
        }
        if (i == depth){
            //stack.pop();   //pop here?
            break;
        }
        else{

            Pair  leftPos,rightPos,upPos,downPos;
            leftPos = leftPosition(parent.x, parent.y);
            rightPos = rightPosition(parent.x, parent.y);
            upPos = upPosition(parent.x, parent.y);
            downPos = downPosition(parent.x, parent.y);


            if(Environment.isMovePossible(rightPos.x, rightPos.y))
                                        //if it can go right
                   stack.push(rightPos);   

            if(Environment.isMovePossible(leftPos.x, leftPos.y))
                                       // if it can go left
                   stack.push(leftPos);

             if(Environment.isMovePossible(downPos.x, downPos.y))
                                     //if it can go down
                  stack.push(downPos);

            if(Environment.isMovePossible(upPos.x, upPos.y))                
                                        //if it can go up
                    stack.push(upPos);


            stack.pop();         //pop here?


        }  //else       

        i++;

    }//while     
}

I don't have that much experience with stack, and i am confused as to where to push it and where to pop. if somebody in here can point me to the right direction, that would be great!

Answer 1

I think you have to mark the positions of the array that you already visited to avoid re-visiting them. Don't push to the stack any positions that you already visited.

Without doing so, you are very likely to end up in an infinite loop:

For example, suppose that from your initial position you can advance in all directions - left, right, up and down. So you push those 4 positions, and then pop the last one you pushed - down.

Now, as long as down is a valid direction, you'll continue going down. When you reach a position from which you can't go down, you'll push the next valid directions, which include up (the direction you just came from).

Since you are pushing up to the stack just before pushing down, when you reach the position in which you can't push down, up would be the last position pushed, which means you'll then pop the up position and go to the position you came from.

From there you'll go back down and then back up in an infinite loop.