DFS Maze Solver returns false when correct

Question

I'm currently working on a little maze solver project to get a better grasp of algorithms like depth-first search. It works in that turns the current position to 2, then checks one of the positions(up, down, left or right) if it's a 0(path) and it will move forward until it's surrounded by cells are 1s(walls) then it's a dead end and it backtracks.

However my maze solver strangely enough keeps returning false, even when it has found its way to the number 3(the end). So I have two questions, what is causing it to return false 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 path into something else)?

Thanks in advance!

Maze solver

public class DFS {
    
    private int[][] maze;
    
    public DFS(int[][] maze) {
        
        this.maze = maze;
    }
    
    // Solves given maze recursively, input starting position in maze.
    public boolean solve(int x, int y) {
        
        maze[x][y] = 2;
        
        // 3 is the cell the algorithm is supposed to find.
        if (maze[x][y] == 3) {
            return true;
        }
        
        // Looks up.
        if (x > 0 && maze[x-1][y] == 0  && solve (x-1, y) ) {
            maze[x][y] = 2;
            return true;
        }
        // Looks down
        if (x < maze.length && maze[x+1][y] == 0  && solve (x+1, y) ) {
            maze[x][y] = 2;
            return true;
        }
        // Looks right.
        if (y < maze.length && maze[x][y+1] == 0  && solve (x, y+1) ) {
            maze[x][y] = 2;
            return true;
        }
        // Looks left.
        if (y > 0 && maze[x][y-1] == 0  && solve (x, y-1) ) {
            maze[x][y] = 2;
            return true;
        }
        
        return false;
    }
    
}

Hardcoded maze

import java.util.ArrayList;

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 ,0, 1},
            {1, 1, 1, 1, 1, 1, 1, 3, 1},
        };
    
    public int[][] getMaze(){
        
        return this.maze;
    }
    
    public static void main(String[] args) {
        
        DFS dfs = new DFS(maze);
        boolean test = dfs.solve(1, 1);
        System.out.println(test);
        
    }
}

Image of the solution when printed. https://i.sstatic.net/8lWo3.jpg

Answer 1

A quick look tells me you're doing this wrong:

        maze[x][y] = 2;
        
        // 3 is the cell the algorithm is supposed to find.
        if (maze[x][y] == 3) { // <-- It will never be 3
            return true;
        }

Also in every if-check: if (x > 0 && maze[x-1][y] == 0 && solve (x-1, y) ) {, you're only visiting neighbors with value 0. So for obvious reasons, you'll never visit a cell with value 3. The if-check should be something like: if (x > 0 && (maze[x-1][y] == 0 || maze[x-1][y] == 3) && solve (x-1, y) ) {

And do note that when backtracking, you need to revert the state back to the original state. That is, maze[x][y] should have the original value when you're returning false.

Maybe try this?

    public boolean solve(int x, int y) {
        // 3 is the cell the algorithm is supposed to find.
        if (maze[x][y] == 3) {
            maze[x][y] = 2;
            return true;
        }

        int orig = maze[x][y];
        maze[x][y] = 2;
        
        // Looks up.
        if (x > 0 && (maze[x-1][y] == 0 || maze[x-1][y] == 3)  && solve (x-1, y) ) {
            //maze[x][y] = 2;
            return true;
        }
        // Looks down
        if (x < maze.length && (maze[x+1][y] == 0 || maze[x+1][y] == 3)  && solve (x+1, y) ) {
            //maze[x][y] = 2;
            return true;
        }
        // Looks right.
        if (y < maze.length && (maze[x][y+1] == 0 || maze[x][y+1] == 3)  && solve (x, y+1) ) {
            //maze[x][y] = 2;
            return true;
        }
        // Looks left.
        if (y > 0 && (maze[x][y-1] == 0 || maze[x][y-1] == 3)  && solve (x, y-1) ) {
            //maze[x][y] = 2;
            return true;
        }

        maze[x][y] = orig;
        return false;
    }

Working solution: https://onlinegdb.com/ryxoPKgCaw