Solving a Maze Using Queue in Java

Question

My homework is to determine if a maze is solvable of not using Queue. If it is, print the path. I can get Queue to get to the end but it says it's unsolvable. When actually it is. If I change the Final check if Statement to:

if (queue.isEmpty())
    {
        System.out.println("The maze is solvable!");
    }
else
    {
        System.out.println("The maze is unsolvable!");
    }

Then it says it is solvable, but then when I try another maze that isn't solvable it says it is solvable. Not sure where I'm going wrong.

I have a separate Point class that defines the Points and right, left, above and below positions. I have to use Point (0,0) to mark the start and Point (row-1,col-1) to mark the goal.

Let me know if you need more code. It is searching a char 2D array.

maze1.txt - (First Line Defines the # of Rows and Columns) - Is Solvable

7 12
..+.+.++++++
.++...++...+
..++.....+.+
+.+..++.+..+
+...++....++
+.+++..++..+
++++++++++..

Says it's unsolvable

    QueueMaze
The maze is unsolvable!
p p + p + p + + + + + + 
p + + p p p + + p p p + 
p p + + p p p p p + p + 
+ p + p p + + p + p p + 
+ p p p + + p p p p + + 
+ p + + + p p + + p p + 
+ + + + + + + + + + p .

mMethod for solving the Maze

public void queueMaze() {

char[][] storedMaze = copy(); 

LinkedList<Point> queue = new LinkedList<Point>();
    int count = 0;
    Point start = new Point(0,0);
    Point cur, end, above, right, left, below;

    Boolean solved = false;

queue.add(start); 

while (!queue.isEmpty())
    {
    //Store the first element position 0 in cur
        cur = queue.removeFirst();
        //System.out.println(cur.toString());

        //compare cur's points to the isEnd points
        //(row-1, col-1) if it is the end, break out
        //of the While
        if (isEnd(cur) && isSafe(cur))
        {
            //System.out.println("cur's final : " + cur.toString());
            end = cur;
            break;
        }

        //mark cur as visited with a P
    markVisited(cur, P);

        //check the position above cur to see if it is
        //
    right = cur.getRight(); 
    if (inBounds(right) && isSafe(right))
        {
            queue.add(right);
        }

        below = cur.getBelow(); 
    if (inBounds(below) && isSafe(below))
        {
            queue.add(below);
        }

        left = cur.getLeft(); 
    if (inBounds(left) && isSafe(left))
        {
            queue.add(left);
        }

        above = cur.getAbove(); 
    if (inBounds(above) && isSafe(above))
        {
            queue.add(above);
        }

}//while
//System.out.println("The queue size is: " + queue.size());

    if (!queue.isEmpty())
    {
        System.out.println("The maze is solvable!");
    }
else
    {
        System.out.println("The maze is unsolvable!");
    }

print();

returnMaze(storedMaze);
}

Doesn't depth first search use Stack? I have to use Queue which is similar to Breadth-first search right? — handro
possible duplicate of Getting Stuck in a Maze using Stack/Queue in Java — Dave Newton
I posted both questions. But the other question was using stack and this is using Queue. I got the other one figured out and answered it. I didn't want to add to it because it would become bigger then it already was. — handro

Alex Lynch Alex Lynch · Accepted Answer · 2012-10-28T23:30:07

the queue being empty does not determine whether or not the maze is solved. the queue simply keeps track of which spaces still need to be checked. it is perfectly fine to come to the end of the maze with lots of spaces left to check in your queue.

it looks like if your if (isEnd(cur) && isSafe(cur)) is triggered, then the maze is solveable.

Solving a Maze Using Queue in Java

1 Answers