Finding a route in maze matrix

Question

Maze puzzle

A 1 in input matrix means "allowed"; 0 means "blocked". Given such a matrix, find the route from the 1st quadrant to the last (n-1, n-1).

I would like to get some feedback to optimize and make this code cleaner. Also let me know if O(n!) is the complexity, where n is the dimension of the maze.

final class Coordinate {
    private final int x;
    private final int y;

    public Coordinate(int x, int y) {
        this.x = x; 
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

public class Maze {

    private final int[][] maze;

    public Maze(int[][] maze) {
        if (maze == null) {
            throw new NullPointerException("The input maze cannot be null");
        }
        if (maze.length == 0) {
            throw new IllegalArgumentException("The size of maze should be greater than 0");
        }

        this.maze = maze;
    }

    public List<Coordinate> solve() {
        return getMazePath(0, 0, new Stack<Coordinate>());
    }

    private List<Coordinate> getMazePath(int row, int col, Stack<Coordinate> stack) {
        assert stack != null;

        stack.add(new Coordinate(row, col));

        if ((row == maze.length - 1) && (col == maze[0].length - 1)) {
            Coordinate[] coordinateArray = stack.toArray(new Coordinate[stack.size()]);
            return Arrays.asList(coordinateArray);
        }

        for (int j = col; j < maze[row].length; j++) {

            if ((j + 1) < maze[row].length && maze[row][j + 1] == 1) {
                return getMazePath(row, j + 1, stack);
            }

            if ((row + 1) < maze.length && maze[row + 1][col] == 1) {
                return getMazePath(row + 1, col, stack);
            }
        }

        return Collections.emptyList();
    }


    public static void main(String[] args) {
        int[][] m = {  {1, 0, 0},
                       {1, 1, 0},
                       {0, 1, 1} };

        Maze maze = new Maze(m);

        for (Coordinate coord :  maze.solve()) {
            System.out.println(coord.getX() + " : " + coord.getY());
        }
    }
}

Answer 1

First of all I don't think the time complexity is O(n!). You are doing DFS(unknowingly). So the time complexity would be O(n + m) and AFAIK you can't solve maze problem less than that unless you are using BFS. But nevertheless it will not make any difference.

Now your code has some bug, I think you didn't consider that way and it's ok if you are a beginner like me. Try to change the maze matrix to

int[][] m = {{1, 1, 1},
             {1, 0, 1},
             {1, 1, 0},                       
             {0, 1, 1}};

and you will get the picture. Maze can be solved but still it's not printing anything. So what is the solution? BACK-TRACK.

Moreover you are only taking account of possibilities of going right and down, why not up and left?

You have hard-coded that the start point will be always (0,0) and end point will be (N-1, N-1)... yeah your puzzle says that but this will not be same for every puzzle right? So think of a general solving technique...

SPOILER ALERT

Web resource

My solution

Code Cleaning Tips

1. getMazePath method can be cleaned. In 1st if you are checking if you have reached the goal or not. Now move the checking condition to another method and return true if you have reached the goal.
2. In for loop(no need of this if you are using recursion) you are checking if you are in the maze and path exists or not... see how you are repeating yourself for every condition... think of a general solution.
3. No need for maintaining a Stack, since you are not using any of Stack's method but only add, which you can also use with a List.
4. Override toString method in Coordinate class. And get rid of long S.o.p s.

Good Luck!

Answer 2

Your logic is just not correct, with the for-loop. Consider the following maze:

1000001
0000001
0000001
0000001

Your code will find a "solution" by jumping to the upper-right, then taking a path down to the finish.

Fix that, and the issues raised by @tintinmj, and then we might be able to analyze the complexity. Until then, it would be a meaningless discussion.