Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import copy
dx = [1,0,-1,0]
dy = [0,1,0,-1]
dir = "ruld"
N = 4
N2 = 16
LIMIT = 50
MDT = [[0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6],
        [1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5],
        [2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4],
        [3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3],
        [1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5],
        [2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4],
        [3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3],
        [4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2],
        [2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4],
        [3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3],
        [4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2],
        [5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1],
        [3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3],
        [4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2],
        [5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1],
        [6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0]]
class Puzzle():
    def __init__(self):
        self.f = [0] * N2
        self.space, self.MD = 0, 0
state = Puzzle()
limit = 0
path = [0] * LIMIT
def dfs(depth, prev, limit, state, path):
    if state.MD == 0: return True
    if depth + state.MD > limit: return False
    sx = state.space // N
    sy = state.space % N
    tmp = Puzzle()
    for r in range(4):
        tx = sx + dx[r]
        ty = sy + dy[r]
        if tx < 0 or tx >= N or ty < 0 or ty >= N: continue
        if max(prev, r) - min(prev, r) == 2: continue
        tmp = copy.deepcopy(state)
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1]
        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1]
        state.f[tx * N + ty], state.f[sx * N + sy] = state.f[sx * N + sy], state.f[tx * N + ty]
        state.space = tx * N + ty
        if dfs(depth + 1, r, limit, state, path):
            path[depth] = r
            return True
        state = copy.deepcopy(tmp)
    return False
