Im trying to create a python program capable of solving a maze. I need it to be able to solve a maze that is any number of rows in height and any number of columns in width. I need the maze itself to be brought in as input from a file and I need it to be validated to ensure it contains a starting point. Once verified I need the maze to be solved iteratively showing each step. The maze will consist of '#' signs for walls the letter 'S' for the start and the letter 'E' for the end. I am having a lot of difficulty with this and any help would be appreciated. Right now I dont even know how to find the starting point of the maze. Heres what I have so far:

def main():
    maze=raw_input("Enter the name of the maze file: ")
    mazefile = open(maze,"r")
    pythonmaze =
    print pythonmaze
def start(m):
    for s in range(0,len(m)): ##Finds the start point.
        if m[s] =="S":
            x = s
    return x

I know what I want to code but cant figure out how to code it. I believe that I need to have a function that looks to find the start of the maze. Then I think I need a function that checks north, east, south, and west to see if there is a space there and moves to the space if there is one. Then I believe I need to have a function that backtracks if it comes to a dead end in order to find the correct path to the end. Ive really been struggling with writing code in order to accomplish this and I hope someone can help me out!

Hello Dmc!

First, there are bugs and small mistakes in your code.
mazefile.close is not a function call, so it does not close the file. It makes no problem because the file is automatically closed at python exit.
Correctly: mazefile.close()
You do not initialize the x variable in start function. That means your code crashes if you do not find the starting point. The other miniscule problem is, that you do not exit the loop when you find it.
Another problem with it, that you give back the character 'S' if found. What information you expect from that?

Correctly, without changing the original meaning:

def start(m):
    for s in range(0,len(m)): ##Finds the start point.
        if m[s] =="S":
            x = s
    if not x: raise Exception() #or whatever way you choose to indicate invalid map
    return x

The range function begins at 0 at default. No need to indicate it.

Second, some additions for the design. You write, you know what to code. Why not write it down? If you are familiar with OO design in some degree, then:

The maze has the following data attributes:

  • Columns, integer
  • Rows, integer
  • Starting point, integer
  • Ending point, integer

The maze will have the following methods:

  • create from file or string
  • validate input
  • find starting point
  • find ending point
  • find route
  • print the maze

One of the main points of OO design, that we have all the data attributes that are needed for the methods.

For solving the maze I recommend A* algo. You can try to figure out another one.

Third, do not begin writing code, unless you know what you will do in terms of design objects. I think you should write down the detailed requirements, and what objects, methods, attributes, function will do, what they take as an argument, what they make with it, what exception they raise so on.

A not detailed requirement list looks like:

  • This is a program capable of solving a maze.
  • The maze consists of walls, corridors, a starting and an ending point.
  • The maze is inputed as file.
  • The program finds the minimal route from starting point to the end point.
  • The program prints out the route.

Now the design will expand the terms used in requirements.

  • Description of the maze object(see my comment), the file, the output of the program. In my design the term corridor disapeared!
  • Description of the main program flow
  • Description of the of the actions taken

After that is the point, where writing code begins.

Maybe that sounds like a bunch of words written instead of real work, or you might think I am a teacher:)
Believe me, I am speaking from several years of work experiment. There are no little programs. If you cannot set requirements for yourself, how can you expect it from an enduser or a product manager? If you can't set an architecture and design for yourself, how can you expect it from an architect?
In fact there are little programs in reality. They tend to be thrown away and remembered as a messed up garbage. They solved something at some time. Thats all.

This article has been dead for over six months. Start a new discussion instead.