Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

8 Puzzle

  The goal of the 8 puzzle problem is to complete pieces on $3 \times 3$ cells where one of the cells is empty space. 

  In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 8 as shown below.

1 3 0
4 2 5
7 8 6

  You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).

1 2 3
4 5 6
7 8 0

  Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Input

  The $3 \times 3$ integers denoting the pieces or space are given.

Output

  Print the fewest steps in a line.

Constraints

There is a solution.

Sample Input 

1 3 0
4 2 5
7 8 6

Sample Output

4



Sample input:
1 3 0
4 2 5
7 8 6


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
queue = [[ini_state, zero_x, zero_y]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = set()
visited |= {hashnum(ini_state)}
trial = 0
while answer not in visited:
    new_queue = []
    trial += 1
    for q in queue:
        state, zero_x, zero_y = q
        for i in range(len(dx)):
            new_state = copy.deepcopy(state)
            new_x = zero_x + dx[i]
            new_y = zero_y + dy[i]
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                perm = hashnum(new_state)
                if perm == answer:
                    print(trial)
                    exit()
                if perm not in visited:
                    visited |= {perm}
                    new_queue.append([new_state, new_x, new_y])
    queue = new_queue
    
# print(trial)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(9):
        x_goal = i%3
        y_goal = i//3
        x_now = (node_list[i] - 1)%3
        y_now = (node_list[i] - 1)//3
        if y_now == -1:
            y_now = 2
        dx = abs(x_now - x_goal)
        dy = abs(y_now - y_goal)
        s += dx + dy
    return s

def moveNodeE(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 1] = node_tmp[space + 1], node_tmp[space]
    return node_tmp
def moveNodeW(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 1] = node_tmp[space - 1], node_tmp[space]
    return node_tmp
def moveNodeN(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 3] = node_tmp[space - 3], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 3] = node_tmp[space + 3], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, g):
        self.node = node_list
        self.space = node_list.index(0)
        self.g = g
        self.h = d_manhattan(node_list)
        self.f = self.g + self.h

    def makeBoard(self):
        space = self.space
        cost_now = self.f
        x_s = space%3
        y_s = space//3
        if x_s < 2:
            node_tmp = moveNodeE(self.node, space)
            yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s < 2:
            node_tmp = moveNodeS(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            yield board(node_tmp, self.g + 1)

b_open = []
n_close = []
n_goal = [1,2,3,4,5,6,7,8,0]
n_start = []

for i in range(3):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close.append(b_now.node)
    for b_new in b_now.makeBoard():
        if b_new.node in n_close:
            continue
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)

Submission status: Time Limit Exceeded

Solution code:
#codinh -utf8
import sys
import copy

goal_state=[1,2,3,4,5,6,7,8,0]
open_list=[]    #????????¢?´¢??????????????????????´?
closed_list=[]  #??¢?´¢????????????????????????????´?


def getH(a, b): #???????????????????????¢????¨????
    h2=0
    i=0
    for n in a:
        if n!=-1:   #????????\??????????????????????????????????????????????????¶????????§????????¢??????????±???????
            j=b.index(n)
            dist=j-i
            dist=abs(dist)  #|i??¨j??????dist|: ??´???????????§????????¢
            if dist==1:     #?????¢??????????????§?¨???????????????????????????????????????§????????¢?????????
                if (i==2 and j==3) or (j==2 and i==3) or (i==5 and j==6) or (j==5 and i==6):
                    dist=3
            elif dist==3:
                dist=1
            elif dist==4:
                if(i!=2 and j!=6) and (i!=6 and j!=2):
                    dist=2
            elif dist==5:
                dist=3
            elif dist==6:
                dist=2
            elif dist==7:
                dist=3
            elif dist==8:
                dist=4
            h2+=dist    #?????????????????¢?????????
        i+=1
    return  h2  #?????¢??????????????????

