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

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht

A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
ans = 46
while(len(d)>0 and len(e)>0):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpans = count + 1 + dp[key][1]
                if tmpans < ans:
                    ans = tmpans
        else:
            if evaluate(B,i)//2 + count < ans:
                dp[key] = (1,count+1)
                d.append((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpans = count + 1 + dp[key][1]
                if tmpans < ans:
                    ans = tmpans
        else:
            if evaluate(A,i)//2 + count < 46:
                dp[key] = (2,count+1)
                e.append((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)
flag = True
while(flag):
    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]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht//2+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)

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)
flag = True
while(flag):
    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]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht*7//6+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)

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)
flag = True
while(flag):
    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]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(i)
            if count+mht//2 < 46:
                heapq.heappush(h,(mht*16//15+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)

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)
flag = True
sw = False
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    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
            mht = evaluate(i)
            if count+mht//2 < 46:
                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)

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)
flag = True
sw = False
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    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
            mht = evaluate(i)
            if count+mht < 46:
                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)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht//2 < ans:
                heapq.heappush(e,(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)

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,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : 1}
h = [(evaluate(A,B),A,0,A.index(0))]
heapq.heapify(h)
flag = True
while(flag):
    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]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            mht = evaluate(B,i)
            if count+mht*14//13 < 46:
                heapq.heappush(h,(mht//2+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)

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):
    wd = 0
    for i,j in enumerate(P):
        if j == 0:
            wd+=len(P[i+1:])
        else:
            for k in P[i+1:]:
                if P[i] < k:
                    wd+=1
        return wd
        
A = []
#B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
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)
flag = True
while(flag):
    wd,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]":
            ans = count + 1
            flag = False
        else:
            dp[key] = 1
            wd = evaluate(i)
            if count+wd < 46:
                heapq.heappush(h,(wd+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)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht < ans:
                heapq.heappush(e,(mht//2+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)

Submission status: Time Limit Exceeded

Solution code:
import sys, itertools
f = sys.stdin
start = [line.split() for line in f]
start = tuple(int(x) for y in start for x in y)
end =(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)

d = {start:0}

def next_board(b):
    brank = b.index(0)
    if brank % 4:
        yield b[:brank - 1] + (b[brank], b[brank - 1]) + b[brank + 1:]
    if brank // 4:
        yield b[:brank - 4] + (b[brank],)+ b[brank - 3:brank] +  (b[brank - 4],) + b[brank + 1:]
    if brank % 4 != 3:
        yield b[:brank] + (b[brank + 1], b[brank]) + b[brank + 2:]
    if brank // 4 != 3:
        yield b[:brank] + (b[brank + 4],)+ b[brank + 1:brank + 4] +  (b[brank],) + b[brank + 5:]

queue = set([start])
while len(queue):
    u = queue.pop()
    for b in next_board(u):
        if (end not in d or d[end] > d[u]) and (b not in d or d[b] > d[u] + 1):
            d[b] = d[u] + 1
            queue.update([b])
        
print(d[end])

Submission status: Time Limit Exceeded

Solution code:
import collections
start = [input().split() for _ in range(4)]
start = [x for y in start for x in y]
start[start.index('10')] = 'a'
start[start.index('11')] = 'b'
start[start.index('12')] = 'c'
start[start.index('13')] = 'd'
start[start.index('14')] = 'e'
start[start.index('15')] = 'f'
start = ''.join(start)

end = '123456789abcdef0'

def next_board(b):
    z = b.index('0')
    if z % 4:
        yield swap(b, z, z - 1)
    if z // 4:
        yield swap(b, z, z - 4)
    if z % 4 != 3:
        yield swap(b, z, z + 1)
    if z // 4 != 3:
        yield swap(b, z, z + 4)

def swap(b, i, j):
    b = list(b)
    b[i], b[j] = b[j], b[i]
    return ''.join(b)
        
d = {start:1, end:-1}
queue = collections.deque([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.popleft()
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.append((b, way))
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
from collections import namedtuple


def get_offset(x, y):
    return 16 * y + 4 * x


def swap(board, orig_x, orig_y, dest_x, dest_y):
    orig_offset = get_offset(orig_x, orig_y)
    dest_offset = get_offset(dest_x, dest_y)
    try:
        dest_val = board & (0b1111 << dest_offset)
    except:
        print(orig_x, orig_y, dest_x, dest_y)
        raise
    offset_diff = dest_offset - orig_offset
    swap_val = dest_val >> offset_diff if offset_diff > 0 else dest_val << abs(offset_diff)
    return board - dest_val + swap_val


def put_next_puzzle(puzzle):
    board, x0, y0, count = puzzle.board, puzzle.x0, puzzle.y0, puzzle.count
    for move_horizontal in [0, 1]:
        for direction in [-1, 1]:
            if move_horizontal:
                new_x0, new_y0 = x0 + direction, y0
                if not 0 <= new_x0 < 4:
                    continue
            else:
                new_x0, new_y0 = x0, y0 + direction
                if not 0 <= new_y0 < 4:
                    continue
            new_board = swap(board, x0, y0, new_x0, new_y0)
            if new_board in cache:
                continue
            if new_board == CORRECT:
                return count + 1
            cache.append(new_board)
            puzzles.put(Puzzle(
                    board=new_board,
                    count=count + 1,
                    x0=new_x0,
                    y0=new_y0
            ))
    return -1


CORRECT = 0x0fedcba987654321
puzzles = Queue()
Puzzle = namedtuple('Puzzle', 'board count x0 y0')
cache = []
board = 0
x0 = y0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        board += v << get_offset(i, j)
        if v == 0:
            x0, y0 = i, j

# print('%x' % board)

puzzles.put(Puzzle(board=board, count=0, x0=x0, y0=y0))
cache.append(board)
result = None

while True:
    if puzzles.empty():
        break

    result = put_next_puzzle(puzzles.get())
    if result > -1:
        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
from collections import namedtuple


def get_offset(x, y):
    return 16 * y + 4 * x


def get_candidate(pid):
    def check(pid, move):
        if abs(move) == 1:
            return pid // 4 == (pid + move) // 4
        else:
            return 0 <= pid + move < 16

    return tuple(pid + move for move in MOVE_CANDIDATE if check(pid, move))


def get_swap_values(orig):
    return {dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest]) for dest in SWAP_CANDIDATE[orig]}


MOVE_CANDIDATE = (-4, -1, 1, 4)
SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))


def swap(board, orig, dest):
    dest_val = (board >> OFFSET_MASTER[dest]) & 0b1111
    return board + dest_val * SWAP_VALUE_MASTER[orig][dest]


def put_next_puzzle(is_reverse):
    global puzzles, cache
    puzzle = puzzles[is_reverse].get()
    board, id0, count, prev = puzzle.board, puzzle.id0, puzzle.count, puzzle.prev
    for new_id0 in SWAP_CANDIDATE[id0]:
        if new_id0 == prev:
            continue

        new_board = swap(board, id0, new_id0)
        if new_board in cache[is_reverse]:
            continue
        if new_board in cache[not is_reverse]:
            return cache[not is_reverse][new_board].count + count + 1
        new_puzzle = Puzzle(
                board=new_board,
                count=count + 1,
                id0=new_id0,
                prev=id0,
                trace=puzzle.trace * 16 + new_id0
        )
        cache[is_reverse][new_board] = new_puzzle
        puzzles[is_reverse].put(new_puzzle)
    return -1


CORRECT = 0x0fedcba987654321
Puzzle = namedtuple('Puzzle', 'board count id0 prev trace')
puzzles = (Queue(), Queue())
cache = ({}, {})
board = 0
id0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        board += v << get_offset(i, j)
        if v == 0:
            id0 = 4 * j + i

start = Puzzle(board=board, count=0, id0=id0, prev=-1, trace=0)
goal = Puzzle(board=CORRECT, count=0, id0=15, prev=-1, trace=0)
puzzles[0].put(start)
puzzles[1].put(goal)
cache[0][board] = start
cache[1][CORRECT] = goal
result = None
is_reverse = False

while True:
    result = put_next_puzzle(is_reverse)
    if result > -1:
        break
    is_reverse = not is_reverse

print(result)

Submission status: Time Limit Exceeded

Solution code:
import heapq

CORRECT = 0x0fedcba987654321
heap_puzzle = []
cache = {}


class Puzzle:
    DEST_BOARD_DICT = {CORRECT >> (4 * i) & 0b1111: i for i in range(16)}
    HEURISTICS = tuple(
            tuple(abs(dest // 4 - orig // 4) + abs(dest % 4 - orig % 4) for dest in range(16)) for orig in range(16))

    def __init__(self, board, pid0, count, prev, heuristic=None):
        self.board = board
        self.pid0 = pid0
        self.count = count
        self.prev = prev
        self.invalid = False
        self.heuristic = heuristic

    def swap(self, dest):
        global OFFSET_MASTER, SWAP_VALUE_MASTER
        dest_val = (self.board >> OFFSET_MASTER[dest]) & 0b1111
        return self.board + dest_val * SWAP_VALUE_MASTER[self.pid0][dest]

    def get_sum_heuristic(self):
        if self.heuristic is not None:
            return self.heuristic

        orig_board_dict = {i: self.board >> (4 * i) & 0b1111 for i in range(16)}
        self.heuristic = sum(self.HEURISTICS[pid][self.DEST_BOARD_DICT[val]] for pid, val in orig_board_dict.items())

        return self.heuristic

    def __lt__(self, other):
        return False


def get_offset(x, y):
    return 16 * y + 4 * x


def get_candidate(pid):
    global MOVE_CANDIDATE

    def check(pid, move):
        if abs(move) == 1:
            return pid // 4 == (pid + move) // 4
        else:
            return 0 <= pid + move < 16

    return tuple(pid + move for move in MOVE_CANDIDATE if check(pid, move))


def get_swap_values(orig):
    global OFFSET_MASTER, SWAP_CANDIDATE
    return {dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest]) for dest in SWAP_CANDIDATE[orig]}


MOVE_CANDIDATE = (-4, -1, 1, 4)
SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))


