import collections
import copy
def slidingPuzzle(board):
    """
    :type board: List[List[int]]
    :rtype: int
    """
    q = collections.deque()
    q.append(([board], 0, [(i, j) for i in range(len(board)) for j in range(len(board[0])) if board[i][j] == 0][0]))


    #newp is a list of boards, the path
    #newp2 is the new path
    seen = set()
    while q:
        newp, d, zero = q.popleft()
        new = newp[-1]
        if tuple(new[0] + new[1]) in seen:
            continue
        seen.add(tuple(new[0] + new[1]))
        if new == [[1, 2, 3], [4, 5, 6], [7,8,0]]:
            return newp
        for i in range(len(new)):
            for j in range(len(new[0])):
                if (abs(i - zero[0]) == 1 and abs(j - zero[1]) == 0) or (
                        abs(i - zero[0]) == 0 and abs(j - zero[1]) == 1):
                    new2 = copy.deepcopy(new)
                    new2[i][j], new2[zero[0]][zero[1]] = 0, new[i][j]
                    newp2 = newp.copy()
                    newp2.append(new2)
                    q.append((newp2, d + 1, (i, j)))
    return -1

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