Rat in a Maze in Java
Problem
Rat in a Maze asks for a path through a grid of open and blocked cells from the top-left corner to the bottom-right, moving only through open cells — a move that leads to a dead end has to be undone and a different move tried instead.
Given a grid of open (1) and blocked (0) cells, find a path from the top-left corner to the bottom-right corner using only down and right moves.
Java Program
public class RatInAMaze {
static boolean solve(int[][] maze, int row, int col, int[][] path) {
int n = maze.length;
if (row == n - 1 && col == n - 1 && maze[row][col] == 1) {
path[row][col] = 1;
return true;
}
if (row < 0 || col < 0 || row >= n || col >= n || maze[row][col] == 0 || path[row][col] == 1) {
return false;
}
path[row][col] = 1; // mark this cell as part of the current path
if (solve(maze, row + 1, col, path) || solve(maze, row, col + 1, path)) {
return true;
}
path[row][col] = 0; // backtrack: this cell doesn't lead to the destination
return false;
}
public static void main(String[] args) {
int[][] maze = {
{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{0, 1, 1, 1}
};
int n = maze.length;
int[][] path = new int[n][n];
boolean found = solve(maze, 0, 0, path);
if (found) {
StringBuilder sb = new StringBuilder();
for (int[] row : path) {
for (int i = 0; i < row.length; i++) {
if (i > 0) sb.append(" ");
sb.append(row[i]);
}
sb.append("\n");
}
System.out.print(sb);
} else {
System.out.println("No path found");
}
}
}Output
Core Logic
Marking the current cell as part of the path, trying to reach the destination by moving down or right, and unmarking the cell if neither move works, explores every possible path without needing to track visited cells separately.
- 1The destination check
row == n - 1 && col == n - 1only succeeds if that final cell is also open, confirming a complete path was found. - 2The rejection check catches an out-of-bounds move, a blocked cell, or a cell already part of the current path, all in one condition.
- 3
path[row][col] = 1marks the current cell as part of the path before either recursive move is attempted. - 4If neither the down move nor the right move reaches the destination,
path[row][col] = 0undoes the mark — this cell isn't part of any working path after all, so it has to be cleared before the caller tries its own next option.
Key Point: The unmark step only runs when a path attempt fails — a successful path returns immediately without ever clearing its own marks, since those marks are exactly the answer being built.
Why: Restricting movement to just down and right means each cell is visited at most once along any single path attempt, giving roughly 2^n possible move sequences for an n-step path, while the path grid itself holds n² cells.
Key Concepts
Approach 2: Four-Directional Movement
public class RatInAMazeFourDirections {
static boolean solve(int[][] maze, int row, int col, int[][] path) {
int n = maze.length;
if (row == n - 1 && col == n - 1 && maze[row][col] == 1) {
path[row][col] = 1;
return true;
}
if (row < 0 || col < 0 || row >= n || col >= n || maze[row][col] == 0 || path[row][col] == 1) {
return false;
}
path[row][col] = 1;
// Tries all four directions, not just down and right
if (solve(maze, row + 1, col, path) || solve(maze, row, col + 1, path)
|| solve(maze, row - 1, col, path) || solve(maze, row, col - 1, path)) {
return true;
}
path[row][col] = 0; // backtrack
return false;
}
public static void main(String[] args) {
int[][] maze = {
{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{0, 1, 1, 1}
};
int n = maze.length;
int[][] path = new int[n][n];
solve(maze, 0, 0, path);
StringBuilder sb = new StringBuilder();
for (int[] r : path) {
for (int i = 0; i < r.length; i++) {
if (i > 0) sb.append(" ");
sb.append(r[i]);
}
sb.append("\n");
}
System.out.print(sb);
}
}
Output
Core Logic
Allowing movement in all four directions — up, down, left, right — finds a path in mazes where a down/right-only search would incorrectly report no solution, at the cost of needing an explicit visited check to avoid looping forever.
- 1Every recursive call tries all four neighboring cells, not just down and right, so a maze that only has a valid path through a leftward or upward step can still be solved.
- 2A cell is skipped if it's out of bounds, blocked, or already marked as part of the current path — that last check is what prevents the search from bouncing back and forth between two cells forever.
- 3The same mark-then-try-then-unmark backtracking pattern applies, just across four recursive calls per cell instead of two.
- 4For this particular maze, moving in extra directions doesn't change the answer — the same down/right path is still found, since it was reachable that way to begin with.
Key Point: The four-directional version is strictly more capable than the down/right-only one, at the cost of a visited check and a larger search space — worth it whenever a maze's solution genuinely requires backtracking away from the destination first.
Why: Each of the n² cells can branch into up to four recursive calls before backtracking, so the worst-case search space grows exponentially with the number of cells rather than just the path length.