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