Posted on by Kalkicode
Code Backtracking

# Find all solutions in a maze

"Find all solutions in a maze" means to identify and trace every possible path or route that leads to the exit of a maze. A maze is a complex puzzle or labyrinth designed to be challenging and confusing to navigate, often with dead ends and multiple possible paths.

To solve a maze, one must explore different routes and make choices at each intersection or decision point until they reach the end. "Finding all solutions" means discovering every possible combination of paths that can be taken from the starting point to the exit point, without missing any possible routes or backtracking unnecessarily.

This task can be challenging depending on the size and complexity of the maze, and may require careful planning, mapping, and tracking of one's progress to avoid getting lost or retracing one's steps. Algorithms and techniques such as depth-first search, breadth-first search, and A* search can be used to systematically explore a maze and find all possible solutions.

In this article, we will explore the problem of finding all solutions in a maze using a C program. The maze represents a grid, and our goal is to find all possible paths from the starting position to the destination position in the maze. Each cell in the maze can be either blocked or unblocked, and we can only move in four directions: up, down, left, and right.

Problem Statement:

The problem is to find all possible paths from the starting position to the destination position in a given maze. We need to consider all valid paths and print them as the output. The maze is represented as a 2D array, where each element can be either 0 (blocked) or 1 (unblocked).

Pseudocode Algorithm:

1. Define a function print_maze to print the maze grid.

2. Define a recursive function all_maze_solution to find all solutions in the maze.

3. Inside the all_maze_solution function:

• a. Check if the current position is out of bounds or if it has already been visited. If so, return.
• b. If the current position is the destination, check if it is an active element (unblocked). If so, print the maze and return.
• c. If the current position is an active element, mark it as visited and recursively call all_maze_solution for all four possible directions: up, down, left, and right.
• d. After exploring all possible paths from the current position, mark it as unvisited.

4. Define a function maze_test to initialize the output grid and call the all_maze_solution function.

5. In the main function, define the maze grid and call the maze_test function.

## Program Solution

// C program
// Find all solutions in a maze
#include <stdio.h>
#define SIZE 6

void print_maze(int maze[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", maze[i][j]);
}
printf("\n");
}
printf("\n");
}
void all_maze_solution(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;
}
else if (output[r][c] == 1)
{
return;
}
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;
//result
printf("\n  Output Maze \n");
print_maze(output);
output[r][c] = 0;
}
}
else if (collection[r][c] == 1)
{
output[r][c] = 1;
//Test four possible direction
all_maze_solution(collection, output, r + 1, c);
all_maze_solution(collection, output, r, c + 1);
all_maze_solution(collection, output, r - 1, c);
all_maze_solution(collection, output, r, c - 1);
output[r][c] = 0;
}
}
void maze_test(int collection[SIZE][SIZE])
{
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;
}
}
all_maze_solution(collection, output, 0, 0);
}
int main()
{
int collection[SIZE][SIZE] = {
{
1 , 0 , 0 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 1 , 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

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  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

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  1  1  0  0
0  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  1  1  1  0
0  0  1  0  0  0
0  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  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1
/*
Java program
Find all solutions 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");
}
//Print output elements
public void output_maze(boolean[][] output, int rows, int cols)
{
int i = 0;
int j = 0;
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");
}
}
System.out.print("\n");
}
}
//Using backtracking find all maze solution
public void all_maze_solution(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;
}
else if (output[r][c] == true)
{
return;
}
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;
//result
System.out.print("\n Output Maze \n");
output_maze(output, rows, cols);
output[r][c] = false;
return;
}
}
else if (collection[r][c] == 1)
{
output[r][c] = true;
//Test four possible direction
all_maze_solution(collection, output, rows, cols, r + 1, c);
all_maze_solution(collection, output, rows, cols, r, c + 1);
all_maze_solution(collection, output, rows, cols, r - 1, c);
all_maze_solution(collection, output, rows, cols, r, c - 1);
output[r][c] = 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;
}
}
System.out.print("\n  Input Maze \n");
print_maze(collection, rows, cols);
all_maze_solution(collection, output, rows, cols, 0, 0);
}
public static void main(String[] args)
{
Maze obj = new Maze();
int[][] collection = {
{
1 , 0 , 0 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 1 , 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  0  1  1  1
1  1  1  1  0  1
0  1  1  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  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  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

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  1  1  0  0
0  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  1  1  1  0
0  0  1  0  0  0
0  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  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1
#include <iostream>
#define R 6
#define C 6
using namespace std;

/*
C++ program
Find all solutions in a maze
*/

class Maze
{
public:
//Print grid elements
void print_maze(int grid[R][C], 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";
}
//Print output elements
void output_maze(bool output[R][C], int rows, int cols)
{
int i = 0;
int j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (output[i][j] == false)
{
cout << "  0";
}
else
{
cout << "  1";
}
}
cout << "\n";
}
}
//Using backtracking find all maze solution
void all_maze_solution(int collection[R][C], bool output[R][C], int rows, int cols, int r, int c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return;
}
else if (output[r][c] == true)
{
return;
}
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;
//result
cout << "\n Output Maze \n";
this->output_maze(output, rows, cols);
output[r][c] = false;
return;
}
}
else if (collection[r][c] == 1)
{
output[r][c] = true;
//Test four possible direction
this->all_maze_solution(collection, output, rows, cols, r + 1, c);
this->all_maze_solution(collection, output, rows, cols, r, c + 1);
this->all_maze_solution(collection, output, rows, cols, r - 1, c);
this->all_maze_solution(collection, output, rows, cols, r, c - 1);
output[r][c] = false;
}
}
//Handles the request to find maze solution
void maze_test(int collection[R][C], int rows, int cols)
{
//Create resultant grid
bool output[R][C] ;
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;
}
}
cout << "\n  Input Maze \n";
this->print_maze(collection, rows, cols);
this->all_maze_solution(collection, output, rows, cols, 0, 0);
}
};
int main()
{
Maze obj = Maze();
int collection[R][C] = {
{
1 , 0 , 0 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 1 , 0 , 1 , 1
} , {
1 , 0 , 1 , 1 , 1 , 0
} , {
1 , 0 , 1 , 1 , 0 , 1
} , {
1 , 0 , 1 , 1 , 1 , 1
}
};
int rows = R;
int cols = C;
obj.maze_test(collection, rows, cols);
return 0;
}

