python maze using recursion

Question

I want to solve a maze using recursion. The program opens a text file like this one:

10 20
1 1 
10 20
-----------------------------------------
|     |     | |     | | |       |     | |
|-+ +-+-+ +-+ + +-+ + + +-+-+ +-+-+ + + |
|         |       |     | | | |   | |   |
| + +-+ + + +-+-+-+ + + + + + +-+ + + + |
| | |   |     |     | |     |       | | |
| +-+-+-+-+ +-+ +-+-+-+-+ +-+ + +-+-+ +-|
| | | |       |   | |         | |   |   |
| + + +-+ +-+-+ + + + +-+ +-+ + + + +-+ |
|     |     |   | |     | |   |   | | | |
|-+-+ +-+-+-+-+-+-+-+ +-+ +-+-+ +-+-+ +-|
| |   |   |     |     |     |   | | | | |
| +-+-+ +-+-+ +-+ + +-+-+ +-+ +-+ + + + |
|       |     | | |   |   | | | |       |
|-+ +-+ + + +-+ +-+-+ + +-+ + + +-+ +-+ |
|   | | | |     | | | | | | | |   | | | |
|-+ + +-+ + + + + + +-+ + + + + +-+-+ + |
|       | | | |     |     |             |
| + + +-+ + +-+-+-+ + +-+ + + +-+-+ +-+ |
| | |     | |           | | | |     |   |
-----------------------------------------

The first line of the file is the size of the maze(10 20), the second line is the starting point(1 1), and the third line is the exit(10, 20). I want to mark the correct path with "*". This is what my code looks like:

EDIT: I change some of the code in the findpath() funtion, and now I dont get any errors but the maze is empty, the path('*') is not 'drawn' on the maze.

class maze():    
    def __init__(self, file):

        self.maze_list = []

        data= file.readlines()

        size = data.pop(0).split()  # size of maze

        start = data.pop(0).split() # starting row and column; keeps being 0 because the previous not there anymore
        self.start_i = start[0]  # starting row
        self.start_j = start[1]  # starting column

        exit = data.pop(0).split()   # exit row and column 
        self.end_i = exit[0]
        self.end_j = exit[1]

        for i in data:  
            self.maze_list.append(list(i[:-1])) # removes \n character off of each list of list
        print(self.maze_list) # debug


    def print_maze(self):

        for i in range(len(self.maze_list)):
            for j in range(len(self.maze_list[0])):  
                print(self.maze_list[i][j], end='')                         
            print()

def main():

    filename = input('Please enter a file name to be processed: ') # prompt user for a file


    try:
        file = open(filename, 'r')
    except:                     # if a non-existing file is atempted to open, returns error 
        print("File Does Not Exist")
        return  

    mazeObject = maze(file)
    mazeObject.print_maze() # prints maze

    row = int(mazeObject.start_i)
    col = int(mazeObject.start_j)   

    findpath(row, col, mazeObject)  # finds solution route of maze if any

def findpath(row, col, mazeObject):

    if row == mazeObject.end_i and col == mazeObject.end_j: # returns True if it has found the Exit of the maze
        mazeObject.maze_list[row][col] = ' ' # to delete wrong path
        return True

    elif mazeObject.maze_list[row][col] == "|": # returns False if it finds wall 
        return False

    elif mazeObject.maze_list[row][col] '-': # returns False if it finds a wall 
    return False

    elif mazeObject.maze_list[row][col] '+': # returns False if it finds a wall 
        return False    

    elif mazeObject.maze_list[row][col] '*': # returns False if the path has been visited
        return False

    mazeObject.maze_list[row][col] = '*'   # marks the path followed with an *   

    if ((findpath(row + 1, col, mazeObject)) 
        or (findpath(row, col - 1, mazeObject)) 
        or (findpath(row - 1, col, mazeObject)) 
        or (findpath(row, col + 1, mazeObject))):    # recursion method
        mazeObject.maze_list[row][col] = ' '  # to delete wrong path
        return True
    return False    

So now my question is, where is the error? I mean the program just prints out the maze without the solution. I want to fill the correct path with "*".

Answer 1

Looking at your code I see several errors. You do not handle the entry and exit row/column pairs correctly. (10,20) is correct for this maze, if you assume that every other row, and every other column, is a grid line. That is, if the | and - characters represent infinitely thin lines that have occasional breaks in them, much like traditional maze drawings.

You'll need to multiple/divide by two, and deal with the inevitable fencepost errors, in order to correctly translate your file parameters into array row/column values.

Next, your findpath function is confused:

First, it should be a method of the class. It accesses internal data, and contains "inner knowledge" about the class details. Make it a method!

Second, your exit condition replaces the current character with a space "to delete wrong path". But if you have found the exit, the path is by definition correct. Don't do that!

Third, you have a bunch of if statements for various character types. That is fine, but please replace them with a single if statement using

if self.maze_list[row][col] in '|-+*':
    return False

Fourth, you wait to mark the current cell with a '*' until after your checks. But you should mark the cell before you declare victory when you reach the exit location. Move the exit test down, I think.

That should clean things up nicely.

Fifth, and finally, your recursive test is backwards. Your code returns True when it reached the exit location. Your code returns False when it runs into a wall, or tries to cross its own path. Therefore, if the code takes a dead end path, it will reach the end, return false, unroll the recursion a few times, returning false all along, until it gets back.

Thus, if you EVER see a True return, you know the code found the exit down that path. You want to immediately return true and do nothing else. Certainly don't erase the path - it leads to the exit!

On the other hand, if none of your possible directions return true, then you have found a dead end - the exit does not lie in this direction. You should erase your path, return False, and hope that the exit can be found at a higher level.