def findChildState(space, std_node):    #???????????????????????????????????????????????????
    nxt_space=[]    #????????????????????????????????????????????????????´?
    if space==0:    #?????????????????????????????????????????£?????´???
        nxt_space.append(space+1)
        nxt_space.append(space+3)
    elif space==1:    #???????????????????????????0??????????????????????????£?????´???
        nxt_space.append(space-1)
        nxt_space.append(space+1)
        nxt_space.append(space+3)
    elif space==2:    #?????????????????????????????????????????£?????´???
        nxt_space.append(space-1)
        nxt_space.append(space+3)
    elif space==3:    #??????????????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space+1)
        nxt_space.append(space+3)
    elif space==4:    #????????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space-1)
        nxt_space.append(space+1)
        nxt_space.append(space+3)
    elif space==5:    #??????????????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space-1)
        nxt_space.append(space+3)
    elif space==6:    #?????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space+1)
    elif space==7:    #????????????????????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space-1)
        nxt_space.append(space+1)
    elif space==8:    #?????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space-1)
    child_set=[]
    for i in nxt_space: #???????????????????????????????????????????????¶???child_state?????????
        child_state=copy.deepcopy(std_node[3])
        child_state[space], child_state[i]=child_state[i], child_state[space]
        child_set.append(child_state)   #chld_set??????????????????????????????????????????????????¶???????????????????´???????
    return child_set

def openChildNode(std_node):    #?????¶??????????????????????????????openlist????????????
    child_set=findChildState(std_node[3].index(0), std_node)   #???????????????????????????????????????
    del open_list[0]    #??????????????????openlist??????????????????
    closed_list.append(std_node)    #??????????????????closedlist???????????????
    for i in child_set:
        g=std_node[0]+1
        h=getH(i, goal_state)
        f=g+h
        child=(g,h,f,i) #?????????????????????????????°????????\??????????????£???????????????????????????????????¶???????¨???????child?????????
        op=list(map(lambda x: i==x[3], open_list))
        cl=list(map(lambda x: i==x[3], closed_list))
        if  (True not in op) and (True not in cl):  #openlist??????closedlist????????????????????¨?????????????????¶??????????????´???
            open_list.append(child) #openlist?????????
        elif (True in op):  #openlist?????????????????¨?????????????????¶??????????????´???
            n=op.index(True)
            if f<open_list[n][2]:   #????????????????????????????????????????????????????°????????????°openlist????????????????????´??°
                open_list[n]=copy.deepcopy(child)
        elif (True in cl):  #closedlist?????????????????¨?????????????????¶??????????????´???
            n=cl.index(True)
            if f<closed_list[n][2]:   #????????????????????????????????????????????????????°????????????°closedlist??????????????????openlist?????????
                del closed_list[n]
                open_list.append(child)

def updateStandard():   #openlist??????????????????????°???????????????????????????????????¨??????????
    min=100000000
    std=()
    if open_list==[]:   #openlist??????????????´?????¢?´¢??±???
        return -1
    for i in open_list: #openlist??????????????????????°????????????????????´¢
        if i[2]<min:
            min=i[2]
            std=copy.deepcopy(i)
    n=open_list.index(std)  #????????????????°???????????????????????????????????¨????
    open_list[0], open_list[n]=open_list[n], open_list[0]   #??????????????????openlist?????????????§????
    return std  #????????????????????????


a=[]
for i in sys.stdin:
    x=list(map(int, i.split()))
    for j in x:
        a.append(j)

g=0     #??????????????§?????????????????°???0
h=getH(a, goal_state)  #?????\??????????????£?????????????¨????
f=g+h   #??´???????????§????¨±???????????????????¨????
std_node=(g, h, f, a)   #?????????(??????????????°????????\??????????????£??????????????????????????????????????¶???)??????????????????????¨????
open_list.append(std_node)

while 1:
    openChildNode(std_node) #open_list????????????????????????
    std=updateStandard()    #openlist?????????????????????f???????°???????????????????
    if std==-1: #openlist???????????£?????´?????¢?´¢??±???
        flag="Failed"
        break
    std_node=copy.deepcopy(std)    #?????????????????????????????????????°????????????????????????????????¨????
    if std_node[3]==goal_state: #????????????????????????????????´???????????¶?????¨?????´????????°??¢?´¢??????
        flag="Done"
        break

if flag=="Done":    #??¢?´¢?????????????????´????????´???????????§???????????????????????°??¨????????¶????????¨???
    print(std_node[0])
elif flag=="Failed":    #??¢?´¢?????±???????????´???????????¨?????????
    print("Search failed")

Submission status: Time Limit Exceeded

Solution code:
#codinh -utf8
import sys
import copy

goal_state=[1,2,3,4,5,6,7,8,0]
open_list=[]    #????????¢?´¢??????????????????????´?
closed_list=[]  #??¢?´¢????????????????????????????´?


