Infinite loop when my stack is empty

Question

I am trying to use a Stack(Depth First Search) to solve a maze. I am having a few issues apart from the main issue which is I am currently getting an infinite loop once my stack becomes empty. I have a good understanding of what I need to do I am just having trouble applying it to my code.

I am following this Algorithm to solve the maze:

1.Create an empty stack

2.Search the array for the starting location.

3.Place the starting point onto the stack

4.Remove a point from the stack

5.Test to see if this point is the finish (If it is, end the loop)

6.Otherwise, mark the spot in the maze as evaluated to show path

7.Check spots in the maze that are neighboring the current location (up, down, left, right).

8.If they are not a wall, and haven’t already been evaluated, then add those points to the stack to be other locations to evaluate.

Solve Method with Helper Methods (most errors are in solveDFS())

    //Tries going up,down,left,or right from current location and
    //marks path if valid. The algorithm should finish when reaching
    //the finish spot
    public static boolean solveDFS( char [][] maze ){
    LinkedStack stack = new LinkedStack();
    Point startLoc = findPoint(maze,'s');
    Point finishLoc = findPoint(maze, 'f');
    stack.push(startLoc);

    Point[] neighborSpots = getNeighborSpots(startLoc);

    boolean test = true;
    while ( test ){
        stack.pop();
        if(stack.peek().equals(finishLoc)){
            printMaze(maze);
            test = false;
            return true;
        }else{
            for( Point evaluate : neighborSpots ){
                if( validSpot( stack, maze ) ){
                    placeMarker( stack, maze );
                    if( stack.peek().equals(evaluate)){
                        return true;
                    }
                    removeMarker( stack, maze);
                }
            }
        }
    }
    return false;
}
//Returns true of coordinates of free spot is valid or finish spot
//Should not be off edge of maze
private static boolean validSpot( LinkedStack spot, char [][] maze ){
    if ( spot.peek().x < 0 || spot.peek().x >= maze.length ||
            spot.peek().y < 0 || spot.peek().y >= maze[spot.peek().x].length ) {
        return false;
    }
    return ( maze[spot.peek().x][spot.peek().y] == ' ' || maze[spot.peek().x][spot.peek().y] == 'f' );
}
//Searches the array for a point
private static Point findPoint( char [][] maze, char c ) {
    for ( int i = 0; i < maze.length; i++ ) {
        for ( int j = 0; j < maze[i].length; j++ ) {
            if ( maze[i][j] == c ) {
                return new Point(i, j);
            }
        }
    }
    return null;
}
//returns an array containing coordinates of neighbor spots
private static Point[] getNeighborSpots( Point spot ) {
    Point[] neighborSpots = new Point[4];

    neighborSpots[0] = new Point(spot.x + 1, spot.y);
    neighborSpots[1] = new Point(spot.x, spot.y + 1);
    neighborSpots[2] = new Point(spot.x - 1, spot.y);
    neighborSpots[3] = new Point(spot.x, spot.y - 1);

    return neighborSpots;
}
//Marks the path by adding a '.'
private static void placeMarker( LinkedStack spot, char [][] maze ){
    maze[spot.peek().x][spot.peek().y] = '.';
}
//Removes marker from path by adding a blank space
private static void removeMarker ( LinkedStack spot, char [][] maze ) {
    maze[spot.peek().x][spot.peek().x] = ' ';
}

Answer 1

Your loop changes the loop variable (test) to false if you find a path (yet the effect is irrelevant, because you return directly from the method.

Your loop does never change the loop variable in other cases. Set testto false if all paths are done, and none is successful.

Or simply do not test a boolean variable but emptyness of the stack in your loop expression (while (!stack.isEmpty())).

Answer 2

You can not pop from or peek at the top of an empty stack. An implementation of a stack therefore needs to have a predicate (a boolean isEmpty() method) for checking whether the stack is empty. Code that peeks at or pops from the stack must use this predicate and handle the case of an empty stack as a special case, or must be written in a manner that guarantees it never manipulates an empty stack. The latter is harder and rarer in practice.

But what should the pop or peep method of a stack do if it is called for an empty stack? That is, if the method has been called in error? The method should signal the error by throwing a suitable unchecked exception. This will make it much easier to debug the error. Whether the stack is empty is part of the state information if the stack. So the stack is in a state that is invalid for the pop or peek method. So an IllegalStateException would be most suitable.

Answer 3

3.Place the starting point onto the stack

4.Remove a point from the stack

Are you sure its a good idea ?

Answer 4

I have tried to correct the logical errors in your code. The following code should work but it will not place your markers as desired:

public static boolean solveDFS( char [][] maze ){
    LinkedStack stack = new LinkedStack();
    Point startLoc = findPoint(maze,'s');
    Point finishLoc = findPoint(maze, 'f');
    stack.push(startLoc);
    while (!stack.isEmpty()) {
         Point curr = stack.pop();
         if(curr.equals(finishLoc)) {
             printMaze(maze);
             return true;
         } else {
            Point[] neighborSpots = getNeighborSpots(curr);
            for(Point evaluate: neighborSpots) {
                if(validSpot(stack, maze)) {
                    placeMarker(stack, maze);
                    stack.push(evaluate);
                    removeMarker(stack, maze);
                }
            }
        }
    }
    return false;
}