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

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.

New Comment