def getH(a, b): #???????????????????????¢????¨????
    h2=0
    i=0
    for n in a:
        if n!=-1:   #????????\??????????????????????????????????????????????????¶????????§????????¢??????????±???????
            j=b.index(n)
            dist=j-i
            dist=abs(dist)  #|i??¨j??????dist|: ??´???????????§????????¢
            if dist==1:     #?????¢??????????????§?¨???????????????????????????????????????§????????¢?????????
                if (i==2 and j==3) or (j==2 and i==3) or (i==5 and j==6) or (j==5 and i==6):
                    dist=3
            elif dist==3:
                dist=1
            elif dist==4:
                if(i!=2 and j!=6) and (i!=6 and j!=2):
                    dist=2
            elif dist==5:
                dist=3
            elif dist==6:
                dist=2
            elif dist==7:
                dist=3
            elif dist==8:
                dist=4
            h2+=dist    #?????????????????¢?????????
        i+=1
    return  h2  #?????¢??????????????????

def findChildState(space, std_node):    #???????????????????????????????????????????????????
    nxt_space=[]    #????????????????????????????????????????????????????´?
    if space==0:    #?????????????????????????????????????????£?????´???
        nxt_space.append(space+1)
        nxt_space.append(space+3)
    elif space==1:    #???????????????????????????0??????????????????????????£?????´???
        nxt_space.append(space-1)
        nxt_space.append(space+1)
        nxt_space.append(space+3)
    elif space==2:    #?????????????????????????????????????????£?????´???
        nxt_space.append(space-1)
        nxt_space.append(space+3)
    elif space==3:    #??????????????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space+1)
        nxt_space.append(space+3)
    elif space==4:    #????????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space-1)
        nxt_space.append(space+1)
        nxt_space.append(space+3)
    elif space==5:    #??????????????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space-1)
        nxt_space.append(space+3)
    elif space==6:    #?????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space+1)
    elif space==7:    #????????????????????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space-1)
        nxt_space.append(space+1)
    elif space==8:    #?????????????????????????????????????????£?????´???
        nxt_space.append(space-3)
        nxt_space.append(space-1)
    child_set=[]
    for i in nxt_space: #???????????????????????????????????????????????¶???child_state?????????
        child_state=copy.deepcopy(std_node[3])
        child_state[space], child_state[i]=child_state[i], child_state[space]
        child_set.append(child_state)   #chld_set??????????????????????????????????????????????????¶???????????????????´???????
    return child_set

def openChildNode(std_node):    #?????¶??????????????????????????????openlist????????????
    child_set=findChildState(std_node[3].index(0), std_node)   #???????????????????????????????????????
    del open_list[0]    #??????????????????openlist??????????????????
    closed_list.append(std_node)    #??????????????????closedlist???????????????
    for i in child_set:
        g=std_node[0]+1
        h=getH(i, goal_state)
        f=g+h
        child=(g,h,f,i) #?????????????????????????????°????????\??????????????£???????????????????????????????????¶???????¨???????child?????????
        op=list(map(lambda x: i==x[3], open_list))
        cl=list(map(lambda x: i==x[3], closed_list))
        if  (True not in op) and (True not in cl):  #openlist??????closedlist????????????????????¨?????????????????¶??????????????´???
            open_list.append(child) #openlist?????????
        elif (True in op):  #openlist?????????????????¨?????????????????¶??????????????´???
            n=op.index(True)
            if f<open_list[n][2]:   #????????????????????????????????????????????????????°????????????°openlist????????????????????´??°
                open_list[n]=copy.deepcopy(child)
        elif (True in cl):  #closedlist?????????????????¨?????????????????¶??????????????´???
            n=cl.index(True)
            if f<closed_list[n][2]:   #????????????????????????????????????????????????????°????????????°closedlist??????????????????openlist?????????
                del closed_list[n]
                open_list.append(child)

def updateStandard():   #openlist??????????????????????°???????????????????????????????????¨??????????
    min=100000000
    std=()
    if open_list==[]:   #openlist??????????????´?????¢?´¢??±???
        return -1
    for i in open_list: #openlist??????????????????????°????????????????????´¢
        if i[2]<min:
            min=i[2]
            std=copy.deepcopy(i)
    n=open_list.index(std)  #????????????????°???????????????????????????????????¨????
    open_list[0], open_list[n]=open_list[n], open_list[0]   #??????????????????openlist?????????????§????
    return std  #????????????????????????


a=[]
for i in sys.stdin:
    x=list(map(int, i.split()))
    for j in x:
        a.append(j)

