#!/bin/python3

import math
import os
import random
import re
import sys



#
# Complete the 'movesToSolve' function below.
#
# The function is expected to return an INTEGER.
# The function accepts 2D_INTEGER_ARRAY puzzle as parameter.
#
from collections import deque
import copy

def zeroLocation(puzzle): # Helper function to return X,Y coordinates of 0 square
    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)
    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:
            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 movesToSolve(puzzle):
    # Write your code here
    nRows = len(puzzle)
    mRows = len(puzzle[0])
    solved = [[0 for x in range(nRows)] for y in range(mRows)]
    counter = 0 # Generate Solved Board to check for Goal
    for i in range(nRows):
        for j in range(mRows):
            solved[i][j] = counter
            counter += 1
    if puzzle == solved:
        return 0

    queue = deque()
    queue.append((puzzle,[puzzle]))
    seen = []

    while 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 == solved:
                    return(len(path)) # Number of Moves
                    exit()
                else:
                    queue.append((neighbor, path+[neighbor]))
        for x in neighbs: seen.append(x)
        return -1




if __name__ == '__main__':