1. Introduction. In this assignment you are required to simulate maze traversal using so called recursive backtracking (the algorithm is given below). The grid of #s and 0s in the following Figure is a two-dimensional array representation of a maze. The #s represent the walls of the maze, and the zeros represent locations in the possible paths through the maze. Moves can be made only to a location in the array that contains a zero. # # # # # # # # # # # # # 0 0 0 # 0 0 0 0 0 0 # 0 0 # 0 # 0 # # # # 0 # # # # 0 # 0 0 0 0 # 0 # # 0 0 0 0 # # # 0 # 0 0 # # # # 0 # 0 # 0 # 0 # # 0 0 # 0 # 0 # 0 # 0 # # # 0 # 0 # 0 # 0 # 0 # # 0 0 0 0 0 0 0 0 # 0 # # # # # # # 0 # # # 0 # # 0 0 0 0 0 0 # 0 0 0 # # # # # # # # # # # # #
Write a recursive method called mazeTraversal, to walk through a maze like the one shown above. The method should receive, as arguments, an n-by-n ( ) character array representing the maze and the current location in the maze (the first time this method is called, the current location should be the entry point of the maze). The mazeTraversal method should attempt to locate the exit, it should also place the character x in each square in the path. There is a simple algorithm for walking through a maze that guarantees finding the exit (assuming there is an exit). If there is no exit, you will arrive at the starting location again.
The algorithm for the method is as follows: • From the current location in the maze, try to move one space in direction (down, right, up or left). • If it is possible to move in at least one direction, call mazeTraversal recursively, passing the new spot in the maze as the current spot. • If it is not possible to go in any direction, return to a previous location in the maze and try a new direction from that location
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.
1. Class Maze. The Maze class should have: A) Two instance variables – private int size, private char[][] maze;
B) Constructor “public Maze(char[][] c)” – takes as an argument an n-by-n ( ) two-dimensional character array that contains only #s and 0s.
C) Method “public void mazeTraversal(int a, int b)” – walks through this maze. Parameters a, b represent the entry point to the maze. Recursive algorithm for the mazeTraversal method is described in the previous section.
D) Method “public void print()” – prints this maze in a tabular format.
E) Method “public char[][] mazeGenerator()” – randomly produces an n-by-n ( ) Maze object which has an entry point on the left side. The algorithm for mazeGenerator should be as follows: • You start with 2-dimensional n-by-n array maze containing only #s, and then you “dig” your way through it until reaching the border, marking the visited cells with 0s. • The entry point is maze[n/2][0] • First move is to the right, after that you chose randomly any of four possible directions to move. • Method stops when it reaches the border.
F) Default constructor “public Maze()” – calls the mazeGenerator.
2. Class TestMaze. This class has only a main method. In the main method you should create three Maze objects: • One on the figure in the section 0. • A 12-by-12 maze that has an entry point but does not have an exit. You should design it yourself. • A randomly generated maze object Then the mazeTraversal method should be called on each of the created objects.
Hint! mazeTraversal method mazeGenerator method print constructors class TestMaze
. Introduction. In this assignment you are required to simulate maze traversal using so called recursive backtracking (the algorithm is given below). The grid of #s and 0s in the following Figure is a two-dimensional array representation of a maze. The #s represent the walls of the maze, and the zeros represent locations in the possible paths through the maze. Moves can be made only to a location in the array that contains a zero.
Write a recursive method called mazeTraversal, to walk through a maze like the one shown above. The method should receive, as arguments, an n-by-n ( ) character array representing the maze and the current location in the maze (the first time this method is called, the current location should be the entry point of the maze). The mazeTraversal method should attempt to locate the exit, it should also place the character x in each square in the path. There is a simple algorithm for walking through a maze that guarantees finding the exit (assuming there is an exit). If there is no exit, you will arrive at the starting location again.
The algorithm for the method is as follows: • From the current location in the maze, try to move one space in direction (down, right, up or left). • If it is possible to move in at least one direction, call mazeTraversal recursively, passing the new spot in the maze as the current spot. • If it is not possible to go in any direction, return to a previous location in the maze and try a new direction from that location
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.
1. Class Maze. The Maze class should have: A) Two instance variables – private int size, private char[][] maze;
B) Constructor “public Maze(char[][] c)” – takes as an argument an n-by-n ( ) two-dimensional character array that contains only #s and 0s.
C) Method “public void mazeTraversal(int a, int b)” – walks through this maze. Parameters a, b represent the entry point to the maze. Recursive algorithm for the mazeTraversal method is described in the previous section.
D) Method “public void print()” – prints this maze in a tabular format.
E) Method “public char[][] mazeGenerator()” – randomly produces an n-by-n ( ) Maze object which has an entry point on the left side. The algorithm for mazeGenerator should be as follows: • You start with 2-dimensional n-by-n array maze containing only #s, and then you “dig” your way through it until reaching the border, marking the visited cells with 0s. • The entry point is maze[n/2][0] • First move is to the right, after that you chose randomly any of four possible directions to move. • Method stops when it reaches the border.
F) Default constructor “public Maze()” – calls the mazeGenerator.
2. Class TestMaze. This class has only a main method. In the main method you should create three Maze objects: • One on the figure in the section 0. • A 12-by-12 maze that has an entry point but does not have an exit. You should design it yourself. • A randomly generated maze object Then the mazeTraversal method should be called on each of the created objects.
Hint! mazeTraversal method mazeGenerator method print constructors class TestMaze
i really apretiate u people replied i was just checking whether u can sove this problem or not. i have already sloved this problem and i don't need any help from u people regarding this assignment.
sandeep i need a help... i hav te same assignemnt...can u pls send tis assignemnt to me ma mail id is chander.balan@gmail.com pls i need it vey ugently..
sandeep i need a help... i hav te same assignemnt...can u pls send tis assignemnt to me ma mail id is chander.balan@gmail.com pls i need it vey ugently..
Previous Topic
