Recursion - Python

Question

I have made the following code in Python which opens the following text file. The first line is the size of the maze file, the second line is the starting point though on the maze it is actually at row 9, column 1 and the third line is the ending point though on the maze it is actually at row 1, column 19.

5  10
1  1
5  10
---------------------
|             | |   |
|-+-+-+ +-+-+ + + +-|
|   |   |   | |     |
| +-+-+ + +-+-+-+ + |
|       | | |     | |
|-+-+ + + + +-+ +-+-|
|     |             |
|-+ +-+-+-+-+-+ +-+ |
|     |         |   |
---------------------

Most of the functions work just fine and do what they are supposed to do. What I am having trouble with is solving the maze. The way my maze_solution function is set up right now fills up the whole maze with asterisks, I would like only the path to be drawn with asterisks and I am not sure how to do so.

class Maze: 
     def __init__(self, file):
         self.file = file
         self.maze = []
         data = self.file.readlines()

         data.pop(0)
         data.pop(0)        
         data.pop(0)

         for line in data:
             if line[-1] == '\n':
                 self.maze.append(list(line[:-1]))  
             else:
                 self.maze.append(list(line))            

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

    def maze_points(self):   
        for item in self.maze:
            rows = len(self.maze)
            columns = len(item)

        self.start = (rows - 2, 1)
        self.end = (1, columns - 2)

    def maze_solution(self, row, col):
        if row == self.end[0] and col == self.end[1]:
            self.maze[row][col] = '*'
            return True

         elif self.maze[row][col] == ' ':
             self.maze[row][col] = '*'

             if self.maze_solution(row, col + 1) or \
                self.maze_solution(row + 1, col) or \ 
                self.maze_solution(row, col - 1) or \
                self.maze_solution(row - 1, col):   
                self.maze[row][col] = ' '
                return False
             return True            

        elif self.maze[row][col] in '-|+':
            return False       

def maze_file():
    file = open('maze.txt', 'r')
    maze = Maze(file)
    maze.maze_points()
    row = maze.start[0]
    col = maze.start[1]              
    maze.maze_solution(row, col) 
    maze.print_maze()

Answer 1

You are almost there!

My suggestion is to keep the path in a separate list for each branch:

def maze_solution(self, row, col, path):
    # Arrived?
    if (row, col) == (self.end[0], self.end[1]):
        return path

    # Wall or been here before?
    if (self.maze[row][col] != " " or (row, col) in path[:-1]):
        return

    for nrow, ncol in [(row, col+1), (row, col-1),
                       (row+1, col), (row-1, col)]:
        sol = self.maze_solution(nrow, ncol, path + [(nrow, ncol)])
        if sol is not None:
            return sol

If you don't break immediately after finding a solution, you can do things like choosing the shortest one. To print it:

def print_maze(self, path):
    for i in range(len(self.maze)):
        for j in range(len(self.maze[0])):
            print("*" if (i,j) in path else self.maze[i][j], end='')
        print()

This outputs:

---------------------
|             | |***|
|-+-+-+ +-+-+ + +*+-|
|   |   |   | |  *  |
| +-+-+ + +-+-+-+*+ |
|    ***| | |  ***| |
|-+-+*+*+ + +-+*+-+-|
|  ***|*********    |
|-+*+-+-+-+-+-+ +-+ |
|***  |         |   |
---------------------

Answer 2

You only need to introduce a separate character for indicating a third state for a square:

•  (space) = not visited before
• * = visited, and on the solution's path
• . = visited, but it is not confirmed to be on the solution's path

There is also a mistake where you return True instead of False and vice versa.

Here is how the solution function needs to be adapted. Comments appear to indicate the three lines that need to be changed in your code:

def maze_solution(self, row, col):
    if row == self.end[0] and col == self.end[1]:
        self.maze[row][col] = '*'
        return True

    elif self.maze[row][col] == ' ': 
        self.maze[row][col] = '.' # New status: "trying"

        if self.maze_solution(row, col + 1) or \
            self.maze_solution(row + 1, col) or \
            self.maze_solution(row, col - 1) or \
            self.maze_solution(row - 1, col):   
            self.maze[row][col] = '*'
            return True # Indicate success (not failure)
        return False # Indicate failure (not success)

    elif self.maze[row][col] in '-|+':
        return False       

Output:

---------------------
|             |.|***|
|-+-+-+ +-+-+ +.+*+-|
|   |   |   | |..*..|
| +-+-+ + +-+-+-+*+.|
|    ***| | |  ***|.|
|-+-+*+*+ + +-+*+-+-|
|  ***|*********....|
|-+*+-+-+-+-+-+.+-+.|
|***..|.........|...|
---------------------

If the dots in the output bother you, you could just add logic in the print function that prints dots as spaces:

def print_maze(self):
    for i in range(len(self.maze)):
        for j in range(len(self.maze[0])):  
            print(self.maze[i][j].replace(".", " "), end='')                         
        print()

But keeping the dots can be useful to see them when debugging.