Solving maze problem with backtracking solution using stack

Question

I solved the maze backtracking question using a stack however could not find any other solution like that anywhere (to validate my solution is actually a valid one).
The problem statement is as follows -

Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move right or down but certain cells are "off limit" such that the robot cannot step on them. design an algorithm to find a path for the robot from the top left to the bottom right

My Solution (java) is as follows -

public static boolean solve(boolean[][] maze) {
 int maxY = maze.length-1;
 int maxX = maze[0].length-1;
 int[] end = new int[]{maxY, maxX};
 int[] currentPosition = new int[]{0, 0};
 Stack<int[]> lastPosition = new Stack<>();
 lastPosition.push(currentPosition);
 while ( (currentPosition[0] != end[0] || currentPosition[1] != end[1]) 
 && !lastPosition.isEmpty()) {
 // get current position coordinates
 int y = currentPosition[0];
 int x = currentPosition[1];
 // Try moving right
 if(x+1 <= maxX && maze[y][x+1]) {
 currentPosition = new int[]{y,x+1}; // Move one step right
 lastPosition.push(currentPosition);
 } else if(y+1 <= maxY && maze[y+1][x]) { // Try moving down
 currentPosition = new int[]{y+1,x}; // Move one step down
 lastPosition.push(currentPosition);
 } else {
 maze[y][x] = false; // Mark as dead end (so we will not try to reach here again)
 currentPosition = lastPosition.pop();
 }
 }
 return !lastPosition.isEmpty();
 }

It looks like it works well (I tested it against several mazes to make sure), it should also run in O(rc) time at worst case (which is fine for the a maze of rc size) but everything else I've seen uses recursion or other methods to solve this problem. Am I missing something?

Will appreciate any kind of guidance.

Answer 1

Your solution looks correct. Your don't need to find a similar implementation to validate yours. You just need to verify yours works correctly, by stepping through the logic as if with a debugger, and verifying all execution paths, and considering all possible corner cases.

By the way, recursive solutions use a stack too, just implicitly. They take advantage of the function call stack, which stores the program state every time you step into a function, and pops it when leaving a function, returning to the caller. Manually implementing a stack based solution is typically less convenient, but more powerful and efficient, because you have full control over the stack and its entries, which can be perfectly sized.

Although your solution works, I would write it slightly differently:

• The logic would be slightly easier to understand if all the conditions of the movement were organized in the same if-else chain inside the loop
• Instead of adding the next position to the stack, it's more conventional to add the current one
• The Stack class is no longer recommended in Java, use Deque and ArrayDeque instead
• Instead of int[] end = new int[]{maxY, maxX};, a shorter more convenient form exists: int[] end = {maxY, maxX};. (Unfortunately this form works only at initialization, it doesn't work for assignment in general.)
• It's more natural to store coordinates as (x, y) pair instead of (y, x) pair

Like this:

public static boolean solve(boolean[][] maze) {
 int maxY = maze.length - 1;
 int maxX = maze[0].length - 1;
 Deque<int[]> stack = new ArrayDeque<>();
 int x = 0;
 int y = 0;
 while (true) {
 if (x == maxX && y == maxY) {
 // Found the exit!
 return true;
 } else if (x + 1 <= maxX && maze[y][x + 1]) {
 // Try moving right
 stack.push(new int[]{x + 1, y});
 x++;
 } else if (y + 1 <= maxY && maze[y + 1][x]) {
 // Try moving down
 stack.push(new int[]{x, y + 1});
 y++;
 } else if (!stack.isEmpty()) {
 // Mark as dead end (so we will not try to reach here again)
 maze[y][x] = false;
 int[] current = stack.pop();
 x = current[0];
 y = current[1];
 } else {
 // No way to go -> impossible to reach the exit
 return false;
 }
 }
}

• crazyPixel: Thanks for your answer! I have a question though - you wrote : "The Stack class is no longer recommended in Java, use Deque and ArrayDeque instead" - why is that? Also - am I right on my time complexity estimation? (will roughly go all way and return in every 2nd row thus O(rc) )
• janos: @crazyPixel See the javadoc of Stack, though it doesn't explain much about the reasoning. Stack extends Vector which is also not recommended, a poorly designed class from the early days of Java. More concretely, Vector is thread-safe, and when you don't need thread-safety, it's an unnecessary overhead.
• janos: @crazyPixel yes that is the correct time complexity