Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or c_depth > depth):
        return

    if(i != 0):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 2):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 2):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(8)]
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+simpleHS(c_puz)) > depth):
        return

    if(i != 0):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 2):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 2):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    if(c_puz[8] == 0):
        count+=1
    return count

def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(8)]
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+HS(c_puz)) > depth):
        return

    if(i != 0):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 2):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 2):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+HS(c_puz)) > depth):
        return

    if(i != 0):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 2):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 2):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = HS(puz)
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+HS(c_puz)) > depth):
        return

    if(i != 0):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
        if(finding == 1):
            return
    if(i != 2):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
        if(finding == 1):
            return
    if(j != 0):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
        if(finding == 1):
            return
    if(j != 2):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+HS(c_puz)) > depth or (c_depth+simpleHS(c_puz)) > depth):
        return

    if(i != 0):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 2):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 2):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+HS(c_puz)) > depth or (c_depth+simpleHS(c_puz)) > depth):
        return

    if(i != 0 and finding != 1):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 2 and finding != 1):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0 and finding != 1):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 2 and finding != 1):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        c_puz = items[3]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+simpleHS(c_puz)) > depth):
            continue

        if(_i != 0):
            heapq.heappush(q,(c_depth+1,_i-1,_j,swapPuz(c_puz[0:],_i,_j,_i-1,_j)))
        if(_i != 2):
            heapq.heappush(q,(c_depth+1,_i+1,_j,swapPuz(c_puz[0:],_i,_j,_i+1,_j)))
        if(_j != 0):
            heapq.heappush(q,(c_depth+1,_i,_j-1,swapPuz(c_puz[0:],_i,_j,_i,_j-1)))
        if(_j != 2):
            heapq.heappush(q,(c_depth+1,_i,_j+1,swapPuz(c_puz[0:],_i,_j,_i,_j+1)))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        c_puz = items[3]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+HS(c_puz)) > depth):
            continue

        if(_i != 0):
            heapq.heappush(q,(c_depth+1,_i-1,_j,swapPuz(c_puz[0:],_i,_j,_i-1,_j)))
        if(_i != 2):
            heapq.heappush(q,(c_depth+1,_i+1,_j,swapPuz(c_puz[0:],_i,_j,_i+1,_j)))
        if(_j != 0):
            heapq.heappush(q,(c_depth+1,_i,_j-1,swapPuz(c_puz[0:],_i,_j,_i,_j-1)))
        if(_j != 2):
            heapq.heappush(q,(c_depth+1,_i,_j+1,swapPuz(c_puz[0:],_i,_j,_i,_j+1)))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        c_puz = items[3]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+simpleHS(c_puz)) >= depth):
            continue

        if(_i != 0):
            heapq.heappush(q,(c_depth+1,_i-1,_j,swapPuz(c_puz[0:],_i,_j,_i-1,_j)))
        if(_i != 2):
            heapq.heappush(q,(c_depth+1,_i+1,_j,swapPuz(c_puz[0:],_i,_j,_i+1,_j)))
        if(_j != 0):
            heapq.heappush(q,(c_depth+1,_i,_j-1,swapPuz(c_puz[0:],_i,_j,_i,_j-1)))
        if(_j != 2):
            heapq.heappush(q,(c_depth+1,_i,_j+1,swapPuz(c_puz[0:],_i,_j,_i,_j+1)))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+simpleHS(c_puz)) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            heapq.heappush(q,(c_depth+1,_i-1,_j,2,swapPuz(c_puz[0:],_i,_j,_i-1,_j)))
        if(_i != 2 and prev_move != 2):
            heapq.heappush(q,(c_depth+1,_i+1,_j,1,swapPuz(c_puz[0:],_i,_j,_i+1,_j)))
        if(_j != 0 and prev_move != 3):
            heapq.heappush(q,(c_depth+1,_i,_j-1,4,swapPuz(c_puz[0:],_i,_j,_i,_j-1)))
        if(_j != 2 and prev_move != 4):
            heapq.heappush(q,(c_depth+1,_i,_j+1,3,swapPuz(c_puz[0:],_i,_j,_i,_j+1)))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i
        ki = (int)(k/3)
        kj = k - ki
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            heapq.heappush(q,(c_depth+1,_i-1,_j,2,swapPuz(c_puz[0:],_i,_j,_i-1,_j)))
        if(_i != 2 and prev_move != 2):
            heapq.heappush(q,(c_depth+1,_i+1,_j,1,swapPuz(c_puz[0:],_i,_j,_i+1,_j)))
        if(_j != 0 and prev_move != 3):
            heapq.heappush(q,(c_depth+1,_i,_j-1,4,swapPuz(c_puz[0:],_i,_j,_i,_j-1)))
        if(_j != 2 and prev_move != 4):
            heapq.heappush(q,(c_depth+1,_i,_j+1,3,swapPuz(c_puz[0:],_i,_j,_i,_j+1)))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/3)
        _j = i - _i*3
        ki = (int)(k/3)
        kj = k - ki*3
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*3+j]
    c_puz[i*3+j] = c_puz[i2*3+j2]
    c_puz[i2*3+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,0,puz,costs))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _costs = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+sumCost(_costs)) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i-1)*3+_j] = HS(_i-1,_j,swap_puz[(_i-1)*3+_j])
            heapq.heappush(q,(c_depth+1,_i-1,_j,2,swap_puz,swap_cost))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i+1)*3+_j] = HS(_i+1,_j,swap_puz[(_i+1)*3+_j])
            heapq.heappush(q,(c_depth+1,_i+1,_j,1,swap_puz,swap_cost))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j-1] = HS(_i,_j-1,swap_puz[_i*3+_j-1])
            heapq.heappush(q,(c_depth+1,_i,_j-1,4,swap_puz,swap_cost))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j+1] = HS(_i,_j+1,swap_puz[_i*3+_j+1])
            heapq.heappush(q,(c_depth+1,_i,_j+1,3,swap_puz,swap_cost))

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,0,puz,costs))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _costs = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+sumCost(_costs)) >= depth or (c_depth+simpleHS(c_puz) >= depth)):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i-1)*3+_j] = HS(_i-1,_j,swap_puz[(_i-1)*3+_j])
            heapq.heappush(q,(c_depth+1,_i-1,_j,2,swap_puz,swap_cost))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i+1)*3+_j] = HS(_i+1,_j,swap_puz[(_i+1)*3+_j])
            heapq.heappush(q,(c_depth+1,_i+1,_j,1,swap_puz,swap_cost))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j-1] = HS(_i,_j-1,swap_puz[_i*3+_j-1])
            heapq.heappush(q,(c_depth+1,_i,_j-1,4,swap_puz,swap_cost))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j+1] = HS(_i,_j+1,swap_puz[_i*3+_j+1])
            heapq.heappush(q,(c_depth+1,_i,_j+1,3,swap_puz,swap_cost))

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,0,puz,costs))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _costs = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+sumCost(_costs)) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i-1)*3+_j] = HS(_i-1,_j,swap_puz[(_i-1)*3+_j])
            if(not checkPuzIsExisted(swap_puz,q)):
                heapq.heappush(q,(c_depth+1,_i-1,_j,2,swap_puz,swap_cost))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i+1)*3+_j] = HS(_i+1,_j,swap_puz[(_i+1)*3+_j])
            if(not checkPuzIsExisted(swap_puz,q)):
                heapq.heappush(q,(c_depth+1,_i+1,_j,1,swap_puz,swap_cost))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j-1] = HS(_i,_j-1,swap_puz[_i*3+_j-1])
            if(not checkPuzIsExisted(swap_puz,q)):
                heapq.heappush(q,(c_depth+1,_i,_j-1,4,swap_puz,swap_cost))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j+1] = HS(_i,_j+1,swap_puz[_i*3+_j+1])
            if(not checkPuzIsExisted(swap_puz,q)):
                heapq.heappush(q,(c_depth+1,_i,_j+1,3,swap_puz,swap_cost))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+simpleHS(c_puz)) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            if(not checkPuzIsExisted(swap_puz,q)):
                heapq.heappush(q,(c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            if(not checkPuzIsExisted(swap_puz,q)):
                heapq.heappush(q,(c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            if(not checkPuzIsExisted(swap_puz,q)):
                heapq.heappush(q,(c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            if(not checkPuzIsExisted(swap_puz,q)):
                heapq.heappush(q,(c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+simpleHS(c_puz)) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Runtime Error):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(simpleHS(swap_puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+c_dWithH) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Runtime Error):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(simpleHS(swap_puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+c_dWithH) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(simpleHS(puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+c_dWithH) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append((simpleHS(puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = q.pop()
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break
        if((c_depth+c_dWithH) > depth):
            continue
            
        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append((simpleHS(puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = q.pop(0)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break
        if((c_depth+c_dWithH) > depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            q.append((c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            q.append((c_depth+1+simpleHS(swap_puz),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            q.append((c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            q.append((c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))


def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append((sumCost(costs),0,i,j,0,puz,costs))
    global finding

    while len(q):
        items = q.pop(0)
        cost = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _costs = items[6]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break

        if((c_depth+cost) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i-1)*3+_j] = HS(_i-1,_j,swap_puz[(_i-1)*3+_j])
            q.append((c_depth+1+sumCost(swap_cost),c_depth+1,_i-1,_j,2,swap_puz,swap_cost))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i+1)*3+_j] = HS(_i+1,_j,swap_puz[(_i+1)*3+_j])
            q.append((c_depth+1+sumCost(swap_cost),c_depth+1,_i+1,_j,1,swap_puz,swap_cost))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j-1] = HS(_i,_j-1,swap_puz[_i*3+_j-1])
            q.append((c_depth+1+sumCost(swap_cost),c_depth+1,_i,_j-1,4,swap_puz,swap_cost))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j+1] = HS(_i,_j+1,swap_puz[_i*3+_j+1])
            q.append((c_depth+1+sumCost(swap_cost),c_depth+1,_i,_j+1,3,swap_puz,swap_cost))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1


Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append((simpleHS(puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = q.pop(0)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break
        if((c_depth+c_dWithH) > depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1


Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append((simpleHS(puz),0,i,j,0,puz))
    global finding

    while len(q):
        items = heapq.heappop(q)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break
        if((c_depth+c_dWithH) > depth):
            continue
            
        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),c_depth+1,_i,_j+1,3,swap_puz))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumCost(costs),(0,i,j,0,puz,costs)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _costs = items[5]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break
        if((c_depth+cost) >= depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i-1)*3+_j] = HS(_i-1,_j,swap_puz[(_i-1)*3+_j])
            heapq.heappush(q,(c_depth+1+sumCost(swap_cost),(c_depth+1,_i-1,_j,2,swap_puz,swap_cost)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[(_i+1)*3+_j] = HS(_i+1,_j,swap_puz[(_i+1)*3+_j])
            heapq.heappush(q,(c_depth+1+sumCost(swap_cost),(c_depth+1,_i+1,_j,1,swap_puz,swap_cost)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j-1] = HS(_i,_j-1,swap_puz[_i*3+_j-1])
            heapq.heappush(q,(c_depth+1+sumCost(swap_cost),(c_depth+1,_i,_j-1,4,swap_puz,swap_cost)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            swap_cost = _costs[0:]
            swap_cost[_i*3+_j] = HS(_i,_j,swap_puz[_i*3+_j])
            swap_cost[_i*3+_j+1] = HS(_i,_j+1,swap_puz[_i*3+_j+1])
            heapq.heappush(q,(c_depth+1+sumCost(swap_cost),(c_depth+1,_i,_j+1,3,swap_puz,swap_cost)))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(simpleHS(puz),(0,i,j,0,puz)))
    global finding

    while len(q):
        c_dWithH, items = q.pop(0)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        if(puzzleCheck(c_puz)):
            finding = 1
            print(c_depth)
            break
        if((c_dWithH) > depth):
            continue

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),(c_depth+1,_i+1,_j,1,swap_puz)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+simpleHS(swap_puz),(c_depth+1,_i,_j+1,3,swap_puz)))

def checkPuzIsExisted(puz,q):
    for i in range(len(q)):
        exist_puz = q[i][4]
        count = 0
        for j in range(len(exist_puz)):
            if(exist_puz[j] != puz[j]):
                count = 1
        if(count == 0):
            return True
    return False

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]
costs = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

for i in range(len(costs)):
    _i = (int)(i/3)
    _j = i - _i*3
    costs[i] = HS(_i,_j,puz[i])

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1





Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        c_dWithH, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),(c_depth+1,_i+1,_j,1,swap_puz)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost
    

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        c_dWithH, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),(c_depth+1,_i+1,_j,1,swap_puz)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            heapq.heappush(q,(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost
    

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

finding = 0
depth = sumcost
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Runtime Error):
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append(sumcost,(0,i,j,0,puz))
    global finding

    while len(q):
        c_dWithH, items = q.pop(0)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        print(c_depth)
        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),(c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),(c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),(c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),(c_depth+1,_i,_j+1,3,swap_puz))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost
    

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Runtime Error):
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append(sumcost,0,i,j,0,puz)
    global finding

    while len(q):
        c_dWithH, items = q.pop(0)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        print(c_depth)
        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),c_depth+1,_i-1,_j,2,swap_puz)
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),c_depth+1,_i+1,_j,1,swap_puz)
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),c_depth+1,_i,_j-1,4,swap_puz)
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            q.append(c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),c_depth+1,_i,_j+1,3,swap_puz)

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost
    

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    q.append((sumcost,0,i,j,0,puz))
    global finding

    while len(q):
        items = q.pop(0)
        c_dWithH = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            q.append((c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j)),c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            q.append((c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j)),c_depth+1,_i+1,_j,1,swap_puz))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            q.append((c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1)),c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            q.append((c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1)),c_depth+1,_i,_j+1,3,swap_puz))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost
    

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1

Buggy python submission (verdict: Time Limit Exceeded):
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        c_dWithH, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = c_dWithH - c_depth

        if(c_dWithH - c_depth == 0):
            finding = 1
            print(c_depth)
            break
        if(c_dWithH > depth):
            continue

        c_cost = simpleHS(c_puz,_i,_j)

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i-1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i-1,_j))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i+1,_j),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i+1,_j))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j-1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j-1))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = c_depth+1+_sum_cost+checkCost(c_cost,simpleHS(c_puz,_i,_j+1),simpleHS(swap_puz,_i,_j),simpleHS(swap_puz,_i,_j+1))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost
    