g=0     #??????????????§?????????????????°???0
h=getH(a, goal_state)  #?????\??????????????£?????????????¨????
f=g+h   #??´???????????§????¨±???????????????????¨????
std_node=(g, h, f, a)   #?????????(??????????????°????????\??????????????£??????????????????????????????????????¶???)??????????????????????¨????
open_list.append(std_node)

while 1:
    if std_node[3]==goal_state: #????????????????????????????????´???????????¶?????¨?????´????????°??¢?´¢??????
        flag="Done"
        break
    openChildNode(std_node) #open_list????????????????????????
    std=updateStandard()    #openlist?????????????????????f???????°???????????????????
    if std==-1: #openlist???????????£?????´?????¢?´¢??±???
        flag="Failed"
        break
    std_node=copy.deepcopy(std)    #?????????????????????????????????????°????????????????????????????????¨????


if flag=="Done":    #??¢?´¢?????????????????´????????´???????????§???????????????????????°??¨????????¶????????¨???
    print(std_node[0])
elif flag=="Failed":    #??¢?´¢?????±???????????´???????????¨?????????
    print("Search failed")

Submission status: Time Limit Exceeded

Solution code:
#codinh -utf8
import sys
import copy

goal_state=[1,2,3,4,5,6,7,8,0]
adj=[(1, 3),(0, 2, 4),(1, 5),(0, 4, 6),(1, 3, 5, 7),(2, 4, 8),(3, 7),(4, 6, 8),(5, 7)]
open_list=[]    #????????¢?´¢??????????????????????´?
closed_list=[]  #??¢?´¢????????????????????????????´?


def getH(a, b): #???????????????????????¢????¨????
    h2=0
    i=0
    for n in a:
        if n!=-1:   #????????\??????????????????????????????????????????????????¶????????§????????¢??????????±???????
            j=b.index(n)
            dist=j-i
            dist=abs(dist)  #|i??¨j??????dist|: ??´???????????§????????¢
            if dist==1:     #?????¢??????????????§?¨???????????????????????????????????????§????????¢?????????
                if (i==2 and j==3) or (j==2 and i==3) or (i==5 and j==6) or (j==5 and i==6):
                    dist=3
            elif dist==3:
                dist=1
            elif dist==4:
                if(i!=2 and j!=6) and (i!=6 and j!=2):
                    dist=2
            elif dist==5:
                dist=3
            elif dist==6:
                dist=2
            elif dist==7:
                dist=3
            elif dist==8:
                dist=4
            h2+=dist    #?????????????????¢?????????
        i+=1
    return  h2  #?????¢??????????????????

def findChildState(space, std_node):    #???????????????????????????????????????????????????
    ad=adj[space]
    child_set=[]
    for i in ad: #???????????????????????????????????????????????¶???child_state?????????
        child_state=copy.deepcopy(std_node[3])
        child_state[space], child_state[i]=child_state[i], child_state[space]
        child_set.append(child_state)   #chld_set??????????????????????????????????????????????????¶???????????????????´???????
    return child_set

def openChildNode(std_node):    #?????¶??????????????????????????????openlist????????????
    child_set=findChildState(std_node[3].index(0), std_node)   #???????????????????????????????????????
    del open_list[0]    #??????????????????openlist??????????????????
    closed_list.append(std_node)    #??????????????????closedlist???????????????
    for i in child_set:
        g=std_node[0]+1
        h=getH(i, goal_state)
        f=g+h
        child=(g,h,f,i) #?????????????????????????????°????????\??????????????£???????????????????????????????????¶???????¨???????child?????????
        op=list(map(lambda x: i==x[3], open_list))
        cl=list(map(lambda x: i==x[3], closed_list))
        if  (True not in op) and (True not in cl):  #openlist??????closedlist????????????????????¨?????????????????¶??????????????´???
            open_list.append(child) #openlist?????????
        elif (True in op):  #openlist?????????????????¨?????????????????¶??????????????´???
            n=op.index(True)
            if f<open_list[n][2]:   #????????????????????????????????????????????????????°????????????°openlist????????????????????´??°
                open_list[n]=copy.deepcopy(child)
        elif (True in cl):  #closedlist?????????????????¨?????????????????¶??????????????´???
            n=cl.index(True)
            if f<closed_list[n][2]:   #????????????????????????????????????????????????????°????????????°closedlist??????????????????openlist?????????
                del closed_list[n]
                open_list.append(child)

