Rat in a Maze
Given a NXN square matrix which contains 0 and 1 value. 1 indicates visible and 0 indicates invisible. Our goal is to find a path from top left corner to bottom right corner.
The "Rat in a Maze" problem is a classic example of a backtracking algorithm. The problem involves finding a path for a rat to navigate through a maze from its starting position to the destination. The maze is represented by a grid, where certain cells are blocked and cannot be traversed. The objective is to find a feasible path, if it exists, from the top-left corner to the bottom-right corner of the maze.
Problem Statement
Given a maze represented by a grid, where 1 denotes an open path and 0 denotes a blocked path, we need to find a solution that leads the rat from the starting position to the destination. The rat can only move in four directions: up, down, left, or right. We are required to implement a backtracking algorithm to solve this problem and print the resulting maze with the rat's path marked by 1s.
Pseudocode Algorithm
The backtracking algorithm for solving the Rat in a Maze problem can be summarized in the following steps:
1. Define a function to print the elements of the grid.
2. Implement a recursive function to solve the maze.
3. Check if the current position is a valid position within the maze.
4. If the destination is reached, check if it is an active element.
5. If the element has already been visited, return false.
6. If the current position is an active element, mark it as visited.
7. Recursively check the four possible directions (up, down, left, right).
8. If a solution is found, return true.
9. If no solution is found, deactivate the visited node status.
10. Return false.
11. Define a function to handle the maze-solving request.
12. Create a resultant grid to store the output.
13. Initialize the output grid with zeros.
14. If a solution exists, print the input maze and the output maze.
15. If no solution is possible, print a message indicating that.
16. Implement the main function.
17. Define the maze grid.
18. Call the maze-solving function.
Code Solution
// C program
// Rat in a Maze
#include <stdio.h>
#define SIZE 6
//Print grid elements
void print_maze(int grid[SIZE][SIZE])
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < SIZE; ++i)
{
for (j = 0; j < SIZE; ++j)
{
printf(" %d",grid[i][j]);
}
printf("\n");
}
printf("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
int solve_maze(int collection[SIZE][SIZE],int output[SIZE][SIZE],int r,int c)
{
if( r < 0 || r >= SIZE || c < 0 || c >= SIZE)
{
//When not valid position
return 0;
}
else if(r == SIZE-1 && c == SIZE-1 )
{
//When we get destination position
if(collection[r][c]==1)
{
//When destination are active element
output[r][c] = 1;
return 1;
}
}
if(output[r][c] == 1)
{
//When the element has been already been visited
return 0;
}
if(collection[r][c] == 1)
{
//Active visiting node
output[r][c] = 1;
//Test four possible direction
if(solve_maze(collection,output,r + 1, c) ||
solve_maze(collection,output,r , c + 1) ||
solve_maze(collection,output,r -1 , c) ||
solve_maze(collection,output,r , c - 1))
{
return 1;
}
// Deactivate visited node status
output[r][c] = 0;
}
return 0;
}
//Handles the request to find maze solution
void maze_test(int collection[SIZE][SIZE])
{
//Create resultant grid
int output[SIZE][SIZE];
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < SIZE; ++i)
{
for (j = 0; j < SIZE; ++j)
{
output[i][j] = 0;
}
}
if(solve_maze(collection,output,0,0))
{
//When result are exist
// Print input problem
printf("\n Input Maze \n");
print_maze(collection);
// Display output solution
printf("\n Output Maze \n");
print_maze(output);
}
else
{
//When no solution possible
printf("\n No Result \n");
}
}
int main()
{
int collection[SIZE][SIZE] =
{
{ 1, 0, 1, 1 ,1 ,1 },
{ 1, 1, 1, 1 ,0 ,1 },
{ 0, 1, 0, 0 ,1 ,1 },
{ 1, 0, 1, 1 ,1 ,0 },
{ 1, 0, 1, 1 ,0 ,1 },
{ 1, 0, 1, 1 ,1 ,1 }
};
maze_test(collection);
return 0;
}Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1
/*
Java program
Rat in a Maze
*/
class Maze
{
//Print grid elements
public void print_maze(int[][] grid, int rows, int cols)
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
System.out.print(" " + grid[i][j] );
}
System.out.print("\n");
}
System.out.print("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
public boolean solve_maze(int[][] collection, boolean[][] output, int rows, int cols, int r, int c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r][c] == 1)
{
//When destination are active element
output[r][c] = true;
return true;
}
}
if (output[r][c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r][c] == 1)
{
//Active visiting node
output[r][c] = true;
//Test four possible direction
if (solve_maze(collection, output, rows, cols, r + 1, c)
|| solve_maze(collection, output, rows, cols, r, c + 1)
|| solve_maze(collection, output, rows, cols, r - 1, c)
|| solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = false;
}
return false;
}
//Handles the request to find maze solution
public void maze_test(int[][] collection, int rows, int cols)
{
//Create resultant grid
boolean[][] output = new boolean[rows][cols];
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
output[i][j] = false;
}
}
if (solve_maze(collection, output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
System.out.print("\n Input Maze \n");
print_maze(collection,rows,cols);
// Display output solution
System.out.print(" Output Maze \n");
//result
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if( output[i][j] == false)
{
System.out.print(" 0" );
}
else
{
System.out.print(" 1" );
}
output[i][j] = false;
}
System.out.print("\n");
}
}
else
{
//When no solution possible
System.out.print("\n No Result \n");
}
}
public static void main(String[] args)
{
Maze obj = new Maze();
int[][] collection = {
{
1 , 0 , 1 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 0 , 0 , 1 , 1
} , {
1 , 0 , 1 , 1 , 1 , 0
} , {
1 , 0 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 1 , 1 , 1
}
};
int rows = collection.length;
int cols = collection[0].length;
obj.maze_test(collection, rows, cols);
}
}Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1//Include header file
#include <iostream>
#define SIZE 6
using namespace std;
/*
C++ program
Rat in a Maze
*/
class Maze
{
public:
//Print grid elements
void print_maze(int grid[SIZE][SIZE], int rows, int cols)
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
cout << " " << grid[i][j];
}
cout << "\n";
}
cout << "\n";
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
bool solve_maze(int collection[SIZE][SIZE], bool output[SIZE][SIZE], int rows, int cols, int r, int c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r][c] == 1)
{
//When destination are active element
output[r][c] = true;
return true;
}
}
if (output[r][c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r][c] == 1)
{
//Active visiting node
output[r][c] = true;
//Test four possible direction
if (this->solve_maze(collection, output, rows, cols, r + 1, c)
|| this->solve_maze(collection, output, rows, cols, r, c + 1)
|| this->solve_maze(collection, output, rows, cols, r - 1, c)
|| this->solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = false;
}
return false;
}
//Handles the request to find maze solution
void maze_test(int collection[SIZE][SIZE], int rows, int cols)
{
//Create resultant grid
bool output[SIZE][SIZE];
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
output[i][j] = false;
}
}
if (this->solve_maze(collection, output, rows, cols, 0, 0)==true)
{
//When result are exist
// Print input problem
cout << "\n Input Maze \n";
this->print_maze(collection, rows, cols);
// Display output solution
cout << " Output Maze \n";
//result
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (output[i][j] == false)
{
cout << " 0";
}
else
{
cout << " 1";
}
output[i][j] = false;
}
cout << "\n";
}
}
else
{
//When no solution possible
cout << "\n No Result \n";
}
}
};
int main()
{
Maze obj = Maze();
int collection[SIZE][SIZE] = {
{
1 , 0 , 1 , 1 , 1 , 1
} ,
{
1 , 1 , 1 , 1 , 0 , 1
} ,
{
0 , 1 , 0 , 0 , 1 , 1
} ,
{
1 , 0 , 1 , 1 , 1 , 0
} ,
{
1 , 0 , 1 , 1 , 0 , 1
} ,
{
1 , 0 , 1 , 1 , 1 , 1
}
};
int rows = sizeof(collection) / sizeof(collection[0]);
int cols = sizeof(collection[0]) / sizeof(collection[0][0]);
obj.maze_test(collection, rows, cols);
return 0;
}Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1//Include namespace system
using System;
/*
C# program
Rat in a Maze
*/
class Maze
{
//Print grid elements
public void print_maze(int[,] grid, int rows, int cols)
{
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
Console.Write(" " + grid[i,j]);
}
Console.Write("\n");
}
Console.Write("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
public Boolean solve_maze(int[,] collection, Boolean[,] output, int rows, int cols, int r, int c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r,c] == 1)
{
//When destination are active element
output[r,c] = true;
return true;
}
}
if (output[r,c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r,c] == 1)
{
//Active visiting node
output[r,c] = true;
//Test four possible direction
if (solve_maze(collection, output, rows, cols, r + 1, c) || solve_maze(collection, output, rows, cols, r, c + 1) || solve_maze(collection, output, rows, cols, r - 1, c) || solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r,c] = false;
}
return false;
}
//Handles the request to find maze solution
public void maze_test(int[,] collection, int rows, int cols)
{
//Create resultant grid
Boolean[,] output = new Boolean[rows,cols];
int i = 0;
int j = 0;
//Set initial values
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
output[i,j] = false;
}
}
if (solve_maze(collection, output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
Console.Write("\n Input Maze \n");
print_maze(collection, rows, cols);
// Display output solution
Console.Write(" Output Maze \n");
//result
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (output[i,j] == false)
{
Console.Write(" 0");
}
else
{
Console.Write(" 1");
}
output[i,j] = false;
}
Console.Write("\n");
}
}
else
{
//When no solution possible
Console.Write("\n No Result \n");
}
}
public static void Main(String[] args)
{
Maze obj = new Maze();
int[,] collection = {
{
1 , 0 , 1 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 0 , 0 , 1 , 1
} , {
1 , 0 , 1 , 1 , 1 , 0
} , {
1 , 0 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 1 , 1 , 1
}
};
int rows = collection.GetLength(0);
int cols = collection.GetLength(1);
obj.maze_test(collection, rows, cols);
}
}Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1<?php
/*
Php program
Rat in a Maze
*/
class Maze
{
//Print grid elements
public function print_maze( & $grid, $rows, $cols)
{
$i = 0;
$j = 0;
//Set initial values
while ($i < $rows)
{
$j = 0;
while ($j < $cols)
{
echo " ". $grid[$i][$j];
++$j;
}
echo "\n";
++$i;
}
echo "\n";
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
public function solve_maze( & $collection, & $output, $rows, $cols, $r, $c)
{
if ($r < 0 || $r >= $rows || $c < 0 || $c >= $cols)
{
//When not valid position
return false;
}
else if ($r == $rows - 1 && $c == $cols - 1)
{
//When we get destination position
if ($collection[$r][$c] == 1)
{
//When destination are active element
$output[$r][$c] = true;
return true;
}
}
if ($output[$r][$c] == true)
{
//When the element has been already been visited
return false;
}
if ($collection[$r][$c] == 1)
{
//Active visiting node
$output[$r][$c] = true;
//Test four possible direction
if ($this->solve_maze($collection, $output, $rows, $cols, $r + 1, $c) || $this->solve_maze($collection, $output, $rows, $cols, $r, $c + 1) || $this->solve_maze($collection, $output, $rows, $cols, $r - 1, $c) || $this->solve_maze($collection, $output, $rows, $cols, $r, $c - 1))
{
return true;
}
// Deactivate visited node status
$output[$r][$c] = false;
}
return false;
}
//Handles the request to find maze solution
public function maze_test( & $collection, $rows, $cols)
{
//Create resultant grid
$output = array_fill(0, $rows, array_fill(0, $cols, false));
$i = 0;
$j = 0;
if ($this->solve_maze($collection, $output, $rows, $cols, 0, 0))
{
//When result are exist
// Print input problem
echo "\n Input Maze \n";
$this->print_maze($collection, $rows, $cols);
// Display output solution
echo " Output Maze \n";
//result
$i = 0;
while ($i < $rows)
{
$j = 0;
while ($j < $cols)
{
if ($output[$i][$j] == false)
{
echo " 0";
}
else
{
echo " 1";
}
$output[$i][$j] = false;
++$j;
}
echo "\n";
++$i;
}
}
else
{
//When no solution possible
echo "\n No Result \n";
}
}
}
function main()
{
$obj = new Maze();
$collection = array(array(1, 0, 1, 1, 1, 1),
array(1, 1, 1, 1, 0, 1),
array(0, 1, 0, 0, 1, 1),
array(1, 0, 1, 1, 1, 0),
array(1, 0, 1, 1, 0, 1),
array(1, 0, 1, 1, 1, 1));
$rows = count($collection);
$cols = count($collection[0]);
$obj->maze_test($collection, $rows, $cols);
}
main();Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1/*
Node Js program
Rat in a Maze
*/
class Maze
{
//Print grid elements
print_maze(grid, rows, cols)
{
var i = 0;
var j = 0;
//Set initial values
while (i < rows)
{
j = 0;
while (j < cols)
{
process.stdout.write(" " + grid[i][j]);
++j;
}
process.stdout.write("\n");
++i;
}
process.stdout.write("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
solve_maze(collection, output, rows, cols, r, c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r][c] == 1)
{
//When destination are active element
output[r][c] = true;
return true;
}
}
if (output[r][c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r][c] == 1)
{
//Active visiting node
output[r][c] = true;
//Test four possible direction
if (this.solve_maze(collection, output, rows, cols, r + 1, c) || this.solve_maze(collection, output, rows, cols, r, c + 1) || this.solve_maze(collection, output, rows, cols, r - 1, c) || this.solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = false;
}
return false;
}
//Handles the request to find maze solution
maze_test(collection, rows, cols)
{
//Create resultant grid
var output = Array(rows).fill(false).map(() => new Array(cols).fill(false));
var i = 0;
var j = 0;
if (this.solve_maze(collection, output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
process.stdout.write("\n Input Maze \n");
this.print_maze(collection, rows, cols);
// Display output solution
process.stdout.write(" Output Maze \n");
//result
i = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output[i][j] == false)
{
process.stdout.write(" 0");
}
else
{
process.stdout.write(" 1");
}
output[i][j] = false;
++j;
}
process.stdout.write("\n");
++i;
}
}
else
{
//When no solution possible
process.stdout.write("\n No Result \n");
}
}
}
function main()
{
var obj = new Maze();
var collection = [
[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1]
];
var rows = collection.length;
var cols = collection[0].length;
obj.maze_test(collection, rows, cols);
}
main();Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1# Python 3 program
# Rat in a Maze
class Maze :
# Print grid elements
def print_maze(self, grid, rows, cols) :
i = 0
j = 0
# Set initial values
while (i < rows) :
j = 0
while (j < cols) :
print(" ", grid[i][j], end = "")
j += 1
print("\n", end = "")
i += 1
print("\n", end = "")
# Using backtracking find maze solution
# If solutions are not exist then it returns 0 (False).
def solve_maze(self, collection, output, rows, cols, r, c) :
if (r < 0 or r >= rows or c < 0 or c >= cols) :
# When not valid position
return False
elif(r == rows - 1 and c == cols - 1) :
# When we get destination position
if (collection[r][c] == 1) :
# When destination are active element
output[r][c] = True
return True
if (output[r][c] == True) :
# When the element has been already been visited
return False
if (collection[r][c] == 1) :
# Active visiting node
output[r][c] = True
# Test four possible direction
if (self.solve_maze(collection, output, rows, cols, r + 1, c) or self.solve_maze(collection, output, rows, cols, r, c + 1) or self.solve_maze(collection, output, rows, cols, r - 1, c) or self.solve_maze(collection, output, rows, cols, r, c - 1)) :
return True
# Deactivate visited node status
output[r][c] = False
return False
# Handles the request to find maze solution
def maze_test(self, collection, rows, cols) :
# Create resultant grid
output = [[False] * (cols) for _ in range(rows) ]
i = 0
j = 0
if (self.solve_maze(collection, output, rows, cols, 0, 0)) :
# When result are exist
# Print input problem
print("\n Input Maze \n", end = "")
self.print_maze(collection, rows, cols)
# Display output solution
print(" Output Maze \n", end = "")
# result
i = 0
while (i < rows) :
j = 0
while (j < cols) :
if (output[i][j] == False) :
print(" 0", end = "")
else :
print(" 1", end = "")
output[i][j] = False
j += 1
print("\n", end = "")
i += 1
else :
# When no solution possible
print("\n No Result \n", end = "")
def main() :
obj = Maze()
collection = [
[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1]
]
rows = len(collection)
cols = len(collection[0])
obj.maze_test(collection, rows, cols)
if __name__ == "__main__": main()Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1# Ruby program
# Rat in a Maze
class Maze
# Print grid elements
def print_maze(grid, rows, cols)
i = 0
j = 0
# Set initial values
while (i < rows)
j = 0
while (j < cols)
print(" ", grid[i][j])
j += 1
end
print("\n")
i += 1
end
print("\n")
end
# Using backtracking find maze solution
# If solutions are not exist then it returns 0 (False).
def solve_maze(collection, output, rows, cols, r, c)
if (r < 0 || r >= rows || c < 0 || c >= cols)
# When not valid position
return false
elsif(r == rows - 1 && c == cols - 1)
# When we get destination position
if (collection[r][c] == 1)
# When destination are active element
output[r][c] = true
return true
end
end
if (output[r][c] == true)
# When the element has been already been visited
return false
end
if (collection[r][c] == 1)
# Active visiting node
output[r][c] = true
# Test four possible direction
if (self.solve_maze(collection, output, rows, cols, r + 1, c) || self.solve_maze(collection, output, rows, cols, r, c + 1) || self.solve_maze(collection, output, rows, cols, r - 1, c) || self.solve_maze(collection, output, rows, cols, r, c - 1))
return true
end
# Deactivate visited node status
output[r][c] = false
end
return false
end
# Handles the request to find maze solution
def maze_test(collection, rows, cols)
# Create resultant grid
output = Array.new(rows) {Array.new(cols) {false}}
i = 0
j = 0
if (self.solve_maze(collection, output, rows, cols, 0, 0))
# When result are exist
# Print input problem
print("\n Input Maze \n")
self.print_maze(collection, rows, cols)
# Display output solution
print(" Output Maze \n")
# result
i = 0
while (i < rows)
j = 0
while (j < cols)
if (output[i][j] == false)
print(" 0")
else
print(" 1")
end
output[i][j] = false
j += 1
end
print("\n")
i += 1
end
else
# When no solution possible
print("\n No Result \n")
end
end
end
def main()
obj = Maze.new()
collection = [
[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1]
]
rows = collection.length
cols = collection[0].length
obj.maze_test(collection, rows, cols)
end
main()Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1
/*
Scala program
Rat in a Maze
*/
class Maze
{
//Print grid elements
def print_maze(grid: Array[Array[Int]],
rows: Int, cols: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
//Set initial values
while (i < rows)
{
j = 0;
while (j < cols)
{
print(" " + grid(i)(j));
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
def solve_maze(collection: Array[Array[Int]],
output: Array[Array[Boolean]],
rows: Int, cols: Int, r: Int, c: Int): Boolean = {
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection(r)(c) == 1)
{
//When destination are active element
output(r)(c) = true;
return true;
}
}
if (output(r)(c) == true)
{
//When the element has been already been visited
return false;
}
if (collection(r)(c) == 1)
{
//Active visiting node
output(r)(c) = true;
//Test four possible direction
if (solve_maze(collection, output, rows, cols, r + 1, c)
|| solve_maze(collection, output, rows, cols, r, c + 1)
|| solve_maze(collection, output, rows, cols, r - 1, c)
|| solve_maze(collection, output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output(r)(c) = false;
}
return false;
}
//Handles the request to find maze solution
def maze_test(collection: Array[Array[Int]], rows: Int, cols: Int): Unit = {
//Create resultant grid
var output: Array[Array[Boolean]] = Array.fill[Boolean](rows, cols)(false);
var i: Int = 0;
var j: Int = 0;
if (solve_maze(collection, output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
print("\n Input Maze \n");
print_maze(collection, rows, cols);
// Display output solution
print(" Output Maze \n");
//result
i = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output(i)(j) == false)
{
print(" 0");
}
else
{
print(" 1");
}
output(i)(j) = false;
j += 1;
}
print("\n");
i += 1;
}
}
else
{
//When no solution possible
print("\n No Result \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Maze = new Maze();
var collection: Array[Array[Int]] = Array(Array(1, 0, 1, 1, 1, 1), Array(1, 1, 1, 1, 0, 1), Array(0, 1, 0, 0, 1, 1), Array(1, 0, 1, 1, 1, 0), Array(1, 0, 1, 1, 0, 1), Array(1, 0, 1, 1, 1, 1));
var rows: Int = collection.length;
var cols: Int = collection(0).length;
obj.maze_test(collection, rows, cols);
}
}Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1/*
Swift 4 program
Rat in a Maze
*/
class Maze
{
//Print grid elements
func print_maze(_ grid: [[Int]], _ rows: Int, _ cols: Int)
{
var i: Int = 0;
var j: Int = 0;
//Set initial values
while (i < rows)
{
j = 0;
while (j < cols)
{
print(" ", grid[i][j], terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
func solve_maze(_ collection: [[Int]], _ output: inout[[Bool]], _ rows: Int, _ cols: Int, _ r: Int, _ c: Int) -> Bool
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return false;
}
else if (r == rows - 1 && c == cols - 1)
{
//When we get destination position
if (collection[r][c] == 1)
{
//When destination are active element
output[r][c] = true;
return true;
}
}
if (output[r][c] == true)
{
//When the element has been already been visited
return false;
}
if (collection[r][c] == 1)
{
//Active visiting node
output[r][c] = true;
//Test four possible direction
if (self.solve_maze(collection, &output, rows, cols, r + 1, c)
|| self.solve_maze(collection, &output, rows, cols, r, c + 1)
|| self.solve_maze(collection, &output, rows, cols, r - 1, c)
|| self.solve_maze(collection, &output, rows, cols, r, c - 1))
{
return true;
}
// Deactivate visited node status
output[r][c] = false;
}
return false;
}
//Handles the request to find maze solution
func maze_test(_ collection: [[Int]], _ rows: Int, _ cols: Int)
{
//Create resultant grid
var output: [[Bool]] = Array(repeating: Array(repeating: false, count: cols), count: rows);
var i: Int = 0;
var j: Int = 0;
if (self.solve_maze(collection, &output, rows, cols, 0, 0))
{
//When result are exist
// Print input problem
print("\n Input Maze \n", terminator: "");
self.print_maze(collection, rows, cols);
// Display output solution
print(" Output Maze \n", terminator: "");
//result
i = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output[i][j] == false)
{
print(" 0", terminator: "");
}
else
{
print(" 1", terminator: "");
}
output[i][j] = false;
j += 1;
}
print("\n", terminator: "");
i += 1;
}
}
else
{
//When no solution possible
print("\n No Result \n", terminator: "");
}
}
}
func main()
{
let obj: Maze = Maze();
let collection: [[Int]] = [[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 0, 0, 1, 1],
[1, 0, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1]];
let rows: Int = collection.count;
let cols: Int = collection[0].count;
obj.maze_test(collection, rows, cols);
}
main();Output
Input Maze
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
Output Maze
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1Explanation
The given C program implements the Rat in a Maze problem using a backtracking algorithm. The maze is represented by a 2D grid, where 1 represents an open path, and 0 represents a blocked path. The program starts by defining the grid and calling the maze-solving function. Inside the maze-solving function, a resultant grid is created to store the output. The grid is initialized with zeros. The solve_maze function is then called recursively to find a feasible path from the starting position (0, 0) to the destination position (SIZE-1, SIZE-1).
The solve_maze function checks if the current position is within the valid bounds of the maze. If it is outside the bounds or if the current position is already visited, it returns false. If the destination is reached, the function checks if it is an active element. If it is, the output grid is updated with a 1 to mark the path, and the function returns true. If the current position is an active element, it is marked as visited, and the function recursively checks the four possible directions (up, down, left, right). If a solution is found in any of the directions, the function returns true. If no solution is found, the visited node status is deactivated, and the function returns false.
The maze_test function handles the request to find a maze solution. It creates the resultant grid, initializes it with zeros, and calls the solve_maze function. If a solution exists, it prints the input maze and the output maze using the print_maze function. If no solution is possible, it prints a message indicating so.
The main function in the program initializes the maze grid and calls the maze_test function. The input maze and the resulting maze are printed to the console.
Result Explanation
The input maze is a 6x6 grid, where the elements are represented by 1s and 0s. The 1s denote open paths, and the 0s denote blocked paths. The program successfully finds a path from the starting position (0, 0) to the destination position (5, 5) and marks the path with 1s in the output maze. The input maze and the output maze are printed to the console, showing the path taken by the rat.
The input maze:
1 0 1 1 1 1
1 1 1 1 0 1
0 1 0 0 1 1
1 0 1 1 1 0
1 0 1 1 0 1
1 0 1 1 1 1
The output maze with the rat's path marked:
1 0 0 1 1 1
1 1 1 1 0 1
0 0 0 0 1 1
0 0 0 1 1 0
0 0 0 1 0 0
0 0 0 1 1 1
Time Complexity of the Code
The time complexity of the backtracking algorithm used in this program is determined by the size of the maze, denoted by the constant SIZE. Since the algorithm explores all possible paths until it finds a feasible solution, the time complexity can be considered exponential.
The worst-case time complexity can be estimated as O(3^N), where N is the number of cells in the maze. This is because, at each cell, the algorithm has three possible directions to explore (excluding the direction it came from) until it either reaches the destination or exhausts all possibilities.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment