from collections import deque
import copy

def zeroLocation(puzzle):
    for i in range(len(puzzle)):
        for j in range(len(puzzle[0])):
            if puzzle[i][j] == 0:
                return (i,j)

def neighbors(puzzle):
    X, Y = len(puzzle), len(puzzle[0])
    neighbors = []
    x_zero, y_zero = zeroLocation(puzzle)
    # print('zero:',zeroLocation(puzzle))
    for x,y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        x_new = x_zero + x
        y_new = y_zero + y
        if 0 <= x_new < X and 0 <= y_new < Y:
            # print(x_new, y_new)
            new_board = copy.deepcopy(puzzle)
            new_board[x_zero][y_zero], new_board[x_new][y_new] = new_board[x_new][y_new], new_board[x_zero][y_zero]
            neighbors.append(new_board)
    return neighbors

def slidingPuzzle(puzzle):
    queue = deque()
    queue.append((puzzle,[puzzle]))

    seen = []

    while queue:
        print(len(queue))
        current, path = queue.popleft()
        neighbs = neighbors(current)
        for p in path:
            if p in neighbs: neighbs.remove(p)
        for neighbor in neighbs:
            if neighbor not in seen:
                if neighbor == [[0,1,2],[3,4,5],[6,7,8]]:
                    # print("FOUND",path + [neighbor])
                    print("MOVES",len(path))
                    exit()
                else:
                    queue.append((neighbor, path+[neighbor]))
        for x in neighbs: seen.append(x)

slidingPuzzle([[1,2,0],[3,4,5],[6,7,8]])