BFS Maze Solver returns false even when path found

Question

I'm currently working on a little maze solver project where you find the shortest path in a maze so as to get a better grasp on path searching algorithms; in this case the breadth-first search algorithm. It works by using a boolean visitation matrix to mark visited cells to avoid repeating steps, it works in the following steps.

Step 1: Uses visitation queue to holds the adjacent cells.

Step 2: Removes the cell at the front of the queue and adds it to a visitation list.

Step 3: Checks adjacent cells and if they aren't walls and they aren't visited, they'll be added to the visitation queue.

Then repeat the last two steps until the entire queue is empty.

However my maze solver strangely enough keeps returning false, even when it has found its way to the the end(i.e. the number 3). So all in all I have two questions, what is it that's causing it to return false even when it found the and what can be changed in the solver so that only the shortest path will have the number 2(i.e when it backtracks it'll turn the dead end paths back into 0s)?

Thanks in advance!

BFS Maze Solver

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    
    // Solves given maze iteratively, input starting position in maze and size of the maze.
    public static boolean solve(int[][] maze, int x, int y, int sizeX, int sizeY) {
        
        boolean[][] visited = new boolean[sizeX][sizeY];
        Queue<Point> vQueue = new LinkedList<Point>();
        vQueue.add(new Point(x, y, null));
        maze[x][y] = 2;
        visited[x][y] = true;
        
        while (!vQueue.isEmpty()) {
            
            Point p = vQueue.remove();
            
            // 3 is the cell the algorithm is supposed to find.
            if (maze[p.x][p.y] == 3) {
                maze[p.x][p.y] = 2;
                return true;
            }
            
            // Down.
            if (visited[p.x-1][p.y] == false && (maze[p.x-1][p.y] == 0 || maze[p.x-1][p.y] == 3)) {
                maze[p.x-1][p.y] = 2;
                visited[p.x-1][p.y] = true;
                Point nextPoint = new Point(p.x-1, p.y, p);
                vQueue.add(nextPoint);
            }
            
            // Up.
            if (visited[p.x+1][p.y] == false  && (maze[p.x+1][p.y] == 0 || maze[p.x+1][p.y] == 3)) {
                maze[p.x+1][p.y] = 2;
                visited[p.x+1][p.y] = true;
                Point nextPoint = new Point(p.x+1, p.y, p);
                vQueue.add(nextPoint);
            }
            
            // Right.
            if (visited[p.x][p.y+1] == false  && (maze[p.x][p.y+1] == 0 || maze[p.x][p.y+1] == 3)) {
                maze[p.x][p.y+1] = 2;
                visited[p.x][p.y+1] = true;
                Point nextPoint = new Point(p.x, p.y+1, p);
                vQueue.add(nextPoint);
            }
            
            // Left.
            if (visited[p.x][y-1] == false  && (maze[p.x][p.y-1] == 0 || maze[p.x][p.y-1] == 3)) {
                maze[p.x][p.y-1] = 2;
                visited[p.x][p.y-1] = true;
                Point nextPoint = new Point(p.x, p.y-1, p);
                vQueue.add(nextPoint);
            }
        }
        
        return false;
    }
    
    // Node class that holds current position and visitation list.
    private static class Point{
        int x;
        int y;
        Point parent;
        
        public Point(int x, int y, Point parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;
        }
        
        
    }
    
}

Test Maze

public class TestMazeDFS {
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},        
            {1, 0, 0, 0, 0, 0, 0, 0, 1},
            {1, 0, 1, 0, 1, 1, 1, 1, 1},
            {1, 0, 1, 0, 0, 0, 0, 0, 1},
            {1, 1, 1, 1, 1, 0, 1, 0, 1},
            {1, 0, 0, 0, 1, 0, 1, 0, 1},
            {1, 0, 1, 1, 1, 1, 1, 0, 1},
            {1, 0, 0, 0, 0, 0, 0 ,3, 1},
            {1, 1, 1, 1, 1, 1, 1, 1, 1},
        };
    
    public int[][] getMaze(){
        
        return this.maze;
    }
    
    // prints the maze.
    public static void printMaze() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
//              if (maze[i][j] == 1) {
//                  System.out.print('#');
//              } else {
//                  System.out.print(' ');
//              }
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        TestMazeDFS maze = new TestMazeDFS();
        boolean test = BFS.solve(maze.getMaze(), 1, 1, 9, 9);
        System.out.println(test);
        printMaze();
        
    }
}

Answer 1

The problem seems to be you change the state of maze nodes before you explore them.

The simplest example is a graph where the source and destination are the same point.
You first set this point: maze[x][y] = 2 - and only then you will explore it, and check if its value is 3. But it's no longer the case.

To solve it, you should set the values of maze[x'][y'] to 2 only when you explore the node, and not when you add it to queue.