Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from heapq import heappush, heappop

def get_patten(B):
    return ''.join(map(str, B))

def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C

def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C

def change_top(index, B):
    C = B.copy()
    C[index], C[index - 4] = C[index - 4], C[index]
    return C

def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 4] = C[index + 4], C[index]
    return C

def get_diff(B):
    diff = 0
    for i in range(16):
        if i == 0:
            place = 15
        else:
            place = i - 1
        index = B.index(i)
        
        d = abs(place - index) 
        if d >= 4:
            diff += (d // 4) + (d % 4)
        elif place // 4 == index // 4:
            diff += d
        elif d == 0:
            continue
        else: # d = 1 or 2 or 3
            diff += 1 + (4 - d)

    return diff

# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))

q = []
diff = get_diff(boad)
# (diff, boad, prev, count)
heappush(q, (diff + 0, boad, None, 0))

while len(q) > 0:
    diff_count, B, prev, count = heappop(q)
    if diff_count > 45:
        continue

    p = get_patten(B)
    if p == '1234567891011121314150':
        print(count)
        exit()

    index = B.index(0)

    if index % 4 != 0 and prev != 'right':
        C = change_left(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'left', count + 1))

    if index % 4 != 3 and prev != 'left':
        C = change_right(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'right', count + 1))

    if index >= 4 and prev != 'bottom':
        C = change_top(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'top', count + 1))

    if index <= 11 and prev != 'top':
        C = change_bottom(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'bottom', count + 1))

Fixed submission:
#!/usr/bin/python3
from heapq import heappush, heappop
solution = [i + 1 for i in range(15)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = (
    (1, 4),
    (0, 2, 5),
    (1, 6, 3),
    (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)
        )

distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0, 0, 0),
    (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 get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[v][i]
    return diff
 
def get_next_board(board, space, prev):
    for nxt in neighbor[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt

def answer_is_odd(board):
    return sum(divmod(board.index(0), 4)) % 2

def search(board):
    lower = get_diff(board)
    start_depth = lower
    if (lower % 2) ^ answer_is_odd(board):
        start_depth += 1
    for limit in range(start_depth, MAX_DEPTH + 1, 2):
        get_next(board, limit, 0, board.index(0), None, lower)
        if count > 0:
            return limit

def get_next(board, limit, move, space, prev, lower):
    if move == limit:
        if board == solution:
            global count
            count += 1
    else:
        for b, nxt in get_next_board(board, space, prev):
            p = board[nxt]
            new_lower = lower - distance[p][nxt] + distance[p][space]
            if new_lower + move <= limit:
                get_next(b, limit, move + 1, nxt, space, new_lower)

# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))
print(search(boad))
exit()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from heapq import heappush, heappop
solution = [i + 1 for i in range(15)]
solution.append(0)

def get_patten(B):
    return ''.join(map(str, B))

def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C

def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C

def change_top(index, B):
    C = B.copy()
    C[index], C[index - 4] = C[index - 4], C[index]
    return C

def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 4] = C[index + 4], C[index]
    return C

def get_diff(B):
    index_list = [0] * 16
    for i, v in enumerate(B):
        index_list[v] = i

    diff = 0
    for i, v in enumerate(solution):
        index = index_list[v]
        d = abs(i - index)
        if d >= 4:
            diff += (d // 4) + (d % 4)
        elif i // 4 == index // 4:
            diff += d
        elif d == 0:
            continue
        else: # d = 1 or 2 or 3
            diff += 1 + (4 - d)

    return diff


def get_diff_old(B):
    diff = 0
    for i in range(16):
        if i == 0:
            place = 15
        else:
            place = i - 1
        index = B.index(i)
        
        d = abs(place - index) 
        if d >= 4:
            diff += (d // 4) + (d % 4)
        elif place // 4 == index // 4:
            diff += d
        elif d == 0:
            continue
        else: # d = 1 or 2 or 3
            diff += 1 + (4 - d)

    return diff

def judge(B):
    for i in range(16):
        if solution[i] != B[i]:
            return False
    return True


# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))

q = []
diff = get_diff(boad)
exist = set()
# (diff, boad, prev, count)
heappush(q, (diff + 0, boad, None, 0))
exist.add(get_patten(boad))

while len(q) > 0:
    diff_count, B, prev, count = heappop(q)
    if diff_count > 45:
        continue

    if judge(B) == True:
        print(count)
        exit()

    index = B.index(0)

    if index % 4 != 0 and prev != 'right':
        C = change_left(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'left', count + 1))

    if index % 4 != 3 and prev != 'left':
        C = change_right(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'right', count + 1))

    if index >= 4 and prev != 'bottom':
        C = change_top(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'top', count + 1))

    if index <= 11 and prev != 'top':
        C = change_bottom(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'bottom', count + 1))

