import collections
wall,clear,goal = 0, 1, 9

#PATH SHOULD BE [0, 0] , [0, 1] , [0, 2] , [1 , 2] 3 moves to get to 9

grid = ['100',
        '100',
        '191']
width, height = 3, 3


def bfs(grid, start):
        queue = collections.deque([[start]])
        seen = set([start])
        while queue:
                path = queue.popleft()
                x, y = path[-1]
                if grid[y][x] == goal:
                        return path
                for x2, y2 in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                        if 0 <= x2 < width and 0 <= y2 < height and grid[y2][x2] != wall and (x2, y2) not in seen:
                                queue.append(path + [(x2, y2)])
                                seen.add((x2, y2))
                                print("in 2nd loop", path)


path = bfs(grid, (0, 0))