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()

You need to keep track of the tiles you passed but had to pass again because you encountered a dead end. I'd probably keep a counter in stead of using the asterisk. — Gerard van Helden
– Gerard van Helden, Commented Feb 9, 2018 at 7:46

csl · Accepted Answer · 2018-02-09 09:15:31Z

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:

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

trincot · Accepted Answer · 2020-10-14 18:42:12Z

1

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.

edited Oct 14, 2020 at 18:42

answered Feb 9, 2018 at 8:51

trincot

357k38 gold badges282 silver badges338 bronze badges

2 Comments

DwightD Over a year ago

Hello! I know it's been two years but your solution helped me so much. Quick question though, how would I code that last part? I want to know how to do it without the dots but I can't seem to wrap my head around that. Thanks in advance!

trincot Over a year ago

That last part? Just iterate your matrix row by row, and replace all dots with spaces.

Collectives™ on Stack Overflow

Recursion - Python

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related