def updateStandard():   #openlist??????????????????????°???????????????????????????????????¨??????????
    min=100000000
    std=()
    if open_list==[]:   #openlist??????????????´?????¢?´¢??±???
        return -1
    for i in open_list: #openlist??????????????????????°????????????????????´¢
        if i[2]<min:
            min=i[2]
            std=copy.deepcopy(i)
    n=open_list.index(std)  #????????????????°???????????????????????????????????¨????
    open_list[0], open_list[n]=open_list[n], open_list[0]   #??????????????????openlist?????????????§????
    return std  #????????????????????????


a=list(map(int, sys.stdin.read().split()))
g=0     #??????????????§?????????????????°???0
h=getH(a, goal_state)  #?????\??????????????£?????????????¨????
f=g+h   #??´???????????§????¨±???????????????????¨????
std_node=(g, h, f, a)   #?????????(??????????????°????????\??????????????£??????????????????????????????????????¶???)??????????????????????¨????
open_list.append(std_node)

while 1:
    if std_node[3]==goal_state: #????????????????????????????????´???????????¶?????¨?????´????????°??¢?´¢??????
        flag="Done"
        break
    openChildNode(std_node) #open_list????????????????????????
    std=updateStandard()    #openlist?????????????????????f???????°??????????????????????????????¨??????
    if std==-1: #openlist???????????£?????´?????¢?´¢??±???
        flag="Failed"
        break
    std_node=copy.deepcopy(std)    #?????????????????????????????????????°????????????????????????????????¨????


if flag=="Done":    #??¢?´¢?????????????????´????????´???????????§???????????????????????°??¨????????¶????????¨???
    print(std_node[0])
elif flag=="Failed":    #??¢?´¢?????±???????????´???????????¨?????????
    print("Search failed")

Submission status: Time Limit Exceeded

Solution code:
import copy
import functools as ft
N = 3


def solved(game):
    for i in range(N):
        for j in range(N):
            if (game[i][j] - 1) != i * N + j and game[i][j] != 0:
                return False
    return True

def debug_game(game):
    for i in range(N):
        print(ft.reduce(lambda x,y: x + str(y) + " ", game[i], ""))

def convert_code(game):
    hash_code = ""
    for i in range(N):
        hash_code = hash_code + ft.reduce(lambda x,y: x + str(y), game[i], "")
    return hash_code

def calc_cost(game):
    cost = 0
    for i in range(N):
        for j in range(N):
            if game[i][j] != 0:
                ideal = (int((game[i][j] - 1) / N), (game[i][j] - 1) % N)
                cost += abs(i - ideal[0]) + abs(j - ideal[1])

    return cost

games = []
closed = []
init = [[] for i in range(N)]

for i in range(N):
    init[i] = [int(item) for item in input().split()]
    for j in range(N):
        if init[i][j] == 0:
            #queue.put((i, j))
            zero = (i, j)

games = games + [(init, zero, calc_cost(init), 0)]
direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]

while len(games) > 0:
    current = games.pop(0)
    zero = current[1]
    #print("Depth: "+str(current[3]) + " Cost: "+str(current[2]))
    #debug_game(current[0])
    closed = closed + [convert_code(current[0])]

    if solved(current[0]):
        print(current[3])
        break

    for d in direction :
        next_step = (zero[0] + d[0], zero[1] + d[1])
        if next_step[0] >= 0 and next_step[0] <= 2 and next_step[1] >= 0 and next_step[1] <= 2:

            tmp = copy.deepcopy(current[0])
            tmp[zero[0]][zero[1]], tmp[next_step[0]][next_step[1]] = tmp[next_step[0]][next_step[1]], tmp[zero[0]][zero[1]]
            tmp_cost = calc_cost(tmp)
            hash_code = convert_code(tmp)

            if not hash_code in closed:
                games = games + [(tmp, next_step, tmp_cost, current[3]+1)]

    games.sort(key=lambda x: x[2]+x[3])

Submission status: Time Limit Exceeded

Solution code:
import copy
import functools as ft
N = 3


def solved(game):
    for i in range(N):
        for j in range(N):
            if (game[i][j] - 1) != i * N + j and game[i][j] != 0:
                return False
    return True

def debug_game(game):
    for i in range(N):
        print(ft.reduce(lambda x,y: x + str(y) + " ", game[i], ""))

def convert_code(game):
    hash_code = ""
    for i in range(N):
        hash_code = hash_code + ft.reduce(lambda x,y: x + str(y), game[i], "")
    return hash_code

