Recursively Solving a Maze
Due: Thurday, July 19th at 11:59PM


This programming assignment asks you to write a program, using recursion, that solves mazes. The mazes will be provided with simple text files and the programs output will be the correct path through the maze.

For simplicity, the program only needs to solve mazes with a single starting point and a single finishing point.

The Maze

A Maze is provided to your program via a plain text file. For example, the maze pictured below is described by the text file sampleMaze.txt:

To help you to focus on the recursion, we've provided you a funtion that can read the maze into a "2D list" list-of-lists. You are welcome to use it -- or to write your own. The file contains our function and a few lines of code showing you how to use it.

For simplicity, the maze cannot have loops of any kind.

The Maze Solver

The really interesting part of this assignment is the mazeSolver function. The mazeSolver() function should accept a maze (list of lists) as an input and return True if the maze is solvable, and False otherwise.

It should also record the solution to the maze. It should do this by pushing the current position within the maze as it unwinds from a correct solution. To "push" onto a stack in Python, you can use the append() method. (Python has a pop(), but uses append() for push). This works because, as you unwind, you'll b e following the path backward. When you push it onto the list, using the list as a stack, you'll be reversing it, making the final order from start-to-finish.

You'll want to think about what to push onto the stack for each step along the solution path. We suggest keeping it simple and just creating the string "(row,col)", e.g. "(5,4)" and pushing that.

To achieve this, you want your mazeSolver() to take an initialized list as an argument. It is left empty if no solution is found (return False case), but is built up from finish-to-start during the unwinding phase if a solution is found (return True case).

So, using your mazeSolver() might look like this:

  mazeFile = "sampleMaze.txt"

  maze = []
  mazeSolution = []
  readMaze(m, mazeFile)
  if (solveMaze(maze, mazeSolution)):
    print mazeSolution
    print "No solution found."

Please note that mazeSolver() should only consider cells to be adjacent if they are in the same column or in the same row -- but not diagnal.