The Iterative Maze Problem

I had posted about a recursive maze solver earlier. This is an iterative solution to that problem.

maze = [
    ['S','0','0','0'],
    ['0','1','0','0'],
    ['0','1','0','0'],
    ['0','1','0','G'],
]

class MazeSolver:
    def __init__(self, maze, verbose=False):
        self.maze = maze
        self.nrows = len(maze)
        self.ncols = len(maze[0])
        self.visited = set([])
        self.verbose = verbose
    def _invalid(self, loc):
        if loc[0] < 0 or loc[1] < 0:
            return False
        elif loc[0] > self.nrows-1 or loc[1] > self.ncols-1:
            return False
        elif self.maze[loc[0]][loc[1]] in ['1']:
            return False
        elif loc in self.visited:
            return False
        else:
            return True
    def neighbors(self, loc):
        x, y = loc
        candidates = [(x-1,y), (x+1,y), (x,y-1), (x,y+1)]
        nbhd = list(filter(self._invalid, candidates))
        return set(nbhd)
    def run(self, loc):
        self.visited.add(loc)
        nbhd = self.neighbors(loc)
        step = 0
        if self.verbose:
            print("{}: {} -- {} -- {}".format(step, loc, nbhd, self.visited))
        while True:
            step += 1
            if len(nbhd) > 0:
                visit = nbhd.pop()
                # add visit to visited
                self.visited.add(visit)
                # you win
                if self.maze[visit[0]][visit[1]] == 'G':
                    if self.verbose:
                        print("{}: {}".format(step, visit))
                    break
                # add unvisited neighbors
                nbhd |= self.neighbors(visit)
                if self.verbose:
                    print("{}: {} -- {} -- {}".format(step, visit, nbhd, self.visited))
            else:
                break

Leave a Reply

Your email address will not be published. Required fields are marked *