Fixed submission:
#!/usr/bin/python3
from heapq import heappush, heappop
solution = [i + 1 for i in range(15)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = (
    (1, 4),
    (0, 2, 5),
    (1, 6, 3),
    (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)
        )

distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0, 0, 0),
    (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 get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[v][i]
    return diff
 
def get_next_board(board, space, prev):
    for nxt in neighbor[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt

def answer_is_odd(board):
    return sum(divmod(board.index(0), 4)) % 2

def search(board):
    lower = get_diff(board)
    start_depth = lower
    if (lower % 2) ^ answer_is_odd(board):
        start_depth += 1
    for limit in range(start_depth, MAX_DEPTH + 1, 2):
        get_next(board, limit, 0, board.index(0), None, lower)
        if count > 0:
            return limit

def get_next(board, limit, move, space, prev, lower):
    if move == limit:
        if board == solution:
            global count
            count += 1
    else:
        for b, nxt in get_next_board(board, space, prev):
            p = board[nxt]
            new_lower = lower - distance[p][nxt] + distance[p][space]
            if new_lower + move <= limit:
                get_next(b, limit, move + 1, nxt, space, new_lower)

# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))
print(search(boad))
exit()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from heapq import heappush, heappop
solution = [i + 1 for i in range(15)] + [0]
sol_idx = [15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

distance = (
    (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 get_patten(B):
    return ''.join(map(str, B))

def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C

def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C

def change_top(index, B):
    C = B.copy()
    C[index], C[index - 4] = C[index - 4], C[index]
    return C

def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 4] = C[index + 4], C[index]
    return C

def get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[sol_idx[v]][i]
    return diff


def get_diff_old(B):
    diff = 0
    for i in range(16):
        if i == 0:
            place = 15
        else:
            place = i - 1
        index = B.index(i)
        
        d = abs(place - index) 
        if d >= 4:
            diff += (d // 4) + (d % 4)
        elif place // 4 == index // 4:
            diff += d
        elif d == 0:
            continue
        else: # d = 1 or 2 or 3
            diff += 1 + (4 - d)

    return diff

def judge(B):
    for i in range(16):
        if solution[i] != B[i]:
            return False
    return True


# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))

q = []
diff = get_diff(boad)
exist = set()
# (diff, boad, prev, count)
heappush(q, (diff + 0, boad, None, 0))
exist.add(get_patten(boad))

while len(q) > 0:
    diff_count, B, prev, count = heappop(q)
    if diff_count > 45:
        continue

    if judge(B) == True:
        print(count)
        exit()

    index = B.index(0)

    if index % 4 != 0 and prev != 'right':
        C = change_left(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'left', count + 1))

    if index % 4 != 3 and prev != 'left':
        C = change_right(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'right', count + 1))

    if index >= 4 and prev != 'bottom':
        C = change_top(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'top', count + 1))

    if index <= 11 and prev != 'top':
        C = change_bottom(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'bottom', count + 1))

Fixed submission:
#!/usr/bin/python3
from heapq import heappush, heappop
solution = [i + 1 for i in range(15)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = (
    (1, 4),
    (0, 2, 5),
    (1, 6, 3),
    (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)
        )

distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0, 0, 0),
    (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 get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[v][i]
    return diff
 
def get_next_board(board, space, prev):
    for nxt in neighbor[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt

def answer_is_odd(board):
    return sum(divmod(board.index(0), 4)) % 2

def search(board):
    lower = get_diff(board)
    start_depth = lower
    if (lower % 2) ^ answer_is_odd(board):
        start_depth += 1
    for limit in range(start_depth, MAX_DEPTH + 1, 2):
        get_next(board, limit, 0, board.index(0), None, lower)
        if count > 0:
            return limit

def get_next(board, limit, move, space, prev, lower):
    if move == limit:
        if board == solution:
            global count
            count += 1
    else:
        for b, nxt in get_next_board(board, space, prev):
            p = board[nxt]
            new_lower = lower - distance[p][nxt] + distance[p][space]
            if new_lower + move <= limit:
                get_next(b, limit, move + 1, nxt, space, new_lower)

# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))
print(search(boad))
exit()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python3
from heapq import heappush, heappop
solution = [i + 1 for i in range(15)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

neighbor = (
    (1, 4),
    (0, 2, 5),
    (1, 6, 3),
    (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)
        )

distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0, 0, 0),
    (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 get_patten(B):
    return ''.join(map(str, B))
 
def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C
 
def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C
 
def change_top(index, B):
    C = B.copy()
    C[index], C[index - 4] = C[index - 4], C[index]
    return C
 
def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 4] = C[index + 4], C[index]
    return C

def get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[v][i]
    return diff
 
def get_next(board, index, prev):
    for nxt in neighbor[index]:
        if nxt == prev:
            continue
        b = board[:]
        b[index], b[nxt] = b[nxt], 0
        yield b, nxt
 
# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))
 
q = []
diff = get_diff(boad)
# (diff, boad, prev, count)
heappush(q, (diff + 0, boad, None, 0))
 
while len(q) > 0:
    diff_count, B, prev, count = heappop(q)
    if diff_count > 45:
        continue
 
    if B == solution:
        print(count)
        exit()
 
    index = B.index(0)
 
    if index % 4 != 0 and prev != 'right':
        C = change_left(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'left', count + 1))
 
    if index % 4 != 3 and prev != 'left':
        C = change_right(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'right', count + 1))
 
    if index >= 4 and prev != 'bottom':
        C = change_top(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'top', count + 1))
 
    if index <= 11 and prev != 'top':
        C = change_bottom(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'bottom', count + 1))

Fixed submission:
#!/usr/bin/python3
from heapq import heappush, heappop
solution = [i + 1 for i in range(15)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = (
    (1, 4),
    (0, 2, 5),
    (1, 6, 3),
    (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)
        )

distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0, 0, 0),
    (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 get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[v][i]
    return diff
 
def get_next_board(board, space, prev):
    for nxt in neighbor[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt

def answer_is_odd(board):
    return sum(divmod(board.index(0), 4)) % 2

def search(board):
    lower = get_diff(board)
    start_depth = lower
    if (lower % 2) ^ answer_is_odd(board):
        start_depth += 1
    for limit in range(start_depth, MAX_DEPTH + 1, 2):
        get_next(board, limit, 0, board.index(0), None, lower)
        if count > 0:
            return limit

def get_next(board, limit, move, space, prev, lower):
    if move == limit:
        if board == solution:
            global count
            count += 1
    else:
        for b, nxt in get_next_board(board, space, prev):
            p = board[nxt]
            new_lower = lower - distance[p][nxt] + distance[p][space]
            if new_lower + move <= limit:
                get_next(b, limit, move + 1, nxt, space, new_lower)

# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))
print(search(boad))
exit()