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.
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 header file
#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
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