def sumCost(costs):
    value = 0
    for i in range(len(costs)):
        value += costs[i]
    return value

def simpleHS(c_puz,i,j):
    if(correctPuz[i*3+j] != c_puz[i*3+j]):
        return 1
    return 0

def HS(i,j,num):
    k = correctPuz.index(num)
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(_i-ki)+abs(_j-kj) 
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[8] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost=0
for i in range(len(correctPuz)):
    if(correctPuz[i] != puz[i]):
        sumcost+=1

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1



Fixed submission:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 2 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 2 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(3):
        value += HS(i,0,puz[i*3])
        value += HS(i,1,puz[i*3+1])
        value += HS(i,2,puz[i*3+2])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 8
    ki = (int)(k/3)
    kj = k - ki*3
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*3+j2],c_puz[i*3+j] = c_puz[i*3+j],c_puz[i2*3+j2]
    return c_puz

correctPuz = [i+1 for i in range(9)]
correctPuz[8] = 0
puz = [0 for i in range(9)]

i_start = 0
j_start = 0

for i in range(3):
    puz[i*3],puz[i*3+1],puz[i*3+2] = map(int, input().split());
    if(puz[i*3] == 0):
        i_start,j_start = i,0
    elif(puz[i*3+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*3+2] == 0):
        i_start,j_start = i,2

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1):
        break
    iterative(i_start,j_start)
    depth+=1