Buggy python submission (verdict: Time Limit Exceeded):
# Manhattan Distance
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)
)

def get_distance(board):
    sd = 0
    for i in range(16):
        p = board[i]
        if p == 0:
            continue
        sd += distance[p][i]
    return sd

adjacent = (
    (1, 4),         # 0
    (0, 2, 5),      # 1
    (1, 3, 6),      # 2
    (2, 7),         # 3
    (0, 5, 8),      # 4
    (1, 4, 6, 9),   # 5
    (2, 5, 7, 10),  # 6
    (3, 6, 11),     # 7
    (4, 9, 12),     # 8
    (5, 8, 10, 13), # 9
    (6, 9, 11, 14), # 10
    (7, 10, 15),    # 11
    (8, 13),        # 12
    (9, 12, 14),    # 13
    (10, 13, 15),   # 14
    (11, 14)        # 15
)

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

import sys
import heapq

OPEN = False
CLOSE = True

# A* algorithm
def solve():
    board = list(map(int, sys.stdin.read().split()))
    #board = [9, 8, 7, 3, 0, 10, 5, 11, 14, 2, 6, 4, 13, 1, 15, 12]
    #board = [1, 6, 15, 0, 14, 11, 5, 7, 10, 9, 8, 3, 2, 13, 12, 4]
    #board = [1, 6, 7, 2, 5, 10, 12, 3, 0, 14, 13, 8, 9, 15, 11, 4]
    h_cost = get_distance(board)
    state = [h_cost, 0, board, OPEN] # state[1] is step.
    
    q = [state] # priority queue
    d = {} # mapping of boards to states
    
    while q:
        state1 = heapq.heappop(q)
        h_cost, step, board, flag = state1
        if flag:
            continue
        if board == GOAL:
            return step
        d[tuple(board)] = state1
        space = board.index(0)
        for i in adjacent[space]:
            p = board[i]
            new_board = board[:]
            new_board[space], new_board[i] = p, 0
            #new_h_cost = h_cost + 1 - distance[p][i] + distance[p][space]
            new_h_cost = step + 1 + get_distance(board)

            key = tuple(new_board)
            if key in d:
                state2 = d[key]
                if step + 1 < state2[1]:
                    #print("check")#
                    if state2[3] == OPEN:
                        state2[3] = CLOSE
                        state2 = [new_h_cost, step + 1, new_board, OPEN]
                        d[key] = state2
                    else:
                        state2[0] = state2[0] - state2[1] + step + 1
                        state2[1] = step + 1
                        state2[3] = OPEN
                    heapq.heappush(q, state2)
            else:
                new_state = [new_h_cost, step + 1, new_board, OPEN]
                heapq.heappush(q, new_state)
                d[key] = new_state

print(solve())

Fixed submission:
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)
)

def get_distance(board):
    sd = 0
    for i in range(16):
        p = board[i]
        if p == 0:
            continue
        sd += distance[p][i]
    return sd

adjacent = (
    (1, 4),         # 0
    (0, 2, 5),      # 1
    (1, 3, 6),      # 2
    (2, 7),         # 3
    (0, 5, 8),      # 4
    (1, 4, 6, 9),   # 5
    (2, 5, 7, 10),  # 6
    (3, 6, 11),     # 7
    (4, 9, 12),     # 8
    (5, 8, 10, 13), # 9
    (6, 9, 11, 14), # 10
    (7, 10, 15),    # 11
    (8, 13),        # 12
    (9, 12, 14),    # 13
    (10, 13, 15),   # 14
    (11, 14)        # 15
)

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

def df_lower_search(limit, move, space, lower, pre_p):
    if move == limit:
        if board == GOAL:
            return True
    else:
        for i in adjacent[space]:
            p = board[i]
            if p == pre_p:
                continue
            board[space] = p
            board[i] = 0
            new_lower = lower - distance[p][i] + distance[p][space]
            if new_lower + move <= limit:
                if df_lower_search(limit, move + 1, i, new_lower, p):
                    return True
            board[space] = 0
            board[i] = p

import sys

board = list(map(int, sys.stdin.read().split()))

s = board.index(0)
e_o = (0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0)

n = get_distance(board)

if e_o[s] != n % 2:
    n += 1

for l in range(n, 46, 2):
    if df_lower_search(l, 0, s, n, None):
        print(l)
        break

