Skip to main content

Rat in a Maze

Given a NXN square matrix which contains 0 and 1 value. 1 indicates visible and 0 indicates invisible. Our goal is to find a path from top left corner to bottom right corner.

Here given code implementation process.

// C program  
// Rat in a Maze

#include <stdio.h>

#define SIZE 6


//Print grid elements
void print_maze(int grid[SIZE][SIZE])
{
    int i  = 0;
    int j  = 0;

    //Set initial values
    for (i = 0; i < SIZE; ++i)
    {
        for (j = 0; j < SIZE; ++j)
        {
            printf("  %d",grid[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

//Using backtracking find maze solution
//If solutions are not exist then it returns 0 (False).
int solve_maze(int collection[SIZE][SIZE],int output[SIZE][SIZE],int r,int c)
{

    if( r < 0 || r >= SIZE || c < 0 || c >= SIZE)
    {
        //When not valid position
        return 0;
    }
    else if(r == SIZE-1 && c == SIZE-1 )
    {
        //When we get destination position

        if(collection[r][c]==1)
        {
            //When destination are active element
            output[r][c] = 1;
        
            return 1;
        }
    }

    if(output[r][c] == 1)
    {
        //When the element has been already been visited
        return 0;
    }
    if(collection[r][c] == 1)
    {

        //Active visiting node
        output[r][c] = 1;

        //Test four possible direction
        if(solve_maze(collection,output,r + 1, c)   ||
           solve_maze(collection,output,r  , c + 1) ||
           solve_maze(collection,output,r -1 , c) ||
           solve_maze(collection,output,r , c - 1))
        {
            return 1;
        }
        // Deactivate visited node status
        output[r][c] = 0;
    }
  

    return 0;


}
//Handles the request to find maze solution
void maze_test(int collection[SIZE][SIZE])
{
    //Create resultant grid
    int output[SIZE][SIZE];

    int i  = 0;
    int j  = 0;

    //Set initial values
    for (i = 0; i < SIZE; ++i)
    {
        for (j = 0; j < SIZE; ++j)
        {
            output[i][j] = 0;
        }
    }

    if(solve_maze(collection,output,0,0))
    {
        //When result are exist
        
        // Print input problem
        printf("\n  Input Maze \n");
        print_maze(collection);

        // Display output solution
        printf("\n  Output Maze \n");
        print_maze(output);

    }
    else
    {
        //When no solution possible
        printf("\n No Result \n");
    }



}

int main()
{

    int collection[SIZE][SIZE] = 
    { 
        { 1, 0, 1, 1 ,1 ,1 }, 
        { 1, 1, 1, 1 ,0 ,1 }, 
        { 0, 1, 0, 0 ,1 ,1 }, 
        { 1, 0, 1, 1 ,1 ,0 },
        { 1, 0, 1, 1 ,0 ,1 },
        { 1, 0, 1, 1 ,1 ,1 }
    }; 
    
    maze_test(collection);       
    return 0;
}

Output

  Input Maze
  1  0  1  1  1  1
  1  1  1  1  0  1
  0  1  0  0  1  1
  1  0  1  1  1  0
  1  0  1  1  0  1
  1  0  1  1  1  1


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

/*
  Java program 
  Rat in a Maze
*/
class Maze
{
    //Print grid elements
    public void print_maze(int[][] grid, int rows, int cols)
    {
        int i = 0;
        int j = 0;
        //Set initial values
        for (i = 0; i < rows; ++i)
        {
            for (j = 0; j < cols; ++j)
            {
                System.out.print("  " + grid[i][j] );
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    //Using backtracking find maze solution
    //If solutions are not exist then it returns 0 (False).
    public boolean solve_maze(int[][] collection, boolean[][] output, int rows, int cols, int r, int c)
    {
        if (r < 0 || r >= rows || c < 0 || c >= cols)
        {
            //When not valid position
            return false;
        }
        else if (r == rows - 1 && c == cols - 1)
        {
            //When we get destination position
            if (collection[r][c] == 1)
            {
                //When destination are active element
                output[r][c] = true;
                return true;
            }
        }
        if (output[r][c] == true)
        {
            //When the element has been already been visited
            return false;
        }
        if (collection[r][c] == 1)
        {
            //Active visiting node
            output[r][c] = true;
            //Test four possible direction
            if (solve_maze(collection, output, rows, cols, r + 1, c) 
                || solve_maze(collection, output, rows, cols, r, c + 1) 
                || solve_maze(collection, output, rows, cols, r - 1, c) 
                || solve_maze(collection, output, rows, cols, r, c - 1))
            {
                return true;
            }
            // Deactivate visited node status
            output[r][c] = false;
        }
        return false;
    }
    //Handles the request to find maze solution
    public void maze_test(int[][] collection, int rows, int cols)
    {
        //Create resultant grid
        boolean[][] output = new boolean[rows][cols];
        int i = 0;
        int j = 0;
        //Set initial values
        for (i = 0; i < rows; ++i)
        {
            for (j = 0; j < cols; ++j)
            {
                output[i][j] = false;
            }
        }
        if (solve_maze(collection, output, rows, cols, 0, 0))
        {
            //When result are exist
            // Print input problem
            System.out.print("\n  Input Maze \n");
            print_maze(collection,rows,cols);
            // Display output solution
            System.out.print("  Output Maze \n");
            //result
            for (i = 0; i < rows; ++i)
            {
                for (j = 0; j < cols; ++j)
                {
                    if( output[i][j] == false)
                    {
                        System.out.print("  0" );
                    }
                    else
                    {
                        System.out.print("  1" );
                    }
                    output[i][j] = false;
                }
                System.out.print("\n");
            }
        }
        else
        {
            //When no solution possible
            System.out.print("\n No Result \n");
        }
    }
    public static void main(String[] args)
    {
        Maze obj = new Maze();
        int[][] collection = {
            {
                1 , 0 , 1 , 1 , 1 , 1
            } , {
                1 , 1 , 1 , 1 , 0 , 1
            } , {
                0 , 1 , 0 , 0 , 1 , 1
            } , {
                1 , 0 , 1 , 1 , 1 , 0
            } , {
                1 , 0 , 1 , 1 , 0 , 1
            } , {
                1 , 0 , 1 , 1 , 1 , 1
            }
        };
        int rows = collection.length;
        int cols = collection[0].length;
        obj.maze_test(collection, rows, cols);
    }
}

Output

  Input Maze
  1  0  1  1  1  1
  1  1  1  1  0  1
  0  1  0  0  1  1
  1  0  1  1  1  0
  1  0  1  1  0  1
  1  0  1  1  1  1

  Output Maze
  1  0  0  1  1  1
  1  1  1  1  0  1
  0  0  0  0  1  1
  0  0  0  1  1  0
  0  0  0  1  0  0
  0  0  0  1  1  1
//Include header file
#include <iostream>
#define SIZE 6
using namespace std;

/*
  C++ program 
  Rat in a Maze
*/
class Maze
{
    public:
        //Print grid elements
        void print_maze(int grid[SIZE][SIZE], int rows, int cols)
        {
            int i = 0;
            int j = 0;
            //Set initial values
            for (i = 0; i < rows; ++i)
            {
                for (j = 0; j < cols; ++j)
                {
                    cout << "  " << grid[i][j];
                }
                cout << "\n";
            }
            cout << "\n";
        }
    //Using backtracking find maze solution
    //If solutions are not exist then it returns 0 (False).
    bool solve_maze(int collection[SIZE][SIZE], bool output[SIZE][SIZE], int rows, int cols, int r, int c)
    {
        if (r < 0 || r >= rows || c < 0 || c >= cols)
        {
            //When not valid position
            return false;
        }
        else if (r == rows - 1 && c == cols - 1)
        {
            //When we get destination position
            if (collection[r][c] == 1)
            {
                //When destination are active element
                output[r][c] = true;
                return true;
            }
        }
        if (output[r][c] == true)
        {
            //When the element has been already been visited
            return false;
        }
        if (collection[r][c] == 1)
        {
            //Active visiting node
            output[r][c] = true;
            //Test four possible direction
            if (this->solve_maze(collection, output, rows, cols, r + 1, c) 
                || this->solve_maze(collection, output, rows, cols, r, c + 1) 
                || this->solve_maze(collection, output, rows, cols, r - 1, c) 
                || this->solve_maze(collection, output, rows, cols, r, c - 1))
            {
                return true;
            }
            // Deactivate visited node status
            output[r][c] = false;
        }
        return false;
    }
    //Handles the request to find maze solution
    void maze_test(int collection[SIZE][SIZE], int rows, int cols)
    {
        //Create resultant grid
        bool output[SIZE][SIZE];
        int i = 0;
        int j = 0;
        //Set initial values
        for (i = 0; i < rows; ++i)
        {
            for (j = 0; j < cols; ++j)
            {
                output[i][j] = false;
            }
        }
        if (this->solve_maze(collection, output, rows, cols, 0, 0)==true)
        {
            //When result are exist
            // Print input problem
            cout << "\n  Input Maze \n";
            this->print_maze(collection, rows, cols);
            // Display output solution
            cout << "  Output Maze \n";
            //result
            for (i = 0; i < rows; ++i)
            {
                for (j = 0; j < cols; ++j)
                {
                    if (output[i][j] == false)
                    {
                        cout << "  0";
                    }
                    else
                    {
                        cout << "  1";
                    }
                    output[i][j] = false;
                }
                cout << "\n";
            }
        }
        else
        {
            //When no solution possible
            cout << "\n No Result \n";
        }
    }
};
int main()
{
    Maze obj = Maze();
    int collection[SIZE][SIZE] = {
        {
            1 , 0 , 1 , 1 , 1 , 1
        } , 
        {
            1 , 1 , 1 , 1 , 0 , 1
        } , 
        {
            0 , 1 , 0 , 0 , 1 , 1
        } , 
        {
            1 , 0 , 1 , 1 , 1 , 0
        } , 
        {
            1 , 0 , 1 , 1 , 0 , 1
        } , 
        {
            1 , 0 , 1 , 1 , 1 , 1
        }
    };
    int rows = sizeof(collection) / sizeof(collection[0]);
    int cols = sizeof(collection[0]) / sizeof(collection[0][0]);
    obj.maze_test(collection, rows, cols);
    return 0;
}

Output

  Input Maze
  1  0  1  1  1  1
  1  1  1  1  0  1
  0  1  0  0  1  1
  1  0  1  1  1  0
  1  0  1  1  0  1
  1  0  1  1  1  1

  Output Maze
  1  0  0  1  1  1
  1  1  1  1  0  1
  0  0  0  0  1  1
  0  0  0  1  1  0
  0  0  0  1  0  0
  0  0  0  1  1  1
//Include namespace system
using System;
/*
  C# program 
  Rat in a Maze
*/
class Maze
{
    //Print grid elements
    public void print_maze(int[,] grid, int rows, int cols)
    {
        int i = 0;
        int j = 0;
        //Set initial values
        for (i = 0; i < rows; ++i)
        {
            for (j = 0; j < cols; ++j)
            {
                Console.Write("  " + grid[i,j]);
            }
            Console.Write("\n");
        }
        Console.Write("\n");
    }
    //Using backtracking find maze solution
    //If solutions are not exist then it returns 0 (False).
    public Boolean solve_maze(int[,] collection, Boolean[,] output, int rows, int cols, int r, int c)
    {
        if (r < 0 || r >= rows || c < 0 || c >= cols)
        {
            //When not valid position
            return false;
        }
        else if (r == rows - 1 && c == cols - 1)
        {
            //When we get destination position
            if (collection[r,c] == 1)
            {
                //When destination are active element
                output[r,c] = true;
                return true;
            }
        }
        if (output[r,c] == true)
        {
            //When the element has been already been visited
            return false;
        }
        if (collection[r,c] == 1)
        {
            //Active visiting node
            output[r,c] = true;
            //Test four possible direction
            if (solve_maze(collection, output, rows, cols, r + 1, c) || solve_maze(collection, output, rows, cols, r, c + 1) || solve_maze(collection, output, rows, cols, r - 1, c) || solve_maze(collection, output, rows, cols, r, c - 1))
            {
                return true;
            }
            // Deactivate visited node status
            output[r,c] = false;
        }
        return false;
    }
    //Handles the request to find maze solution
    public void maze_test(int[,] collection, int rows, int cols)
    {
        //Create resultant grid
        Boolean[,] output = new Boolean[rows,cols];
        int i = 0;
        int j = 0;
        //Set initial values
        for (i = 0; i < rows; ++i)
        {
            for (j = 0; j < cols; ++j)
            {
                output[i,j] = false;
            }
        }
        if (solve_maze(collection, output, rows, cols, 0, 0))
        {
            //When result are exist
            // Print input problem
            Console.Write("\n  Input Maze \n");
            print_maze(collection, rows, cols);
            // Display output solution
            Console.Write("  Output Maze \n");
            //result
            for (i = 0; i < rows; ++i)
            {
                for (j = 0; j < cols; ++j)
                {
                    if (output[i,j] == false)
                    {
                        Console.Write("  0");
                    }
                    else
                    {
                        Console.Write("  1");
                    }
                    output[i,j] = false;
                }
                Console.Write("\n");
            }
        }
        else
        {
            //When no solution possible
            Console.Write("\n No Result \n");
        }
    }
    public static void Main(String[] args)
    {
        Maze obj = new Maze();
        int[,] collection = {
            {
                1 , 0 , 1 , 1 , 1 , 1
            } , {
                1 , 1 , 1 , 1 , 0 , 1
            } , {
                0 , 1 , 0 , 0 , 1 , 1
            } , {
                1 , 0 , 1 , 1 , 1 , 0
            } , {
                1 , 0 , 1 , 1 , 0 , 1
            } , {
                1 , 0 , 1 , 1 , 1 , 1
            }
        };
        int rows = collection.GetLength(0);
        int cols = collection.GetLength(1);
        obj.maze_test(collection, rows, cols);
    }
}

Output

  Input Maze
  1  0  1  1  1  1
  1  1  1  1  0  1
  0  1  0  0  1  1
  1  0  1  1  1  0
  1  0  1  1  0  1
  1  0  1  1  1  1

  Output Maze
  1  0  0  1  1  1
  1  1  1  1  0  1
  0  0  0  0  1  1
  0  0  0  1  1  0
  0  0  0  1  0  0
  0  0  0  1  1  1
<?php
/*
  Php program 
  Rat in a Maze
*/
class Maze
{
    //Print grid elements
    public  function print_maze( & $grid, $rows, $cols)
    {
        $i = 0;
        $j = 0;
        //Set initial values
        while ($i < $rows)
        {
            $j = 0;
            while ($j < $cols)
            {
                echo "  ". $grid[$i][$j];
                ++$j;
            }
            echo "\n";
            ++$i;
        }
        echo "\n";
    }
    //Using backtracking find maze solution
    //If solutions are not exist then it returns 0 (False).
    public  function solve_maze( & $collection, & $output, $rows, $cols, $r, $c)
    {
        if ($r < 0 || $r >= $rows || $c < 0 || $c >= $cols)
        {
            //When not valid position
            return false;
        }
        else if ($r == $rows - 1 && $c == $cols - 1)
        {
            //When we get destination position
            if ($collection[$r][$c] == 1)
            {
                //When destination are active element
                $output[$r][$c] = true;
                return true;
            }
        }
        if ($output[$r][$c] == true)
        {
            //When the element has been already been visited
            return false;
        }
        if ($collection[$r][$c] == 1)
        {
            //Active visiting node
            $output[$r][$c] = true;
            //Test four possible direction
            if ($this->solve_maze($collection, $output, $rows, $cols, $r + 1, $c) || $this->solve_maze($collection, $output, $rows, $cols, $r, $c + 1) || $this->solve_maze($collection, $output, $rows, $cols, $r - 1, $c) || $this->solve_maze($collection, $output, $rows, $cols, $r, $c - 1))
            {
                return true;
            }
            // Deactivate visited node status
            $output[$r][$c] = false;
        }
        return false;
    }
    //Handles the request to find maze solution
    public  function maze_test( & $collection, $rows, $cols)
    {
        //Create resultant grid
        $output = array_fill(0, $rows, array_fill(0, $cols, false));
        $i = 0;
        $j = 0;
        if ($this->solve_maze($collection, $output, $rows, $cols, 0, 0))
        {
            //When result are exist
            // Print input problem
            echo "\n  Input Maze \n";
            $this->print_maze($collection, $rows, $cols);
            // Display output solution
            echo "  Output Maze \n";
            //result
            $i = 0;
            while ($i < $rows)
            {
                $j = 0;
                while ($j < $cols)
                {
                    if ($output[$i][$j] == false)
                    {
                        echo "  0";
                    }
                    else
                    {
                        echo "  1";
                    }
                    $output[$i][$j] = false;
                    ++$j;
                }
                echo "\n";
                ++$i;
            }
        }
        else
        {
            //When no solution possible
            echo "\n No Result \n";
        }
    }
}

function main()
{
    $obj = new Maze();
    $collection = array(array(1, 0, 1, 1, 1, 1), 
                        array(1, 1, 1, 1, 0, 1), 
                        array(0, 1, 0, 0, 1, 1), 
                        array(1, 0, 1, 1, 1, 0), 
                        array(1, 0, 1, 1, 0, 1), 
                        array(1, 0, 1, 1, 1, 1));
    $rows = count($collection);
    $cols = count($collection[0]);
    $obj->maze_test($collection, $rows, $cols);
}
main();

Output

  Input Maze
  1  0  1  1  1  1
  1  1  1  1  0  1
  0  1  0  0  1  1
  1  0  1  1  1  0
  1  0  1  1  0  1
  1  0  1  1  1  1

  Output Maze
  1  0  0  1  1  1
  1  1  1  1  0  1
  0  0  0  0  1  1
  0  0  0  1  1  0
  0  0  0  1  0  0
  0  0  0  1  1  1
/*
  Node Js program 
  Rat in a Maze
*/
class Maze
{
    //Print grid elements
    print_maze(grid, rows, cols)
    {
        var i = 0;
        var j = 0;
        //Set initial values
        while (i < rows)
        {
            j = 0;
            while (j < cols)
            {
                process.stdout.write("  " + grid[i][j]);
                ++j;
            }
            process.stdout.write("\n");
            ++i;
        }
        process.stdout.write("\n");
    }
    //Using backtracking find maze solution
    //If solutions are not exist then it returns 0 (False).
    solve_maze(collection, output, rows, cols, r, c)
    {
        if (r < 0 || r >= rows || c < 0 || c >= cols)
        {
            //When not valid position
            return false;
        }
        else if (r == rows - 1 && c == cols - 1)
        {
            //When we get destination position
            if (collection[r][c] == 1)
            {
                //When destination are active element
                output[r][c] = true;
                return true;
            }
        }
        if (output[r][c] == true)
        {
            //When the element has been already been visited
            return false;
        }
        if (collection[r][c] == 1)
        {
            //Active visiting node
            output[r][c] = true;
            //Test four possible direction
            if (this.solve_maze(collection, output, rows, cols, r + 1, c) || this.solve_maze(collection, output, rows, cols, r, c + 1) || this.solve_maze(collection, output, rows, cols, r - 1, c) || this.solve_maze(collection, output, rows, cols, r, c - 1))
            {
                return true;
            }
            // Deactivate visited node status
            output[r][c] = false;
        }
        return false;
    }
    //Handles the request to find maze solution
    maze_test(collection, rows, cols)
    {
        //Create resultant grid
        var output = Array(rows).fill(false).map(() => new Array(cols).fill(false));
        var i = 0;
        var j = 0;
        if (this.solve_maze(collection, output, rows, cols, 0, 0))
        {
            //When result are exist
            // Print input problem
            process.stdout.write("\n  Input Maze \n");
            this.print_maze(collection, rows, cols);
            // Display output solution
            process.stdout.write("  Output Maze \n");
            //result
            i = 0;
            while (i < rows)
            {
                j = 0;
                while (j < cols)
                {
                    if (output[i][j] == false)
                    {
                        process.stdout.write("  0");
                    }
                    else
                    {
                        process.stdout.write("  1");
                    }
                    output[i][j] = false;
                    ++j;
                }
                process.stdout.write("\n");
                ++i;
            }
        }
        else
        {
            //When no solution possible
            process.stdout.write("\n No Result \n");
        }
    }
}

function main()
{
    var obj = new Maze();
    var collection = [
        [1, 0, 1, 1, 1, 1],
        [1, 1, 1, 1, 0, 1],
        [0, 1, 0, 0, 1, 1],
        [1, 0, 1, 1, 1, 0],
        [1, 0, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 1]
    ];
    var rows = collection.length;
    var cols = collection[0].length;
    obj.maze_test(collection, rows, cols);
}
main();

Output

  Input Maze
  1  0  1  1  1  1
  1  1  1  1  0  1
  0  1  0  0  1  1
  1  0  1  1  1  0
  1  0  1  1  0  1
  1  0  1  1  1  1

  Output Maze
  1  0  0  1  1  1
  1  1  1  1  0  1
  0  0  0  0  1  1
  0  0  0  1  1  0
  0  0  0  1  0  0
  0  0  0  1  1  1
#   Python 3 program 
#   Rat in a Maze

class Maze :
    # Print grid elements
    def print_maze(self, grid, rows, cols) :
        i = 0
        j = 0
        # Set initial values
        while (i < rows) :
            j = 0
            while (j < cols) :
                print("  ", grid[i][j], end = "")
                j += 1
            
            print("\n", end = "")
            i += 1
        
        print("\n", end = "")
    
    # Using backtracking find maze solution
    # If solutions are not exist then it returns 0 (False).
    def solve_maze(self, collection, output, rows, cols, r, c) :
        if (r < 0 or r >= rows or c < 0 or c >= cols) :
            # When not valid position
            return False
        
        elif(r == rows - 1 and c == cols - 1) :
            # When we get destination position
            if (collection[r][c] == 1) :
                # When destination are active element
                output[r][c] = True
                return True
            
        
        if (output[r][c] == True) :
            # When the element has been already been visited
            return False
        
        if (collection[r][c] == 1) :
            # Active visiting node
            output[r][c] = True
            # Test four possible direction
            if (self.solve_maze(collection, output, rows, cols, r + 1, c) or self.solve_maze(collection, output, rows, cols, r, c + 1) or self.solve_maze(collection, output, rows, cols, r - 1, c) or self.solve_maze(collection, output, rows, cols, r, c - 1)) :
                return True
            
            #  Deactivate visited node status
            output[r][c] = False
        
        return False
    
    # Handles the request to find maze solution
    def maze_test(self, collection, rows, cols) :
        # Create resultant grid
        output = [[False] * (cols) for _ in range(rows) ]
        i = 0
        j = 0
        if (self.solve_maze(collection, output, rows, cols, 0, 0)) :
            # When result are exist
            #  Print input problem
            print("\n  Input Maze \n", end = "")
            self.print_maze(collection, rows, cols)
            #  Display output solution
            print("  Output Maze \n", end = "")
            # result
            i = 0
            while (i < rows) :
                j = 0
                while (j < cols) :
                    if (output[i][j] == False) :
                        print("   0", end = "")
                    else :
                        print("   1", end = "")
                    
                    output[i][j] = False
                    j += 1
                
                print("\n", end = "")
                i += 1
            
        else :
            # When no solution possible
            print("\n No Result \n", end = "")
        
    

def main() :
    obj = Maze()
    collection = [
        [1, 0, 1, 1, 1, 1],
        [1, 1, 1, 1, 0, 1],
        [0, 1, 0, 0, 1, 1],
        [1, 0, 1, 1, 1, 0],
        [1, 0, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 1]
    ]
    rows = len(collection)
    cols = len(collection[0])
    obj.maze_test(collection, rows, cols)

if __name__ == "__main__": main()

Output

  Input Maze
   1   0   1   1   1   1
   1   1   1   1   0   1
   0   1   0   0   1   1
   1   0   1   1   1   0
   1   0   1   1   0   1
   1   0   1   1   1   1

  Output Maze
   1   0   0   1   1   1
   1   1   1   1   0   1
   0   0   0   0   1   1
   0   0   0   1   1   0
   0   0   0   1   0   0
   0   0   0   1   1   1
#   Ruby program 
#   Rat in a Maze

class Maze 
    # Print grid elements
    def print_maze(grid, rows, cols) 
        i = 0
        j = 0
        # Set initial values
        while (i < rows) 
            j = 0
            while (j < cols) 
                print("  ", grid[i][j])
                j += 1
            end

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

        print("\n")
    end

    # Using backtracking find maze solution
    # If solutions are not exist then it returns 0 (False).
    def solve_maze(collection, output, rows, cols, r, c) 
        if (r < 0 || r >= rows || c < 0 || c >= cols) 
            # When not valid position
            return false
        elsif(r == rows - 1 && c == cols - 1) 
            # When we get destination position
            if (collection[r][c] == 1) 
                # When destination are active element
                output[r][c] = true
                return true
            end

        end

        if (output[r][c] == true) 
            # When the element has been already been visited
            return false
        end

        if (collection[r][c] == 1) 
            # Active visiting node
            output[r][c] = true
            # Test four possible direction
            if (self.solve_maze(collection, output, rows, cols, r + 1, c) || self.solve_maze(collection, output, rows, cols, r, c + 1) || self.solve_maze(collection, output, rows, cols, r - 1, c) || self.solve_maze(collection, output, rows, cols, r, c - 1)) 
                return true
            end

            #  Deactivate visited node status
            output[r][c] = false
        end

        return false
    end

    # Handles the request to find maze solution
    def maze_test(collection, rows, cols) 
        # Create resultant grid
        output = Array.new(rows) {Array.new(cols) {false}}
        i = 0
        j = 0
        if (self.solve_maze(collection, output, rows, cols, 0, 0)) 
            # When result are exist
            #  Print input problem
            print("\n  Input Maze \n")
            self.print_maze(collection, rows, cols)
            #  Display output solution
            print("  Output Maze \n")
            # result
            i = 0
            while (i < rows) 
                j = 0
                while (j < cols) 
                    if (output[i][j] == false) 
                        print("  0")
                    else 
                        print("  1")
                    end

                    output[i][j] = false
                    j += 1
                end

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

        else 
            # When no solution possible
            print("\n No Result \n")
        end

    end

end

def main() 
    obj = Maze.new()
    collection = [
        [1, 0, 1, 1, 1, 1],
        [1, 1, 1, 1, 0, 1],
        [0, 1, 0, 0, 1, 1],
        [1, 0, 1, 1, 1, 0],
        [1, 0, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 1]
    ]
    rows = collection.length
    cols = collection[0].length
    obj.maze_test(collection, rows, cols)
end

main()

Output

  Input Maze 
  1  0  1  1  1  1
  1  1  1  1  0  1
  0  1  0  0  1  1
  1  0  1  1  1  0
  1  0  1  1  0  1
  1  0  1  1  1  1

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

/*
  Scala program 
  Rat in a Maze
*/
class Maze
{
    //Print grid elements
    def print_maze(grid: Array[Array[Int]], 
      rows: Int, cols: Int): Unit = {
        var i: Int = 0;
        var j: Int = 0;
        //Set initial values
        while (i < rows)
        {
            j = 0;
            while (j < cols)
            {
                print("  " + grid(i)(j));
                j += 1;
            }
            print("\n");
            i += 1;
        }
        print("\n");
    }
    //Using backtracking find maze solution
    //If solutions are not exist then it returns 0 (False).
    def solve_maze(collection: Array[Array[Int]], 
      output: Array[Array[Boolean]], 
        rows: Int, cols: Int, r: Int, c: Int): Boolean = {
        if (r < 0 || r >= rows || c < 0 || c >= cols)
        {
            //When not valid position
            return false;
        }
        else if (r == rows - 1 && c == cols - 1)
        {
            //When we get destination position
            if (collection(r)(c) == 1)
            {
                //When destination are active element
                output(r)(c) = true;
                return true;
            }
        }
        if (output(r)(c) == true)
        {
            //When the element has been already been visited
            return false;
        }
        if (collection(r)(c) == 1)
        {
            //Active visiting node
            output(r)(c) = true;
            //Test four possible direction
            if (solve_maze(collection, output, rows, cols, r + 1, c) 
                || solve_maze(collection, output, rows, cols, r, c + 1) 
                || solve_maze(collection, output, rows, cols, r - 1, c) 
                || solve_maze(collection, output, rows, cols, r, c - 1))
            {
                return true;
            }
            // Deactivate visited node status
            output(r)(c) = false;
        }
        return false;
    }
    //Handles the request to find maze solution
    def maze_test(collection: Array[Array[Int]], rows: Int, cols: Int): Unit = {
        //Create resultant grid
        var output: Array[Array[Boolean]] = Array.fill[Boolean](rows, cols)(false);
        var i: Int = 0;
        var j: Int = 0;
    
        if (solve_maze(collection, output, rows, cols, 0, 0))
        {
            //When result are exist
            // Print input problem
            print("\n  Input Maze \n");
            print_maze(collection, rows, cols);
            // Display output solution
            print("  Output Maze \n");
            //result
            i = 0;
            while (i < rows)
            {
                j = 0;
                while (j < cols)
                {
                    if (output(i)(j) == false)
                    {
                        print("  0");
                    }
                    else
                    {
                        print("  1");
                    }
                    output(i)(j) = false;
                    j += 1;
                }
                print("\n");
                i += 1;
            }
        }
        else
        {
            //When no solution possible
            print("\n No Result \n");
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var obj: Maze = new Maze();
        var collection: Array[Array[Int]] = Array(Array(1, 0, 1, 1, 1, 1), Array(1, 1, 1, 1, 0, 1), Array(0, 1, 0, 0, 1, 1), Array(1, 0, 1, 1, 1, 0), Array(1, 0, 1, 1, 0, 1), Array(1, 0, 1, 1, 1, 1));
        var rows: Int = collection.length;
        var cols: Int = collection(0).length;
        obj.maze_test(collection, rows, cols);
    }
}

Output

  Input Maze
  1  0  1  1  1  1
  1  1  1  1  0  1
  0  1  0  0  1  1
  1  0  1  1  1  0
  1  0  1  1  0  1
  1  0  1  1  1  1

  Output Maze
  1  0  0  1  1  1
  1  1  1  1  0  1
  0  0  0  0  1  1
  0  0  0  1  1  0
  0  0  0  1  0  0
  0  0  0  1  1  1
/*
  Swift 4 program 
  Rat in a Maze
*/
class Maze
{
    //Print grid elements
    func print_maze(_ grid: [[Int]], _ rows: Int, _ cols: Int)
    {
        var i: Int = 0;
        var j: Int = 0;
        //Set initial values
        while (i < rows)
        {
            j = 0;
            while (j < cols)
            {
                print("  ", grid[i][j], terminator: "");
                j += 1;
            }
            print("\n", terminator: "");
            i += 1;
        }
        print("\n", terminator: "");
    }
    //Using backtracking find maze solution
    //If solutions are not exist then it returns 0 (False).
    func solve_maze(_ collection: [[Int]], _ output: inout[[Bool]], _ rows: Int, _ cols: Int, _ r: Int, _ c: Int) -> Bool
    {
        if (r < 0 || r >= rows || c < 0 || c >= cols)
        {
            //When not valid position
            return false;
        }
        else if (r == rows - 1 && c == cols - 1)
        {
            //When we get destination position
            if (collection[r][c] == 1)
            {
                //When destination are active element
                output[r][c] = true;
                return true;
            }
        }
        if (output[r][c] == true)
        {
            //When the element has been already been visited
            return false;
        }
        if (collection[r][c] == 1)
        {
            //Active visiting node
            output[r][c] = true;
            //Test four possible direction
            if (self.solve_maze(collection, &output, rows, cols, r + 1, c) 
                || self.solve_maze(collection, &output, rows, cols, r, c + 1) 
                || self.solve_maze(collection, &output, rows, cols, r - 1, c) 
                || self.solve_maze(collection, &output, rows, cols, r, c - 1))
            {
                return true;
            }
            // Deactivate visited node status
            output[r][c] = false;
        }
        return false;
    }
    //Handles the request to find maze solution
    func maze_test(_ collection: [[Int]], _ rows: Int, _ cols: Int)
    {
        //Create resultant grid
        var output: [[Bool]] = Array(repeating: Array(repeating: false, count: cols), count: rows);
        var i: Int = 0;
        var j: Int = 0;
        if (self.solve_maze(collection, &output, rows, cols, 0, 0))
        {
            //When result are exist
            // Print input problem
            print("\n  Input Maze \n", terminator: "");
            self.print_maze(collection, rows, cols);
            // Display output solution
            print("  Output Maze \n", terminator: "");
            //result
            i = 0;
            while (i < rows)
            {
                j = 0;
                while (j < cols)
                {
                    if (output[i][j] == false)
                    {
                        print("   0", terminator: "");
                    }
                    else
                    {
                        print("   1", terminator: "");
                    }
                    output[i][j] = false;
                    j += 1;
                }
                print("\n", terminator: "");
                i += 1;
            }
        }
        else
        {
            //When no solution possible
            print("\n No Result \n", terminator: "");
        }
    }
}
func main()
{
    let obj: Maze = Maze();
    let collection: [[Int]] = [[1, 0, 1, 1, 1, 1],
        [1, 1, 1, 1, 0, 1],
        [0, 1, 0, 0, 1, 1],
        [1, 0, 1, 1, 1, 0],
        [1, 0, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 1]];
    let rows: Int = collection.count;
    let cols: Int = collection[0].count;
    obj.maze_test(collection, rows, cols);
}
main();

Output

  Input Maze
   1   0   1   1   1   1
   1   1   1   1   0   1
   0   1   0   0   1   1
   1   0   1   1   1   0
   1   0   1   1   0   1
   1   0   1   1   1   1

  Output Maze
   1   0   0   1   1   1
   1   1   1   1   0   1
   0   0   0   0   1   1
   0   0   0   1   1   0
   0   0   0   1   0   0
   0   0   0   1   1   1
Last updated on by Kalkicode




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