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: Wrong Answer

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]
        
        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+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+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+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+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: Wrong Answer

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])

        print(c_depth,_sum_cost,c_puz)
        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: Wrong Answer

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]
        print(depth,cost,cost2)
        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

Submission status: Wrong Answer

Solution code:
import heapq

N, N2 = 4, 16
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
dir = ['r', 'u', 'l', 'd']
MDT = [[abs(i//N - j//N) + abs(i%N - j%N) for j in range(N2)] for i in range(N2)]

class Puzzle:
    def __init__(self, field=None, space=None, MD=None, cost=None):
        self.field = field
        self.space = space
        self.MD = MD
        self.cost = cost

    def __lt__(self, pzl): # <
        for i in range(N2):
            if self.field[i] == pzl.field[i]:
                continue
            return self.field[i] > pzl.field[i]
        return False

    def set_MD(self):
        sum = 0
        for i in range(N2):
            if self.field[i] == N2: continue
            sum += MDT[i][self.field[i]-1]
        self.MD = sum

class State():
    def __init__(self, pzl=None, estimated=None):
        self.puzzle = pzl
        self.estimated = estimated

    def __lt__(self, stat):
        return self.estimated < stat.estimated

def astar(pzl):
    pqueue = []
    pzl.set_MD()
    pzl.cost = 0
    V = {}
    u, v = Puzzle(), Puzzle()
    initial = State(pzl, pzl.MD)
    heapq.heappush(pqueue, initial)

    if pzl.MD == 0: return pzl.cost

    while len(pqueue) != 0:
        st = heapq.heappop(pqueue)
        u = st.puzzle

        V[str(u.field)] = True

        sx = u.space//N
        sy = u.space%N
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= N or ty >= N: continue
            v = Puzzle(field=[u.field[i] for i in range(N2)], space=u.space, MD=u.MD, cost=u.cost)

            v.MD -= MDT[tx*N + ty][v.field[tx*N + ty]-1]
            v.MD += MDT[sx*N + sy][v.field[tx*N + ty]-1]

            v.field[sx*N + sy], v.field[tx*N + ty] = v.field[tx*N + ty], v.field[sx*N + sy]
            v.space = tx*N + ty
            if not V.get(str(v.field)):
                if v.MD == 0: return v.cost
                v.cost += 1
                news = State()
                news.puzzle = v
                news.estimated = v.cost + v.MD
                heapq.heappush(pqueue, news)
    return -1

field = []
for i in range(4):
    field.extend(list(map(int, input().split(' '))))

space = None
for i in range(N2):
    if field[i] == 0:
        field[i] = N2
        space = i
        break

s = Puzzle(field=field, space=space)
print(astar(s))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

def dpkey(P):
    tmp = ""
    for i in P:
        for j in i:
            tmp += str(j) + " "
    return tmp

A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {dpkey(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = dpkey(i)
        if key == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if dpkey(A) == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

def dpkey(P):
    tmp = ""
    for i in P:
        for j in i:
            tmp += str(j) + " "
    return tmp
 
A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {dpkey(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = dpkey(i)
        if key == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if dpkey(A) == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {str(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = str(i)
        if key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def move(P,r,c):
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def move(P,r,c):
    global dp
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        if not str(tmp) in dp:
            tmpr = r - 1
            yield tmp,tmpr,c
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        if not str(tmp) in dp:
            tmpr = r + 1
            yield tmp,tmpr,c
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        if not str(tmp) in dp:
            tmpc = c - 1
            yield tmp,r,tmpc
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        if not str(tmp) in dp:
            tmpc = c + 1
            yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
while(True):
    tmp,count,r,c = d.pop()
    if str(tmp) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
        ans = count
        break
    for i,j,k in move(tmp,r,c):
        dp[str(i)] = 1
        d.appendleft((i,count+1,j,k))
        
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def move(P,r,c):
    if r > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if r < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if c > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if c < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key in dp:
            continue
        elif key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def move(P,r,c):
    if r > 0:
        tmp = copy.deepcopy(P)
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if r < 3:
        tmp = copy.deepcopy(P)
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if c > 0:
        tmp = copy.deepcopy(P)
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if c < 3:
        tmp = copy.deepcopy(P)
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key in dp:
            continue
        elif key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def move(P,r,c):
    if r > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        tmpr = r - 1
        yield tmp,tmpr,c
    if r < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        tmpr = r + 1
        yield tmp,tmpr,c
    if c > 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        tmpc = c - 1
        yield tmp,r,tmpc
    if c < 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        tmpc = c + 1
        yield tmp,r,tmpc

A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
        for j in range(4):
            if A[i][j] == 0:
                r,c = i,j
dp = {str(A) : 1}
d = deque([(A,0,r,c)])
flag = True
t = 0
while(flag):
    tmp,count,r,c = d.pop()
    for i,j,k in move(tmp,r,c):
        key = str(i)
        if key in dp:
            continue
        elif key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j,k))
            t+=1
if str(A) == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
d = deque([(A,0,A.index(0))])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            d.appendleft((i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+1 < ans:
                heapq.heappush(h,(mht,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    return mht
        
A = []
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A),A,0,A.index(0))]
heapq.heapify(h)
ans = 46
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            if count+1<ans:
                ans = count + 1
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+1 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)