Introduction

In this assignment you are required to simulate a maze traversal, i.e. you need to develop a program that starts from some location in a maze, and searches it to locate an exit.

The maze should be implemented as a two-dimensional array of characters, where #s represent walls of the maze, whitespace characters represent empty spaces in the maze through which one can walk. In the maze, you can move one step at a time in the following four directions: up, down, right, left — no “diagonal” moves are allowed. A move can be made only to a location in the array that contains a whitespace.! See image.

If there is an exit the program finds way out and displays the solution as described below. See Figure_2 and Figure_3.! See image. See image.

If there is no way out of the maze, the program should report that there is no solution.

The implementation requirements

A maze should be implemented as a 2-dimensional square (n✕n) array of characters. The only allowed characters in the array are:!

  • '#' — denote walls of the maze;!
  • ' ' — denote unvisited locations in the maze;!
  • 'x' — denote visited locations, that are not yet "dead ends";!
  • 'd' — "dead ends", i.e. locations from which you cannot proceed further and should return back.!

Initially the array(maze) contains only '#'s and ' 's.

You will need to define a Location class to represent locations in the maze and a Stack< Location > class to store visited locations.

To solve a maze you need to implement the following (recursive) algorithm:

  • (a)Start from some initial location in the maze that contains a whitespace, i.e. push it on the stack. Proceed to (b).!
  • (b)If the top location on the stack contains a whitespace, override it by 'x'. !
    • if this location is an exit proceed to (e).!
    • else proceed to (c).
  • (c)Try one by one locations adjacent to the top location on the stack. (up, down, left, right).!
    • push on stack the first one that contains a whitespace. Proceed to (b).
    • else, if none of the adjacent locations contain a whitespace, override the top location's character by 'd' and pop the stack. !
    • if the stack is empty proceed to (d)
    • else proceed to (c).
  • (d) Print "There is no solution", then exit.!
  • (e) Print the found solution in a nice format like the one on Figure_3, then exit. Note, that the solution path is contained in the stack.!

The main function

In the main function you have to test your program against two different mazes:

  • The one from Figure_2 (with the specified initial position). Please note, that your program may output a different solution.
  • Design a maze n✕n, n > 10, and solve it.!
Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.