from collections import deque

def get_new_state(index1, index2, current_state):
    if current_state[index1] == "0" or current_state[index2] == "0":
        current_state = list(current_state)
        current_state[index1], current_state[index2] = current_state[index2], current_state[index1]
        return "".join(current_state)
    return None

def sliding_puzzle(board):
    """
    :type board: List[List[int]]
    :rtype: int
    """
    min_step = 1 << 31
    # need to convert board to a string so that we can add it as a state in the set
    # construct the graph based on the positions of the next place it can swap
    graph = {0:[1, 3], 1:[0, 2, 4], 2:[1, 5], 3:[0, 4], 4:[1, 3, 5], 5:[2, 4]}

    # convert init board to an initial state
    init_state = [] + board[0] + board[1]
    init_state = "".join(str(_) for _ in init_state)

    visited = {init_state}
    queue = deque([[init_state, 0]])
    while queue:
        top = queue.popleft()
        current_state, step = top

        # check results
        if current_state == "123450":
             min_step = min(min_step, step)

        for index1 in graph:
            for index2 in graph[index1]:
                new_state = self.get_new_state(index1, index2, current_state)
                if new_state is not None and new_state not in visited:
                    queue.append([new_state, step + 1])
                    visited.add(new_state)
    if min_step == 1<< 31:
        return -1
    return min_step

#print(sliding_puzzle([[1,2,3],[4,0,5]]))

>>> 1

#Explanation: Swap the 0 and the 5 in one move.

#print(sliding_puzzle([[1,2,3],[5,4,0]]))

>>> -1

#Explanation: No number of moves will make the board solved.

#print(sliding_puzzle([[4,1,2],[5,0,3]]))

>>> 5

#Explanation: 5 is the smallest number of moves that solves the board.

#An example path -
#After move 0: [[4,1,2],[5,0,3]]
#After move 1: [[4,1,2],[0,5,3]]
#After move 2: [[0,1,2],[4,5,3]]
#After move 3: [[1,0,2],[4,5,3]]
#After move 4: [[1,2,0],[4,5,3]]
#After move 5: [[1,2,3],[4,5,0]]

#print(sliding_puzzle([[3,2,4],[1,5,0]]))

>>> 14

%timeit output.sliding_puzzle([[1,2,3],[4,0,5]])
3.24 ms ± 629 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit output.sliding_puzzle([[1,2,3],[5,4,0]])
3.17 ms ± 633 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit output.sliding_puzzle([[4,1,2],[5,0,3]])
3.32 ms ± 719 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit output.sliding_puzzle([[3,2,4],[1,5,0]])
2.75 ms ± 131 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)