Problem:


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

15 Puzzle

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

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

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15

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

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

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

Input

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

Output

  Print the fewest steps in a line.

Constraints

The given puzzle is solvable in at most 45 steps.

Sample Input

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15

Sample Output

8



Sample input:
1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
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 > 45):
            continue

        c_cost = HS(_i,_j,c_puz[_i*4+_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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if(n_cost <= 45):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 3 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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            if(n_cost <= 45):
                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*4+_j-1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if(n_cost <= 45):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 3 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*4+_j+1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j+1,swap_puz[_i*4+_j+1]))
            if(n_cost <= 45):
                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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

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


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

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)

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

Submission status: Time Limit Exceeded

Solution code:
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*4+_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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 3 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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i+1,_j,swap_puz[(_i+1)*4+_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*4+_j-1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 3 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*4+_j+1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j+1,swap_puz[_i*4+_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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

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


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

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)

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

Submission status: Time Limit Exceeded

Solution code:
import sys;
import heapq
from collections import deque

def iterative(i,j):
    q = deque()
    q.appendleft((sumcost,0,i,j,0,puz))
    global finding

    while len(q):
        items = q.pop()
        cost = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _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*4+_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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if(n_cost <= depth):
                q.appendleft((n_cost,c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 3 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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            if(n_cost <= depth):
                q.appendleft((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*4+_j-1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if(n_cost <= depth):
                q.appendleft((n_cost,c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 3 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*4+_j+1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j+1,swap_puz[_i*4+_j+1]))
            if(n_cost <= depth):
                q.appendleft((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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

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


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

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)

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

Submission status: Time Limit Exceeded

Solution code:
import sys;
import heapq
from collections import deque

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

    while len(q):
        items = q.pop()
        cost = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _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*4+_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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if(n_cost <= depth):
                q.append((n_cost,c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 3 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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            if(n_cost <= depth):
                q.append((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*4+_j-1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if(n_cost <= depth):
                q.append((n_cost,c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 3 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*4+_j+1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j+1,swap_puz[_i*4+_j+1]))
            if(n_cost <= depth):
                q.append((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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

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


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

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)

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

Submission status: Time Limit Exceeded

Solution code:
import sys;
import heapq
from collections import deque

def iterative(i,j):
    q = deque()
    q.append((sumcost+sum2cost,0,i,j,0,puz))
    global finding

    while len(q):
        items = q.pop()
        cost = items[0]
        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _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*4+_j])
        c2_cost = simpleHS(_i,_j,c_puz[_i*4+_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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            n_cost += checkCost(c2_cost,simpleHS(_i-1,_j,c_puz[(_i-1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if(n_cost <= depth):
                q.append((n_cost,c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 3 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)*4+_j]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            n_cost += checkCost(c2_cost,simpleHS(_i+1,_j,c_puz[(_i+1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            if(n_cost <= depth):
                q.append((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*4+_j-1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j-1,swap_puz[_i*4+_j-1]))
            n_cost += checkCost(c2_cost,simpleHS(_i,_j-1,c_puz[_i*4+_j-1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if(n_cost <= depth):
                q.append((n_cost,c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 3 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*4+_j+1]),HS(_i,_j,swap_puz[_i*4+_j]),HS(_i,_j+1,swap_puz[_i*4+_j+1]))
            n_cost += checkCost(c2_cost,simpleHS(_i,_j+1,c_puz[_i*4+_j+1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j+1,swap_puz[_i*4+_j+1]))
            if(n_cost <= depth):
                q.append((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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

def simpleHS(i,j,puz):
    if(not correctPuz[i+j] == puz):
        return 1
    return 0

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


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

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)
sum2cost = 0
for i in range(4):
    sum2cost += simpleHS(i*4,0,puz[i*4])
    sum2cost += simpleHS(i*4,1,puz[i*4+1])
    sum2cost += simpleHS(i*4,2,puz[i*4+2])
    sum2cost += simpleHS(i*4,3,puz[i*4+3])

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

Submission status: Time Limit Exceeded

Solution code:
import sys;
import heapq
from collections import deque

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

    while len(q):
        items = q.popleft()
        cost = items[0]
        
        if(cost > depth):
            continue

        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _sum_cost = cost - c_depth

        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        _i4 = _i*4
        c_cost = HS(_i,_j,c_puz[_i4+_j])
        #c2_cost = simpleHS(_i,_j,c_puz[_i*4+_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[_i4-4+_j]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i-1,_j,swap_puz[_i4-4+_j]))
            #n_cost += checkCost(c2_cost,simpleHS(_i-1,_j,c_puz[(_i-1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if(n_cost <= depth):
                q.append((n_cost,c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 3 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[_i4+4+_j]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i+1,_j,swap_puz[_i4+4+_j]))
            #n_cost += checkCost(c2_cost,simpleHS(_i+1,_j,c_puz[(_i+1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            if(n_cost <= depth):
                q.append((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[_i4+_j-1]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i,_j-1,swap_puz[_i4+_j-1]))
            #n_cost += checkCost(c2_cost,simpleHS(_i,_j-1,c_puz[_i*4+_j-1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if(n_cost <= depth):
                q.append((n_cost,c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 3 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[_i4+_j+1]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i,_j+1,swap_puz[_i4+_j+1]))
            #n_cost += checkCost(c2_cost,simpleHS(_i,_j+1,c_puz[_i*4+_j+1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j+1,swap_puz[_i*4+_j+1]))
            if(n_cost <= depth):
                q.append((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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

def simpleHS(i,j,puz):
    if(not correctPuz[i+j] == puz):
        return 1
    return 0

def HS(i,j,num):
    k = num-1
    if(k == -1):
        k = 15
    ki = (int)(k/4)
    kj = k - ki*4
    value = abs(i-ki)+abs(j-kj)
    return value

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

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)
#sum2cost = 0
#for i in range(4):
#    sum2cost += simpleHS(i*4,0,puz[i*4])
#    sum2cost += simpleHS(i*4,1,puz[i*4+1])
#    sum2cost += simpleHS(i*4,2,puz[i*4+2])
#    sum2cost += simpleHS(i*4,3,puz[i*4+3])

finding = 0
depth = 45
iterative(i_start,j_start)

Submission status: Time Limit Exceeded

Solution code:
import sys;
import heapq
from collections import deque

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

    if(sumcost > depth):
        return

    while len(q):
        items = q.pop()
        cost = items[0]

        c_depth = items[1]
        _i = items[2]
        _j = items[3]
        prev_move = items[4]
        c_puz = items[5]
        _sum_cost = cost - c_depth

        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        _i4 = _i*4
        c_cost = HS(_i,_j,c_puz[_i4+_j])
        c2_cost = simpleHS(_i,_j,c_puz[_i*4+_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[_i4-4+_j]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i-1,_j,swap_puz[_i4-4+_j]))
            n2_cost = cost+1+checkCost(c2_cost,simpleHS(_i-1,_j,c_puz[(_i-1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if(n_cost <= depth and n2_cost <= depth):
                q.append((n_cost,c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 3 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[_i4+4+_j]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i+1,_j,swap_puz[_i4+4+_j]))
            n2_cost = cost+1+checkCost(c2_cost,simpleHS(_i+1,_j,c_puz[(_i+1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            if(n_cost <= depth and n2_cost <= depth):
                q.append((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[_i4+_j-1]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i,_j-1,swap_puz[_i4+_j-1]))
            n2_cost = cost+1+checkCost(c2_cost,simpleHS(_i,_j-1,c_puz[_i*4+_j-1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if(n_cost <= depth and n2_cost <= depth):
                q.append((n_cost,c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 3 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[_i4+_j+1]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i,_j+1,swap_puz[_i4+_j+1]))
            n2_cost = cost+1+checkCost(c2_cost,simpleHS(_i,_j+1,c_puz[_i*4+_j+1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j+1,swap_puz[_i*4+_j+1]))
            if(n_cost <= depth and n2_cost <= depth):
                q.append((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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

def simpleHS(i,j,puz):
    if(not correctPuz[i+j] == puz):
        return 1
    return 0

def HS(i,j,num):
    k = num-1
    if(k == -1):
        k = 15
    ki = (int)(k/4)
    kj = k - ki*4
    value = abs(i-ki)+abs(j-kj)
    return value

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

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)
sum2cost = 0
for i in range(4):
    sum2cost += simpleHS(i*4,0,puz[i*4])
    sum2cost += simpleHS(i*4,1,puz[i*4+1])
    sum2cost += simpleHS(i*4,2,puz[i*4+2])
    sum2cost += simpleHS(i*4,3,puz[i*4+3])

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

Submission status: Time Limit Exceeded

Solution code:
import sys;
import heapq
from collections import deque

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

    if(sumcost > depth or sum2cost > depth):
        return

    while len(q):
        items = q.popleft()
        cost = items[0]
        cost2 = items[1]
        c_depth = items[2]
        _i = items[3]
        _j = items[4]
        prev_move = items[5]
        c_puz = items[6]
        if(cost == 0 or cost2 == 0):
            finding = 1
            print(c_depth)
            break
        _i4 = _i*4
        c_cost = HS(_i,_j,c_puz[_i4+_j])
        c2_cost = simpleHS(_i,_j,c_puz[_i4+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+checkCost(c_cost,HS(_i-1,_j,c_puz[_i4-4+_j]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i-1,_j,swap_puz[_i4-4+_j]))
            n2_cost = cost2+checkCost(c2_cost,simpleHS(_i-1,_j,c_puz[(_i-1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i-1,_j,swap_puz[(_i-1)*4+_j]))
            if((n_cost+c_depth+1) <= depth and (n2_cost+c_depth+1) <= depth):
                q.append((n_cost,n2_cost,c_depth+1,_i-1,_j,2,swap_puz))
        if(_i != 3 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+checkCost(c_cost,HS(_i+1,_j,c_puz[_i4+4+_j]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i+1,_j,swap_puz[_i4+4+_j]))
            n2_cost = cost2+checkCost(c2_cost,simpleHS(_i+1,_j,c_puz[(_i+1)*4+_j]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i+1,_j,swap_puz[(_i+1)*4+_j]))
            if((n_cost+c_depth+1) <= depth and (n2_cost+c_depth+1) <= depth):
                q.append((n_cost,n2_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+checkCost(c_cost,HS(_i,_j-1,c_puz[_i4+_j-1]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i,_j-1,swap_puz[_i4+_j-1]))
            n2_cost = cost2+checkCost(c2_cost,simpleHS(_i,_j-1,c_puz[_i*4+_j-1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j-1,swap_puz[_i*4+_j-1]))
            if((n_cost+c_depth+1) <= depth and (n2_cost+c_depth+1) <= depth):
                q.append((n_cost,n2_cost,c_depth+1,_i,_j-1,4,swap_puz))
        if(_j != 3 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+checkCost(c_cost,HS(_i,_j+1,c_puz[_i4+_j+1]),HS(_i,_j,swap_puz[_i4+_j]),HS(_i,_j+1,swap_puz[_i4+_j+1]))
            n2_cost = cost2+checkCost(c2_cost,simpleHS(_i,_j+1,c_puz[_i*4+_j+1]),simpleHS(_i,_j,swap_puz[_i*4+_j]),simpleHS(_i,_j+1,swap_puz[_i*4+_j+1]))
            if((n_cost+c_depth+1) <= depth and (n2_cost+c_depth+1) <= depth):
                q.append((n_cost,n2_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(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,3,puz[i*4+3])
    return value

def simpleHS(i,j,puz):
    if(not correctPuz[i+j] == puz):
        return 1
    return 0

def HS(i,j,num):
    k = num-1
    if(k == -1):
        k = 15
    ki = (int)(k/4)
    kj = k - ki*4
    value = abs(i-ki)+abs(j-kj)
    return value

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

def puzzleCheck(c_puz):
    if(c_puz[15] == 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(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

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

sumcost = sumCost(puz)
sum2cost = 0
for i in range(4):
    sum2cost += simpleHS(i*4,0,puz[i*4])
    sum2cost += simpleHS(i*4,1,puz[i*4+1])
    sum2cost += simpleHS(i*4,2,puz[i*4+2])
    sum2cost += simpleHS(i*4,3,puz[i*4+3])

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