Buggy python submission (verdict: Time Limit Exceeded):
def make_distance_table(board):
    table = [[]] + [[None for j in range(16)] for i in range(1, 16)]
    for i, p in enumerate(board):
        if p == 0:
            continue
        x1 = i % 4
        y1 = i // 4
        for j in range(16):
            x2 = j % 4
            y2 = j // 4
            table[p][j] = abs(x1 - x2) + abs(y1 - y2)
    return table

def get_h_cost(board, distance_table):
    h_cost = 0
    for i, p in enumerate(board):
        if p == 0:
            continue
        h_cost += distance_table[p][i]
    return h_cost

adjacent = (
    (1, 4),         # 0
    (0, 2, 5),      # 1
    (1, 3, 6),      # 2
    (2, 7),         # 3
    (0, 5, 8),      # 4
    (1, 4, 6, 9),   # 5
    (2, 5, 7, 10),  # 6
    (3, 6, 11),     # 7
    (4, 9, 12),     # 8
    (5, 8, 10, 13), # 9
    (6, 9, 11, 14), # 10
    (7, 10, 15),    # 11
    (8, 13),        # 12
    (9, 12, 14),    # 13
    (10, 13, 15),   # 14
    (11, 14)        # 15
)

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

FORE = True
BACK = False

import sys

# Bidirectional search using breadth-first search
def solve():
    start = list(map(int, sys.stdin.read().split()))
    if start == GOAL:
        return 0

    d_t_f = make_distance_table(GOAL)
    d_t_b = make_distance_table(start)
    h_cost_f = get_h_cost(start, d_t_f)
    h_cost_b = get_h_cost(GOAL, d_t_b)
    state_f = (h_cost_f, 0, start, FORE)
    state_b = (h_cost_b, 0, GOAL, BACK)

    l1 = [state_f, state_b]
    d = {tuple(start): (FORE, 0), tuple(GOAL): (BACK, 0)}
    while l1:
        l2 = l1[:]
        l1 = []
        for state in l2:
            h_cost, step, board, direction = state
            space = board.index(0)
            for i in adjacent[space]:
                p = board[i]
                new_board = board[:]
                new_board[space], new_board[i] = p, 0

                if direction:
                    distance = d_t_f
                else:
                    distance = d_t_b
                new_h_cost = h_cost + 1 - distance[p][i] + distance[p][space]
                
                key = tuple(new_board)
                if key in d:
                    if d[key][0] != direction:
                        return d[key][1] + step + 1
                elif new_h_cost <= 45:
                    new_state = (new_h_cost, step + 1, new_board, direction)
                    l1.append(new_state)
                    d[key] = (direction, step + 1)

print(solve())

Fixed submission:
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)
)

def get_distance(board):
    sd = 0
    for i in range(16):
        p = board[i]
        if p == 0:
            continue
        sd += distance[p][i]
    return sd

adjacent = (
    (1, 4),         # 0
    (0, 2, 5),      # 1
    (1, 3, 6),      # 2
    (2, 7),         # 3
    (0, 5, 8),      # 4
    (1, 4, 6, 9),   # 5
    (2, 5, 7, 10),  # 6
    (3, 6, 11),     # 7
    (4, 9, 12),     # 8
    (5, 8, 10, 13), # 9
    (6, 9, 11, 14), # 10
    (7, 10, 15),    # 11
    (8, 13),        # 12
    (9, 12, 14),    # 13
    (10, 13, 15),   # 14
    (11, 14)        # 15
)

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

def df_lower_search(limit, move, space, lower, pre_p):
    if move == limit:
        if board == GOAL:
            return True
    else:
        for i in adjacent[space]:
            p = board[i]
            if p == pre_p:
                continue
            board[space] = p
            board[i] = 0
            new_lower = lower - distance[p][i] + distance[p][space]
            if new_lower + move <= limit:
                if df_lower_search(limit, move + 1, i, new_lower, p):
                    return True
            board[space] = 0
            board[i] = p

import sys

board = list(map(int, sys.stdin.read().split()))

s = board.index(0)
e_o = (0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0)

n = get_distance(board)

if e_o[s] != n % 2:
    n += 1

for l in range(n, 46, 2):
    if df_lower_search(l, 0, s, n, None):
        print(l)
        break