Rat in a Maze in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int maze[4][4] = {
{1,0,0,0},
{1,1,0,1},
{0,1,0,0},
{1,1,1,1}}, path[4][4], N=4;
void print(){
    for(int i=0;i<N;i++,puts(""))
        for(int j=0;j<N;j++)
            printf("%d ", path[i][j]);
    puts("");
}
void solve(int x, int y){
    if(x>=N || y>=N || !maze[x][y] || path[x][y]) return;
    path[x][y] = 1;
    if(x==N-1 && y==N-1) { print(); path[x][y]=0; return; }
    solve(x+1,y);
    solve(x,y+1);
    path[x][y] = 0;
}
int main() { solve(0,0); }

C Output

Input:  
1 0 0 0  
1 1 0 1  
0 1 0 0  
1 1 1 1  

Output:  
1 0 0 0  
1 1 0 0  
0 1 0 0  
0 1 1 1

C++ Program

#include <iostream>
using namespace std;
int maze[3][3] = {
{1,1,0},
{0,1,0},
{0,1,1}}, path[3][3], N=3;
void print(){
    for(int i=0;i<N;i++,cout<<endl)
        for(int j=0;j<N;j++)
            cout<<path[i][j]<<" ";
    cout<<endl;
}
void solve(int x,int y){
    if(x>=N||y>=N||!maze[x][y]||path[x][y]) return;
    path[x][y]=1;
    if(x==N-1 && y==N-1){ print(); path[x][y]=0; return; }
    solve(x+1,y);
    solve(x,y+1);
    path[x][y]=0;
}
int main(){ solve(0,0); }

C++ Output

Input:  
1 1 0  
0 1 0  
0 1 1 

Output:  
1 1 0  
0 1 0  
0 1 1

JAVA Program

public class Main {
    static int[][] maze = {
        {1,0,0},
        {1,1,0},
        {0,1,1}}, path = new int[3][3];
    static int N = 3;
    static void print(){
        for(int[] r : path){
            for(int v : r) System.out.print(v+" ");
            System.out.println();
        }
        System.out.println();
    }
    static void solve(int x, int y){
        if(x>=N||y>=N||maze[x][y]==0||path[x][y]==1) return;
        path[x][y]=1;
        if(x==N-1 && y==N-1){ print(); path[x][y]=0; return; }
        solve(x+1,y);
        solve(x,y+1);
        path[x][y]=0;
    }
    public static void main(String[] args){ solve(0,0); }
}

JAVA Output

Input:  
1 0 0  
1 1 0  
0 1 1

Output:  
1 0 0  
1 1 0  
0 1 1

Python Program

maze = [[1,0,0,0],
        [1,1,0,1],
        [0,1,0,0],
        [1,1,1,1]]
n = 4
path = [[0]*n for _ in range(n)]
def print_path():
    for r in path: print(r)
    print()
def solve(x, y):
    if x>=n or y>=n or maze[x][y]==0 or path[x][y]==1: return
    path[x][y] = 1
    if x==n-1 and y==n-1: print_path(); path[x][y]=0; return
    solve(x+1, y)
    solve(x, y+1)
    path[x][y] = 0
solve(0,0)

Python Output

Input:  
1 0 0 0  
1 1 0 1  
0 1 0 0  
1 1 1 1 

Output:  
[1, 0, 0, 0]  
[1, 1, 0, 0]  
[0, 1, 0, 0]  
[0, 1, 1, 1]

In-Depth Explanation

Example

The rat begins at (0,0) in the C version and can move only right or down. It follows all the possible paths until it arrives at (n-1,n-1). The path matrix remembers the current valid path. If a move is towards a dead-end, the function gets back and unmarks the cell.

Real-Life Analogy

Consider walking through a building when there is a power outage. Every hallway is either open (1) or closed (0). The objective is to get to the exit door (bottom-right) by only taking permitted pathways. You cannot move up or left. If a path is closed, you reverse and attempt another.

Why It Matters

This timeless backtracking problem illustrates how to:

Walk through grids recursively

Employ base conditions well

Steer clear of loops and illegitimate moves

Apply backtracking to try alternatives

It is the basis for more complex problems such as word searches, robot motion, AI movement, and game logic.

Learning Insights

You learn:

How recursive depth creates possible states

How to reverse decisions (backtracking)

Efficient traversal with constraints

Matrix traversal in code

This problem cements your mental model of recursion and introduces actual planning logic.

Interview Use

"Rat in a Maze" is a classic interview problem posed to test:

Recursive comprehension

Matrix/grid traversal

Backtracking with state memory

It is usual in corporations such as Amazon, Accenture, Infosys, and TCS to illustrate problem-solving and pattern-recognition skills.

The Rat in a Maze problem is one of the most popular backtracking exercises for training students and evaluating developers during interviews. It's closely connected with robotic locomotion, AI search strategies, grid traveling, and puzzle solving. Having learned this problem in C, C++, Java, and Python and knowing how to construct paths recursively with rollback mechanisms, you're getting yourself ready for numerous real-world problems involving structured exploration and constraint management.