#### Output

Input Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  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  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  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

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  1  1  0  0
0  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  1  1  1  0
0  0  1  0  0  0
0  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  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1
//Include namespace system
using System;
/*
C# program
Find all solutions 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");
}
//Print output elements
public void output_maze(Boolean[,] output, int rows, int cols)
{
int i = 0;
int j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (output[i,j] == false)
{
Console.Write("  0");
}
else
{
Console.Write("  1");
}
}
Console.Write("\n");
}
}
//Using backtracking find all maze solution
public void all_maze_solution(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;
}
else if (output[r,c] == true)
{
return;
}
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;
//result
Console.Write("\n Output Maze \n");
output_maze(output, rows, cols);
output[r,c] = false;
return;
}
}
else if (collection[r,c] == 1)
{
output[r,c] = true;
//Test four possible direction
all_maze_solution(collection, output, rows, cols, r + 1, c);
all_maze_solution(collection, output, rows, cols, r, c + 1);
all_maze_solution(collection, output, rows, cols, r - 1, c);
all_maze_solution(collection, output, rows, cols, r, c - 1);
output[r,c] = 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;
}
}
Console.Write("\n  Input Maze \n");
print_maze(collection, rows, cols);
all_maze_solution(collection, output, rows, cols, 0, 0);
}
public static void Main(String[] args)
{
Maze obj = new Maze();
int[,] collection = {
{
1 , 0 , 0 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 0 , 1
} , {
0 , 1 , 1 , 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  0  1  1  1
1  1  1  1  0  1
0  1  1  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  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  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

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  1  1  0  0
0  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  1  1  1  0
0  0  1  0  0  0
0  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  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1
<?php
/*
Php program
Find all solutions 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";
}
//Print output elements
public	function output_maze( & \$output, \$rows, \$cols)
{
\$i = 0;
\$j = 0;
while (\$i < \$rows)
{
\$j = 0;
while (\$j < \$cols)
{
if (\$output[\$i][\$j] == false)
{
echo "  0";
}
else
{
echo "  1";
}++\$j;
}
echo "\n";
++\$i;
}
}
//Using backtracking find all maze solution
public	function all_maze_solution( & \$collection, & \$output, \$rows, \$cols, \$r, \$c)
{
if (\$r < 0 || \$r >= \$rows || \$c < 0 || \$c >= \$cols)
{
//When not valid position
return;
}
else if (\$output[\$r][\$c] == true)
{
return;
}
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;
//result
echo "\n Output Maze \n";
\$this->output_maze(\$output, \$rows, \$cols);
\$output[\$r][\$c] = false;
return;
}
}
else if (\$collection[\$r][\$c] == 1)
{
\$output[\$r][\$c] = true;
//Test four possible direction
\$this->all_maze_solution(\$collection, \$output, \$rows, \$cols, \$r + 1, \$c);
\$this->all_maze_solution(\$collection, \$output, \$rows, \$cols, \$r, \$c + 1);
\$this->all_maze_solution(\$collection, \$output, \$rows, \$cols, \$r - 1, \$c);
\$this->all_maze_solution(\$collection, \$output, \$rows, \$cols, \$r, \$c - 1);
\$output[\$r][\$c] = 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));
echo "\n  Input Maze \n";
\$this->print_maze(\$collection, \$rows, \$cols);
\$this->all_maze_solution(\$collection, \$output, \$rows, \$cols, 0, 0);
}
}

function main()
{
\$obj = new Maze();
\$collection = array(
array(1, 0, 0, 1, 1, 1),
array(1, 1, 1, 1, 0, 1),
array(0, 1, 1, 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  0  1  1  1
1  1  1  1  0  1
0  1  1  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  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  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

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  1  1  0  0
0  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  1  1  1  0
0  0  1  0  0  0
0  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  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1
/*
Node Js program
Find all solutions 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");
}
//Print output elements
output_maze(output, rows, cols)
{
var i = 0;
var j = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output[i][j] == false)
{
process.stdout.write("  0");
}
else
{
process.stdout.write("  1");
}
++j;
}
process.stdout.write("\n");
++i;
}
}
//Using backtracking find all maze solution
all_maze_solution(collection, output, rows, cols, r, c)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return;
}
else if (output[r][c] == true)
{
return;
}
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;
//result
process.stdout.write("\n Output Maze \n");
this.output_maze(output, rows, cols);
output[r][c] = false;
return;
}
}
else if (collection[r][c] == 1)
{
output[r][c] = true;
//Test four possible direction
this.all_maze_solution(collection, output, rows, cols, r + 1, c);
this.all_maze_solution(collection, output, rows, cols, r, c + 1);
this.all_maze_solution(collection, output, rows, cols, r - 1, c);
this.all_maze_solution(collection, output, rows, cols, r, c - 1);
output[r][c] = 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));
process.stdout.write("\n  Input Maze \n");
this.print_maze(collection, rows, cols);
this.all_maze_solution(collection, output, rows, cols, 0, 0);
}
}

function main()
{
var obj = new Maze();
var collection = [
[1, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 1, 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  0  1  1  1
1  1  1  1  0  1
0  1  1  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  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  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

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  1  1  0  0
0  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  1  1  1  0
0  0  1  0  0  0
0  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  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1
#   Python 3 program
#   Find all solutions 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 = "")

# Print output elements
def output_maze(self, output, rows, cols) :
i = 0
j = 0
while (i < rows) :
j = 0
while (j < cols) :
if (output[i][j] == False) :
print("   0", end = "")
else :
print("   1", end = "")

j += 1

print("\n", end = "")
i += 1

# Using backtracking find all maze solution
def all_maze_solution(self, collection, output, rows, cols, r, c) :
if (r < 0 or r >= rows or c < 0 or c >= cols) :
# When not valid position
return

elif(output[r][c] == True) :
return

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
# result
print("\n Output Maze \n", end = "")
self.output_maze(output, rows, cols)
output[r][c] = False
return

elif(collection[r][c] == 1) :
output[r][c] = True
# Test four possible direction
self.all_maze_solution(collection, output, rows, cols, r + 1, c)
self.all_maze_solution(collection, output, rows, cols, r, c + 1)
self.all_maze_solution(collection, output, rows, cols, r - 1, c)
self.all_maze_solution(collection, output, rows, cols, r, c - 1)
output[r][c] = 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) ]
print("\n  Input Maze \n", end = "")
self.print_maze(collection, rows, cols)
self.all_maze_solution(collection, output, rows, cols, 0, 0)

def main() :
obj = Maze()
collection = [
[1, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 1, 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   0   1   1   1
1   1   1   1   0   1
0   1   1   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   0   0   0
1   1   0   0   0   0
0   1   1   0   0   0
0   0   1   0   0   0
0   0   1   0   0   0
0   0   1   1   1   1

Output Maze
1   0   0   0   0   0
1   1   0   0   0   0
0   1   1   0   0   0
0   0   1   0   0   0
0   0   1   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   0   0   0   0
0   1   1   0   0   0
0   0   1   1   0   0
0   0   0   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   0   0   0   0
0   1   1   0   0   0
0   0   1   1   0   0
0   0   1   1   0   0
0   0   1   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   1   1   0   1   1
0   0   0   1   1   0
0   0   0   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   1   1   0   1   1
0   0   0   1   1   0
0   0   1   1   0   0
0   0   1   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   1   1   0   1   1
0   0   1   1   1   0
0   0   1   0   0   0
0   0   1   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   1   1   0   1   1
0   0   1   1   1   0
0   0   1   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   1   0   0   0
0   0   1   0   0   0
0   0   1   0   0   0
0   0   1   0   0   0
0   0   1   1   1   1

Output Maze
1   0   0   0   0   0
1   1   1   0   0   0
0   0   1   0   0   0
0   0   1   0   0   0
0   0   1   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   1   0   0   0
0   0   1   0   0   0
0   0   1   1   0   0
0   0   0   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   1   0   0   0
0   0   1   0   0   0
0   0   1   1   0   0
0   0   1   1   0   0
0   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

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   1   1   0   0
0   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   1   1   1   0
0   0   1   0   0   0
0   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   1   1   1   0
0   0   1   1   0   0
0   0   0   1   1   1
#   Ruby program
#   Find all solutions 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

# Print output elements
def output_maze(output, rows, cols)
i = 0
j = 0
while (i < rows)
j = 0
while (j < cols)
if (output[i][j] == false)
print("  0")
else
print("  1")
end

j += 1
end

print("\n")
i += 1
end

end

# Using backtracking find all maze solution
def all_maze_solution(collection, output, rows, cols, r, c)
if (r < 0 || r >= rows || c < 0 || c >= cols)
# When not valid position
return
elsif(output[r][c] == true)
return
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
# result
print("\n Output Maze \n")
self.output_maze(output, rows, cols)
output[r][c] = false
return
end

elsif(collection[r][c] == 1)
output[r][c] = true
# Test four possible direction
self.all_maze_solution(collection, output, rows, cols, r + 1, c)
self.all_maze_solution(collection, output, rows, cols, r, c + 1)
self.all_maze_solution(collection, output, rows, cols, r - 1, c)
self.all_maze_solution(collection, output, rows, cols, r, c - 1)
output[r][c] = false
end

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}}
print("\n  Input Maze \n")
self.print_maze(collection, rows, cols)
self.all_maze_solution(collection, output, rows, cols, 0, 0)
end

end

def main()
obj = Maze.new()
collection = [
[1, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 1, 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  0  1  1  1
1  1  1  1  0  1
0  1  1  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  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  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

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  1  1  0  0
0  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  1  1  1  0
0  0  1  0  0  0
0  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  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1
/*
Scala program
Find all solutions 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");
}
//Print output elements
def output_maze(output: Array[Array[Boolean]], rows: Int, cols: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output(i)(j) == false)
{
print("  0");
}
else
{
print("  1");
}
j += 1;
}
print("\n");
i += 1;
}
}
//Using backtracking find all maze solution
def all_maze_solution(collection: Array[Array[Int]], output: Array[Array[Boolean]], rows: Int, cols: Int, r: Int, c: Int): Unit = {
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return;
}
else if (output(r)(c) == true)
{
return;
}
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;
//result
print("\n Output Maze \n");
output_maze(output, rows, cols);
output(r)(c) = false;
return;
}
}
else if (collection(r)(c) == 1)
{
output(r)(c) = true;
//Test four possible direction
all_maze_solution(collection, output, rows, cols, r + 1, c);
all_maze_solution(collection, output, rows, cols, r, c + 1);
all_maze_solution(collection, output, rows, cols, r - 1, c);
all_maze_solution(collection, output, rows, cols, r, c - 1);
output(r)(c) = 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);
print("\n  Input Maze \n");
print_maze(collection, rows, cols);
all_maze_solution(collection, output, rows, cols, 0, 0);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Maze = new Maze();
var collection: Array[Array[Int]] = Array(Array(1, 0, 0, 1, 1, 1), Array(1, 1, 1, 1, 0, 1), Array(0, 1, 1, 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  0  1  1  1
1  1  1  1  0  1
0  1  1  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  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  0  0  0  0
0  1  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  0  1  1  0
0  0  1  1  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  1  1  1
1  1  1  1  0  1
0  1  1  0  1  1
0  0  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  0  1  0  0
0  0  0  1  1  1

Output Maze
1  0  0  0  0  0
1  1  1  0  0  0
0  0  1  0  0  0
0  0  1  1  0  0
0  0  1  1  0  0
0  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

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  1  1  0  0
0  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  1  1  1  0
0  0  1  0  0  0
0  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  1  1  1  0
0  0  1  1  0  0
0  0  0  1  1  1
/*
Swift 4 program
Find all solutions 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: "");
}
//Print output elements
func output_maze(_ output: [[Bool]], _ rows: Int, _ cols: Int)
{
var i: Int = 0;
var j: Int = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (output[i][j] == false)
{
print("   0", terminator: "");
}
else
{
print("   1", terminator: "");
}
j += 1;
}
print("\n", terminator: "");
i += 1;
}
}
//Using backtracking find all maze solution
func all_maze_solution(_ collection: [[Int]], _ output: inout[[Bool]], _ rows: Int, _ cols: Int, _ r: Int, _ c: Int)
{
if (r < 0 || r >= rows || c < 0 || c >= cols)
{
//When not valid position
return;
}
else if (output[r][c] == true)
{
return;
}
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;
//result
print("\n Output Maze \n", terminator: "");
self.output_maze(output, rows, cols);
output[r][c] = false;
return;
}
}
else if (collection[r][c] == 1)
{
output[r][c] = true;
//Test four possible direction
self.all_maze_solution(collection, &output, rows, cols, r + 1, c);
self.all_maze_solution(collection, &output, rows, cols, r, c + 1);
self.all_maze_solution(collection, &output, rows, cols, r - 1, c);
self.all_maze_solution(collection, &output, rows, cols, r, c - 1);
output[r][c] = 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);
print("\n  Input Maze \n", terminator: "");
self.print_maze(collection, rows, cols);
self.all_maze_solution(collection, &output, rows, cols, 0, 0);
}
}
func main()
{
let obj: Maze = Maze();
let collection: [[Int]] = [[1, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 1, 1, 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   0   1   1   1
1   1   1   1   0   1
0   1   1   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   0   0   0
1   1   0   0   0   0
0   1   1   0   0   0
0   0   1   0   0   0
0   0   1   0   0   0
0   0   1   1   1   1

Output Maze
1   0   0   0   0   0
1   1   0   0   0   0
0   1   1   0   0   0
0   0   1   0   0   0
0   0   1   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   0   0   0   0
0   1   1   0   0   0
0   0   1   1   0   0
0   0   0   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   0   0   0   0
0   1   1   0   0   0
0   0   1   1   0   0
0   0   1   1   0   0
0   0   1   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   1   1   0   1   1
0   0   0   1   1   0
0   0   0   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   1   1   0   1   1
0   0   0   1   1   0
0   0   1   1   0   0
0   0   1   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   1   1   0   1   1
0   0   1   1   1   0
0   0   1   0   0   0
0   0   1   1   1   1

Output Maze
1   0   0   1   1   1
1   1   1   1   0   1
0   1   1   0   1   1
0   0   1   1   1   0
0   0   1   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   1   0   0   0
0   0   1   0   0   0
0   0   1   0   0   0
0   0   1   0   0   0
0   0   1   1   1   1

Output Maze
1   0   0   0   0   0
1   1   1   0   0   0
0   0   1   0   0   0
0   0   1   0   0   0
0   0   1   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   1   0   0   0
0   0   1   0   0   0
0   0   1   1   0   0
0   0   0   1   0   0
0   0   0   1   1   1

Output Maze
1   0   0   0   0   0
1   1   1   0   0   0
0   0   1   0   0   0
0   0   1   1   0   0
0   0   1   1   0   0
0   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

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   1   1   0   0
0   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   1   1   1   0
0   0   1   0   0   0
0   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   1   1   1   0
0   0   1   1   0   0
0   0   0   1   1   1

Time Complexity:

The time complexity of the algorithm depends on the size of the maze grid. Let N be the size of the grid. In the worst case, the algorithm explores all possible paths in the maze. Each cell can be visited at most once. Therefore, the time complexity is O(N^2) because we have to iterate over all cells in the maze.

Resultant Output Explanation:

The output shows all the possible solutions in the maze grid. Each solution represents a path from the starting position (top-left) to the destination position (bottom-right). The output is printed as a series of 2D grids, where 1 represents the path and 0 represents the blocked cells.

For example, the first output grid represents one possible solution where all unblocked cells on the path from the start to the destination are marked as 1, and the blocked cells are marked as 0.

The subsequent output grids represent different solutions found by the algorithm. Each solution explores a unique path through the maze.

## Comment

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.

Categories
Relative Post