Question

Java maze

Create a grid of #’s and dots(.) using a two dimensional array representation of a maze that looks like this:

############

#...#......#

..#.#.####.#

###.#....#.#

#....###.#..

####.#.#.#.#

#..#.#.#.#.#

##.#.#.#.#.#

#........#.#

######.###.#

#......#...#

#’s represent the walls of the maze, and the dots represent locations in the possible paths through the maze. A move can be made only to a location in the array that contains a dot.

You can use any maze formation you wish, but there must be a starting point and exit, with a path to each with some dead paths along the way.

Write a program that contains a recursive method (mazeTraversal) to walk through the maze. The method should receive as arguments a 12 by 12 character array representing the maze and the current location in the maze. (The first time this method is called, it should receive the entry point in the maze. In this example, it would be 2,0). As mazeTraversal attempts to locate the exit, it should place the character x in each square in the path, which is used as a breadcrumb to indicate where it has been.

The algorithm: From the current location in the maze, try to move one space in any of the possible directions(down, right, up or left). If it’s possible to move in at least one direction, call mazeTraversal recursively, passing the new spot on the maze as the current spot. If it’s not possible to go in any direction, “back up” to a previous location in the maze and try a new direction for that location (this is an example of recursive backtracking). Program the method to display the maze after each move so the user can watch as the maze is solved. The final output of the maze should display only the path needed to solve the maze---If going in a particular direction results in a dead end, the x’s going in that direction should not be displayed. [Hint: To display only the final path, it may be helpful to mark off spots that result in a dead end with another character.

Answer 1

# Maze size 
N=12

# A utility function to print solution matrix sol 
def printSolution( sol ): 
        
        for i in sol: 
                for j in i: 
                        print(str(j) + " ", end ="") 
                print("") 

# A utility function to check if x, y is valid 
# index for N * N Maze 
def isSafe( maze, x, y ): 
        
        if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1: 
                return True
        
        return False

""" This function solves the Maze problem using Backtracking. 
        It mainly uses solveMazeUtil() to solve the problem. It 
        returns false if no path is possible, otherwise return 
        true and prints the path in the form of 1s. Please note 
        that there may be more than one solutions, this function 
        prints one of the feasable solutions. """
def solveMaze( maze ): 
        
        
        sol = [ [ 0 for j in range(12) ] for i in range(12) ] 
        
        if solveMazeUtil(maze, 0, 0, sol) == False: 
                print("Solution doesn't exist"); 
                return False
        
        printSolution(sol) 
        return True
        
# A recursive utility function to solve Maze problem 
def solveMazeUtil(maze, x, y, sol): 
        
        # if (x, y is goal) return True 
        if x == N - 1 and y == N - 1 and maze[x][y]== 1: 
                sol[x][y] = '.'
                return True
                
        # Check if maze[x][y] is valid 
        if isSafe(maze, x, y) == True: 
                # mark x, y as part of solution path 
                sol[x][y] = '.'
                
                # Move forward in x direction 
                if solveMazeUtil(maze, x + 1, y, sol) == True: 
                        return True
                        
                # If moving in x direction doesn't give solution 
                # then Move down in y direction 
                if solveMazeUtil(maze, x, y + 1, sol) == True: 
                        return True
                
                # If none of the above movements work then 
                # BACKTRACK: unmark x, y as part of solution path 
                sol[x][y] = '!'
                return False


# Initialising the maze 
m=[['#','#','#','#','#','#','#','#','#','#','#','#']

['#','.','.','.','#','.','.','.','.','.','.','#'],

['.','.','#','.','#','.','#','#','#','#','.','#'],

['#','#','#','.','#','.','.','.','.','#','.','#'],

['#','.','.','.','.','#','#','#','.','#','.','.'],

['#','#','#','#','.','#','.','#','.','#','.','#'],

['#','.','.','#','.','#','.','#','.','#','.','#'],

['#','#','.','#','.','#','.','#','.','#','.','#'],

['#','.','.','.','.','.','.','.','.','#','.','#'],

['#','#','#','#','#','#','.','#','#','#','.','#'],

['#','.','.','.','.','.','.','#','.','.','.','#']]
rows=len(m)
cols=len(m[0])
maze=[][]
for i in range(rows):
  for j in range(cols):
    if m[i][j]=='#':
      maze[i][j]=0
    else:
      maze[i][j]=1
    
                        
solveMaze(maze)