def calc_cost(game):
    cost = 0
    for i in range(N):
        for j in range(N):
            if game[i][j] != 0:
                ideal = (int((game[i][j] - 1) / N), (game[i][j] - 1) % N)
                cost += abs(i - ideal[0]) + abs(j - ideal[1])
            else:
                cost += abs(i - (N-1)) + abs(j - (N-1))

    return cost

games = []
closed = []
init = [[] for i in range(N)]

for i in range(N):
    init[i] = [int(item) for item in input().split()]
    for j in range(N):
        if init[i][j] == 0:
            #queue.put((i, j))
            zero = (i, j)

games = games + [(init, zero, calc_cost(init), 0)]
direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]

while len(games) > 0:
    current = games.pop(0)
    zero = current[1]
    #print("Depth: "+str(current[3]) + " Cost: "+str(current[2]))
    #debug_game(current[0])
    closed = closed + [convert_code(current[0])]

    if solved(current[0]):
        print(current[3])
        break

    for d in direction :
        next_step = (zero[0] + d[0], zero[1] + d[1])
        if next_step[0] >= 0 and next_step[0] <= 2 and next_step[1] >= 0 and next_step[1] <= 2:

            tmp = copy.deepcopy(current[0])
            tmp[zero[0]][zero[1]], tmp[next_step[0]][next_step[1]] = tmp[next_step[0]][next_step[1]], tmp[zero[0]][zero[1]]
            tmp_cost = calc_cost(tmp)
            hash_code = convert_code(tmp)
            if not hash_code in closed:
                #print(hash_code)
                games = games + [(tmp, next_step, tmp_cost, current[3]+1)]

    games.sort(key=lambda x: x[2] + x[3])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
f = lambda x: "\n".join(" ".join(map(str, x[i])) for i in range(3))
def MAIN():
    MAP = [list(map(int, input().split())) for _ in range(N)]
    goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    ans = 0
    dp = deque([[0, MAP]])
    LOG = [MAP]
    while dp:
        cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        y, x = divmod(sum(M, []).index(0), N)
        cnt += 1
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                CM = deepcopy(M)
                CM[y][x], CM[ny][nx] = CM[ny][nx], CM[y][x]
                if not CM in LOG:
                    dp.append([cnt, CM])
                    LOG.append(CM)
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
f = lambda x: "\n".join(" ".join(map(str, x[i])) for i in range(3))
def MAIN():
    MAP = [list(map(int, input().split())) for _ in range(N)]
    start = divmod(sum(MAP, []).index(0), N)
    goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    ans = 0
    dp = deque([[start[0], start[1], 0, MAP]])
    LOG = [MAP]
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                CM = deepcopy(M)
                CM[y][x], CM[ny][nx] = CM[ny][nx], CM[y][x]
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.append(CM)
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def MAIN():
    MAP = sum([input().split() for _ in range(N)], [])
    y0, x0 = divmod(MAP.index("0"), N)
    goal = ['1', '2', '3', '4', '5', '6', '7', '8', '0']
    ans = 0
    dp = deque([[y0, x0, 0, MAP]])
    LOG = [MAP]
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        yx = y * N + x
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                CM = deepcopy(M)
                nyx = ny * N + nx
                CM[yx], CM[nyx] = CM[nyx], CM[yx]
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.append(CM)
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def MAIN():
    MAP = tuple(sum([input().split() for _ in range(N)], []))
    y0, x0 = divmod(MAP.index("0"), N)
    goal = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    ans = 0
    dp = deque([[y0, x0, 0, MAP]])
    LOG = {MAP}
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        yx = y * N + x
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                CM = list(deepcopy(M))
                nyx = ny * N + nx
                CM[yx], CM[nyx] = CM[nyx], CM[yx]
                CM = tuple(CM)
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.add(CM)
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def MAIN():
    MAP = tuple(sum([input().split() for _ in range(N)], []))
    y0, x0 = divmod(MAP.index("0"), N)
    goal = ('1', '2', '3', '4', '5', '6', '7', '8', '0')
    ans = 0
    dp = deque([[y0, x0, 0, MAP]])
    LOG = {MAP}
    while dp:
        y, x, cnt, M = dp.popleft()
        cnt += 1
        yx = y * N + x
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                CM = list(deepcopy(M))
                nyx = ny * N + nx
                CM[yx], CM[nyx] = CM[nyx], CM[yx]
                CM = tuple(CM)
                if not CM in LOG:
                    if CM == goal:
                        print(cnt)
                        dp = []
                        break
                    dp.append([ny, nx, cnt, CM])
                    LOG.add(CM)
MAIN()