In = Puzzle()
for k in range(N2 // 4):
    for n, j in enumerate(map(int, stdin.readline().split())):
        i = k * 4 + n
        if j == 0:
            In.f[i] = N2
            In.space = i
        else:
            In.f[i] = j
for i in range(0, N2):
    if (In.f[i] == N2): continue
    In.MD += MDT[i][In.f[i] - 1]
ans = ""
for limit in range(In.MD, LIMIT + 1):
    state = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)

Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import copy
dx = [1,0,-1,0]
dy = [0,1,0,-1]
dir = "ruld"
N = 4
N2 = 16
LIMIT = 50
MDT = ((0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
        (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
        (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
        (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
        (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
        (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
        (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
        (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
        (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
        (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
        (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
        (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
        (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
        (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
        (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
        (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0))
class Puzzle():
    def __init__(self):
        self.f = [0] * N2
        self.space, self.MD = 0, 0
state = Puzzle()
limit = 0
path = [0] * LIMIT
def dfs(depth, prev, limit, state, path):
    if state.MD == 0: return True
    if depth + state.MD > limit: return False
    sx = state.space // N
    sy = state.space % N
    tmp = Puzzle()
    for r in range(4):
        tx = sx + dx[r]
        ty = sy + dy[r]
        if tx < 0 or tx >= N or ty < 0 or ty >= N: continue
        if max(prev, r) - min(prev, r) == 2: continue
        tmp = copy.deepcopy(state)
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1]
        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1]
        state.f[tx * N + ty], state.f[sx * N + sy] = state.f[sx * N + sy], state.f[tx * N + ty]
        state.space = tx * N + ty
        if dfs(depth + 1, r, limit, state, path):
            path[depth] = r
            return True
        state = copy.deepcopy(tmp)
    return False
In = Puzzle()
for k in range(N2 // 4):
    for n, j in enumerate(map(int, stdin.readline().split())):
        i = k * 4 + n
        if j == 0:
            In.f[i] = N2
            In.space = i
        else:
            In.f[i] = j
for i in range(0, N2):
    if (In.f[i] == N2): continue
    In.MD += MDT[i][In.f[i] - 1]
ans = ""
for limit in range(In.MD, LIMIT + 1):
    state = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)

Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import copy
dx = tuple(1,0,-1,0)
dy = tuple(0,1,0,-1)
dir = "ruld"
N = 4
N2 = 16
LIMIT = 50
MDT = ((0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
        (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
        (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
        (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
        (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
        (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
        (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
        (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
        (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
        (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
        (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
        (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
        (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
        (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
        (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
        (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0))
class Puzzle():
    def __init__(self):
        self.f = [0] * N2
        self.space, self.MD = 0, 0
state = Puzzle()
limit = 0
path = [0] * LIMIT
def dfs(depth, prev, limit, state, path):
    if state.MD == 0: return True
    if depth + state.MD > limit: return False
    sx = state.space // N
    sy = state.space % N
    tmp = Puzzle()
    for r in range(4):
        tx = sx + dx[r]
        ty = sy + dy[r]
        if tx < 0 or tx >= N or ty < 0 or ty >= N: continue
        if max(prev, r) - min(prev, r) == 2: continue
        tmp = copy.deepcopy(state)
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1]
        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1]
        state.f[tx * N + ty], state.f[sx * N + sy] = state.f[sx * N + sy], state.f[tx * N + ty]
        state.space = tx * N + ty
        if dfs(depth + 1, r, limit, state, path):
            path[depth] = r
            return True
        state = copy.deepcopy(tmp)
    return False
In = Puzzle()
for k in range(N2 // 4):
    for n, j in enumerate(map(int, stdin.readline().split())):
        i = k * 4 + n
        if j == 0:
            In.f[i] = N2
            In.space = i
        else:
            In.f[i] = j
for i in range(0, N2):
    if (In.f[i] == N2): continue
    In.MD += MDT[i][In.f[i] - 1]
ans = ""
for limit in range(In.MD, LIMIT + 1):
    state = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)

Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Runtime Error):
from sys import stdin
import copy
dx = tuple(1,0,-1,0)
dy = tuple(0,1,0,-1)
dir = "ruld"
N = 4
N2 = 16
LIMIT = 50
MDT = ((0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
        (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
        (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
        (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
        (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
        (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
        (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
        (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
        (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
        (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
        (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
        (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
        (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
        (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
        (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
        (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0))
class Puzzle():
    def __init__(self):
        self.f = [0] * N2
        self.space, self.MD = 0, 0
state = Puzzle()
limit = 0
path = [0] * LIMIT
def dfs(depth, prev, limit, state, path):
    if state.MD == 0: return True
    if depth + state.MD > limit: return False
    sx = state.space // N
    sy = state.space % N
    tmp = Puzzle()
    for r in range(4):
        tx = sx + dx[r]
        ty = sy + dy[r]
        if tx < 0 or tx >= N or ty < 0 or ty >= N: continue
        if max(prev, r) - min(prev, r) == 2: continue
        tmp = copy.deepcopy(state)
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1]
        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1]
        state.f[tx * N + ty], state.f[sx * N + sy] = state.f[sx * N + sy], state.f[tx * N + ty]
        state.space = tx * N + ty
        if dfs(depth + 1, r, limit, state, path):
            path[depth] = r
            return True
        state = copy.deepcopy(tmp)
    return False
In = Puzzle()
for k in range(N2 // 4):
    for n, j in enumerate(map(int, stdin.readline().split())):
        i = k * 4 + n
        if j == 0:
            In.f[i] = N2
            In.space = i
        else:
            In.f[i] = j
for i in range(0, N2):
    if (In.f[i] == N2): continue
    In.MD += MDT[i][In.f[i] - 1]
ans = ""
for limit in range(In.MD, LIMIT + 1):
    state = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)

Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import copy
dx = 1,0,-1,0
dy = 0,1,0,-1
dir = "ruld"
N = 4
N2 = 16
LIMIT = 50
MDT = ((0,1,2,3,1,2,3,4,2,3,4,5,3,4,5,6),
        (1,0,1,2,2,1,2,3,3,2,3,4,4,3,4,5),
        (2,1,0,1,3,2,1,2,4,3,2,3,5,4,3,4),
        (3,2,1,0,4,3,2,1,5,4,3,2,6,5,4,3),
        (1,2,3,4,0,1,2,3,1,2,3,4,2,3,4,5),
        (2,1,2,3,1,0,1,2,2,1,2,3,3,2,3,4),
        (3,2,1,2,2,1,0,1,3,2,1,2,4,3,2,3),
        (4,3,2,1,3,2,1,0,4,3,2,1,5,4,3,2),
        (2,3,4,5,1,2,3,4,0,1,2,3,1,2,3,4),
        (3,2,3,4,2,1,2,3,1,0,1,2,2,1,2,3),
        (4,3,2,3,3,2,1,2,2,1,0,1,3,2,1,2),
        (5,4,3,2,4,3,2,1,3,2,1,0,4,3,2,1),
        (3,4,5,6,2,3,4,5,1,2,3,4,0,1,2,3),
        (4,3,4,5,3,2,3,4,2,1,2,3,1,0,1,2),
        (5,4,3,4,4,3,2,3,3,2,1,2,2,1,0,1),
        (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0))
class Puzzle():
    def __init__(self):
        self.f = [0] * N2
        self.space, self.MD = 0, 0
state = Puzzle()
limit = 0
path = [0] * LIMIT
def dfs(depth, prev, limit, state, path):
    if state.MD == 0: return True
    if depth + state.MD > limit: return False
    sx = state.space // N
    sy = state.space % N
    tmp = Puzzle()
    for r in range(4):
        tx = sx + dx[r]
        ty = sy + dy[r]
        if tx < 0 or tx >= N or ty < 0 or ty >= N: continue
        if max(prev, r) - min(prev, r) == 2: continue
        tmp = copy.deepcopy(state)
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1]
        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1]
        state.f[tx * N + ty], state.f[sx * N + sy] = state.f[sx * N + sy], state.f[tx * N + ty]
        state.space = tx * N + ty
        if dfs(depth + 1, r, limit, state, path):
            path[depth] = r
            return True
        state = copy.deepcopy(tmp)
    return False
In = Puzzle()
for k in range(N2 // 4):
    for n, j in enumerate(map(int, stdin.readline().split())):
        i = k * 4 + n
        if j == 0:
            In.f[i] = N2
            In.space = i
        else:
            In.f[i] = j
for i in range(0, N2):
    if (In.f[i] == N2): continue
    In.MD += MDT[i][In.f[i] - 1]
ans = ""
for limit in range(In.MD, LIMIT + 1):
    state = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)

Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
def g(i, j, a):
    t = a // (16 ** j) % 16
    return a - t * (16 ** j) + t * (16 ** i)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero, 1), (0, goal, 0, 0)]
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = heappop(dp)
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            heappush(dp, (cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
def g(i, j, a):
    t = a // (16 ** j) % 16
    return a - t * (16 ** j) + t * (16 ** i)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(start, zero, -1)]
    for i in range(1, 46):
        dp0 = []
        while dp:
            M, space, lower = dp.pop()
            for nyx in m[space]:
                if nyx != lower:
                    key = g(space, nyx, M)
                    if key == goal:
                        return i
                    dp0.append((key, nyx, space))
        dp = dp0
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
def solve():
    board = sum((list(map(int, input().split())) for _ in range(4)), [])
    zero = board.index(0)
    if board == GOAL:
        return 0
    def df_lower_search(limit, move, space, before):
        if move == limit:
            if board == GOAL:
                return True
        else:
            for i in m[space]:
                if i == before:
                    continue
                p = board[i]
                board[space] = p
                board[i] = 0
                if move + 1 <= limit:
                    if df_lower_search(limit, move + 1, i, space):
                        return True
                board[space] = 0
                board[i] = p
    for l in range(1, 46):
        if df_lower_search(l, 0, zero, None):
            return l
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = deque([(estimation_init, board_init, blank_init)])
visited = set()
while True:
    estimation, board, blank = queue.popleft()
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        queue.append((new_estimation, new_board, new_blank))


Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
def g(i, j, a):
    t = (a >> 4 * j) % 16
    return a - (t << 4 * j) + (t << 4 * i)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Runtime Error):
from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
def g(i, j, a):
    t = (a >> 4 * j) % 16
    return a - (t << 4 * j) + (t << 4 * i)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            TABLE.append(key)
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop
from collections import deque
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
def g(i, j, a):
    t = (a >> 4 * j) % 16
    return a - (t << 4 * j) + (t << 4 * i)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            TABLE.add(key)
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
def g(i, j, a):
    t = (a >> 4 * j) % 16
    return a - (t << 4 * j) + (t << 4 * i)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            TABLE.add(key)
            if cnt > 45:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
manhattan = (0, 1, 2, 3,
             1, 2, 3, 4,
             2, 3, 4, 5,
             3, 4, 5, 6)
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        cnt += 1
        for nyx in m[yx]:
            num = (M >> 4 * nyx) & 15
            key = M - (num << 4 * nyx) + (num << 4 * yx)
            if key == goal:
                return cnt
            if key in TABLE:
                continue
            TABLE.add(key)
            new_cnt = cnt + manhattan[nyx]
            if new_cnt > 45:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop
N = 4
m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
goal = 0x123456789abcdef0
manhattan = (
 (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6),
 (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5),
 (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4),
 (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3),
 (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5),
 (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4),
 (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3),
 (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2),
 (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4),
 (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3),
 (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2),
 (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1),
 (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3),
 (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2),
 (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1),
 (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0))
def solve():
    MAP = sum((input().split() for _ in range(N)), [])
    start = int("".join(f"{int(i):x}" for i in MAP), base=16)
    if start == goal:
        return 0
    zero = 15 - MAP.index("0")
    dp = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        cnt += 1
        for nyx in m[yx]:
            num = (M >> 4 * nyx) & 15
            key = M - (num << 4 * nyx) + (num << 4 * yx)
            if key == goal:
                return cnt
            if key in TABLE:
                continue
            TABLE.add(key)
            new_cnt = cnt - manhattan[nyx][num] + manhattan[yx][num]
            if new_cnt > 45:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heapify, heappush, heappop
from copy import deepcopy, copy
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
dir = ('r', 'u', 'l', 'd')
N = 4
N2 = 16
LIMIT = 46
MDT = tuple(tuple(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):
        self.f = []
        self.space, self.MD = 0, 0
state = Puzzle()
path = [0] * LIMIT
def getAllMD(pz):
    global MDT
    sum_mdt = 0
    for i in range(N2):
        if pz.f[i] == N2:
            continue
        sum_mdt += MDT[i][pz.f[i] - 1]
    return sum_mdt
def dfs(depth, prev, limit, state, path):
    if state.MD == 0:
        return True
    if depth + state.MD > limit:
        return False
    sx = state.space // N
    sy = state.space % N
    for r in range(4):
        tx = sx + dx[r]
        ty = sy + dy[r]
        if tx < 0 or tx >= N or ty < 0 or ty >= N:
            continue
        if max(prev, r) - min(prev, r) == 2:
            continue
        tmp = deepcopy(state)
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1]
        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1]
        state.f[tx * N + ty], state.f[sx * N + sy] = state.f[sx * N + sy], state.f[tx * N + ty]
        state.space = tx * N + ty
        if dfs(depth + 1, r, limit, state, path):
            return True
        state = deepcopy(tmp)
    return False
def iterative_deepening(pin, state, path):
    pin.MD = getAllMD(pin)
    ans = ""
    for limit in range(pin.MD, LIMIT + 1):
        state = deepcopy(pin)
        if dfs(0, -100, limit, state, path):
            return limit
    return "unsolvable"
in0 = Puzzle()
in0.f = sum([list(map(int, input().split())) for _ in range(N)], [])
t = in0.f.index(0)
in0.f[t] = N2
in0.space = t
print(iterative_deepening(in0, state, path))



Fixed submission:
from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))