def put_next_puzzle():
    global heap_puzzle, cache
    (cost, puzzle) = heapq.heappop(heap_puzzle)
    if puzzle.invalid:
        return -1
    board, pid0, count, prev = puzzle.board, puzzle.pid0, puzzle.count, puzzle.prev
    for new_pid0 in SWAP_CANDIDATE[pid0]:
        if new_pid0 == prev:
            continue

        new_board = puzzle.swap(new_pid0)

        if new_board == CORRECT:
            return count + 1

        heuristic = None
        if new_board in cache:
            closed_puzzle = cache[new_board]
            if closed_puzzle.count <= count:
                continue
            else:
                closed_puzzle.invalid = True
                heuristic = closed_puzzle.heuristic

        new_puzzle = Puzzle(
                board=new_board,
                count=count + 1,
                pid0=new_pid0,
                prev=pid0,
                heuristic=heuristic
        )
        new_cost = count + 1 + new_puzzle.get_sum_heuristic()
        heapq.heappush(heap_puzzle, (new_cost, new_puzzle))
        cache[new_board] = new_puzzle
    return -1


first_board = 0
first_pid0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        first_board += v << get_offset(i, j)
        if v == 0:
            first_pid0 = 4 * j + i

s_puzzle = Puzzle(board=first_board, count=0, pid0=first_pid0, prev=-1)
heapq.heappush(heap_puzzle, (s_puzzle.get_sum_heuristic(), s_puzzle))
cache[first_board] = s_puzzle
result = None

while True:
    result = put_next_puzzle()
    if result > -1:
        break

print(result)