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:
# 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())

Submission status: Time Limit Exceeded

Solution code:
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())

Submission status: Time Limit Exceeded

Solution code:
import copy
def hashnum(state):
    num = ""
    for i in range(4):
        for j in range(4):
            num += str(state[i][j])
    return num

answer = "1234567891011121314150"
ini_state = []
for i in range(4):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
queue = [[ini_state, zero_x, zero_y, 0], [end_state, 3, 3, 1]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
if hashnum(ini_state) == answer:
    print(0)
else:
    visited[hashnum(ini_state)] = [0, 0]
    visited[answer] = [0, 1]
    trial = 0
    ended = 0
    while queue:
        new_queue = []
        trial += 1
        for q in queue:
            if ended:
                break
            state, zero_x, zero_y, direction = q
            for i in range(len(dx)):
                new_state = copy.deepcopy(state)
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < 4 and 0 <= new_y < 4:
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][1]:
                        print(trial + visited[perm][0])
                        ended = 1
                        break
                    elif perm not in visited:
                        visited[perm] = [trial, direction]
                        new_queue.append([new_state, new_x, new_y, direction])
        queue = new_queue

Submission status: Time Limit Exceeded

Solution code:
import copy
import heapq as hq
WIDTH = 4

def hashnum(state):
    num = ""
    for i in range(WIDTH):
        for j in range(WIDTH):
            num += str(state[i][j])
    return num

def heauristic(here_x, here_y):
    return abs((WIDTH - 1) - here_x) + abs((WIDTH - 1) - here_y)

answer = "1234567891011121314150"
ini_state = []
for i in range(WIDTH):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
end_hash = hashnum(end_state)
queue = []
hq.heapify(queue)
hq.heappush(queue, [0, ini_state, zero_x, zero_y, 0, "start"])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
visited[hashnum(ini_state)] = [0, "open", "start"]
if hashnum(ini_state) == answer:
    print(0)
else:
    trial = 0
    while queue:
        q = hq.heappop(queue)
        heauristic_sum_cost, state, zero_x, zero_y, now_cost, direction = q
        here = hashnum(state)
        if here == end_hash:
            print(now_cost)
            break
        if here not in visited or visited[here][1] == "open":
            visited[here][1] = "close"
            for i in range(len(dx)):
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < WIDTH and 0 <= new_y < WIDTH:
                    new_state = copy.deepcopy(state)
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm not in visited:
                        estimated_cost = heauristic(zero_x, zero_y)
                        visited[perm] = [now_cost + 1, "open", direction]
                        hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, "start"])
                    elif now_cost < visited[perm][0]:
                        visited[perm][0] = now_cost + 1
                        if visited[perm][1] == "close":
                            visited[perm][1] = "open"
                            hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, "start"])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy
import heapq as hq
WIDTH = 4

def hashnum(state):
    num = ""
    for i in range(WIDTH):
        for j in range(WIDTH):
            num += str(state[i][j])
    return num

def make_heauristic_table(state):
    answer = defaultdict(list)
    for i in range(WIDTH):
        for j in range(WIDTH):
            answer[state[i][j]] = [j, i]
    return answer

def heauristic(state, direction):
    if direction == "start":
        global end_eval
        evaluation = end_eval
    else:
        global start_eval
        evaluation = start_eval
    estimated_cost = 0
    for i in range(WIDTH):
        for j in range(WIDTH):
            this = state[i][j]
            if this == 0:
                continue
            here = evaluation[this]
            estimated_cost += abs(here[0] - j) + abs(here[1] - i)
    return estimated_cost

answer = "1234567891011121314150"
ini_state = []
start_x = -1
start_y = -1
for i in range(WIDTH):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        start_x, start_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
end_hash = hashnum(end_state)
end_eval = make_heauristic_table(end_state)
start_eval = make_heauristic_table(ini_state)
queue = []
hq.heapify(queue)
hq.heappush(queue, [heauristic(ini_state, "start"), ini_state, start_x, start_y, 0, "start"])
hq.heappush(queue, [heauristic(end_state, "goal"), end_state, WIDTH - 1, WIDTH - 1, 0, "goal"])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
visited[hashnum(ini_state)] = [0, "open", "start"]
visited[end_hash] = [0, "open", "goal"]
answer = float("inf")
if hashnum(ini_state) == answer:
    print(0)
else:
    while queue:
        q = hq.heappop(queue)
        heauristic_sum_cost, state, zero_x, zero_y, now_cost, direction = q
        if heauristic_sum_cost > answer:
            break
        here = hashnum(state)
        if here not in visited or visited[here][1] == "open":
            visited[here][1] = "close"
            for i in range(4):
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < WIDTH and 0 <= new_y < WIDTH:
                    new_state = copy.deepcopy(state)
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][2]:
                        answer = min(answer, now_cost + visited[perm][0] + 1)
                    elif perm not in visited:
                        estimated_cost = heauristic(new_state, direction)
                        visited[perm] = [now_cost + 1, "open", direction]
                        hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
                    elif now_cost + 1 < visited[perm][0]:
                        visited[perm][0] = now_cost + 1
                        estimated_cost = heauristic(new_state, direction)
                        if visited[perm][1] == "close":
                            visited[perm][1] = "open"
                            hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy
import heapq as hq
WIDTH = 4

def hashnum(state):
    num = ""
    for i in range(WIDTH):
        for j in range(WIDTH):
            num += str(state[i][j])
    return num

def make_heauristic_table(state):
    answer = defaultdict(list)
    for i in range(WIDTH):
        for j in range(WIDTH):
            answer[state[i][j]] = [j, i]
    return answer

def heauristic(state, direction):
    if direction == "start":
        global end_eval
        evaluation = end_eval
    else:
        global start_eval
        evaluation = start_eval
    estimated_cost = 0
    for i in range(WIDTH):
        for j in range(WIDTH):
            this = state[i][j]
            if this == 0:
                continue
            here = evaluation[this]
            estimated_cost += abs(here[0] - j) + abs(here[1] - i)
    return estimated_cost

answer = "1234567891011121314150"
ini_state = []
start_x = -1
start_y = -1
for i in range(WIDTH):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        start_x, start_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
end_hash = hashnum(end_state)
end_eval = make_heauristic_table(end_state)
start_eval = make_heauristic_table(ini_state)
queue = []
hq.heapify(queue)
hq.heappush(queue, [heauristic(ini_state, "start"), ini_state, start_x, start_y, 0, "start"])
hq.heappush(queue, [heauristic(end_state, "goal"), end_state, WIDTH - 1, WIDTH - 1, 0, "goal"])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
visited[hashnum(ini_state)] = [0, "open", "start"]
visited[end_hash] = [0, "open", "goal"]
answer = float("inf")
max_heauristic = float("inf")
if hashnum(ini_state) == answer:
    print(0)
else:
    while queue:
        q = hq.heappop(queue)
        heauristic_sum_cost, state, zero_x, zero_y, now_cost, direction = q
        if heauristic_sum_cost >= answer:
            break
        here = hashnum(state)
        if here not in visited or visited[here][1] == "open":
            visited[here][1] = "close"
            for i in range(4):
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < WIDTH and 0 <= new_y < WIDTH:
                    new_state = copy.deepcopy(state)
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][2]:
                        answer = min(answer, now_cost + visited[perm][0] + 1)
                        max_heauristic = heauristic_sum_cost
                    elif perm not in visited:
                        estimated_cost = heauristic(new_state, direction)
                        visited[perm] = [now_cost + 1, "open", direction]
                        hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
                    elif now_cost + 1 < visited[perm][0]:
                        visited[perm][0] = now_cost + 1
                        estimated_cost = heauristic(new_state, direction)
                        if visited[perm][1] == "close":
                            visited[perm][1] = "open"
                            hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy
import heapq as hq
WIDTH = 4

def hashnum(state):
    num = ""
    for i in range(WIDTH):
        for j in range(WIDTH):
            num += str(state[i][j])
    return num

def make_heauristic_table(state):
    answer = defaultdict(list)
    for i in range(WIDTH):
        for j in range(WIDTH):
            answer[state[i][j]] = [j, i]
    return answer

def heauristic(state, direction):
    if direction == "start":
        global end_eval
        evaluation = end_eval
    else:
        global start_eval
        evaluation = start_eval
    estimated_cost = 0
    for i in range(WIDTH):
        for j in range(WIDTH):
            this = state[i][j]
            if this == 0:
                continue
            here = evaluation[this]
            estimated_cost += abs(here[0] - j) + abs(here[1] - i)
    return estimated_cost

answer = "1234567891011121314150"
ini_state = []
start_x = -1
start_y = -1
for i in range(WIDTH):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        start_x, start_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
end_hash = hashnum(end_state)
end_eval = make_heauristic_table(end_state)
start_eval = make_heauristic_table(ini_state)
queue = []
hq.heapify(queue)
hq.heappush(queue, [heauristic(ini_state, "start"), ini_state, start_x, start_y, 0, "start"])
hq.heappush(queue, [heauristic(end_state, "goal"), end_state, WIDTH - 1, WIDTH - 1, 0, "goal"])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
visited[hashnum(ini_state)] = [0, "open", "start"]
visited[end_hash] = [0, "open", "goal"]
answer = float("inf")
max_heauristic = float("inf")
if hashnum(ini_state) == answer:
    print(0)
else:
    while queue:
        q = hq.heappop(queue)
        heauristic_sum_cost, state, zero_x, zero_y, now_cost, direction = q
        if heauristic_sum_cost >= answer:
            break
        here = hashnum(state)
        if here not in visited or visited[here][1] == "open":
            visited[here][1] = "close"
            for i in range(4):
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < WIDTH and 0 <= new_y < WIDTH:
                    new_state = copy.deepcopy(state)
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][2]:
                        answer = min(answer, now_cost + visited[perm][0] + 1)
                        if heauristic_sum_cost < queue[0][0]:
                            queue = []
                        max_heauristic = heauristic_sum_cost
                    elif perm not in visited:
                        estimated_cost = heauristic(new_state, direction)
                        visited[perm] = [now_cost + 1, "open", direction]
                        hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
                    elif now_cost + 1 < visited[perm][0]:
                        visited[perm][0] = now_cost + 1
                        estimated_cost = heauristic(new_state, direction)
                        if visited[perm][1] == "close":
                            visited[perm][1] = "open"
                            hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy
import heapq as hq
WIDTH = 4

def hashnum(state):
    num = ""
    for i in range(WIDTH):
        for j in range(WIDTH):
            num += str(state[i][j])
    return num

def make_heauristic_table(state):
    answer = defaultdict(list)
    for i in range(WIDTH):
        for j in range(WIDTH):
            answer[state[i][j]] = [j, i]
    return answer

def heauristic(state, direction):
    if direction == "start":
        global end_eval
        evaluation = end_eval
    else:
        global start_eval
        evaluation = start_eval
    estimated_cost = 0
    for i in range(WIDTH):
        for j in range(WIDTH):
            this = state[i][j]
            if this == 0:
                continue
            here = evaluation[this]
            estimated_cost += abs(here[0] - j) + abs(here[1] - i)
    return estimated_cost

answer = "1234567891011121314150"
ini_state = []
start_x = -1
start_y = -1
for i in range(WIDTH):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        start_x, start_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
end_hash = hashnum(end_state)
end_eval = make_heauristic_table(end_state)
start_eval = make_heauristic_table(ini_state)
queue = []
hq.heapify(queue)
hq.heappush(queue, [heauristic(ini_state, "start"), ini_state, start_x, start_y, 0, "start"])
hq.heappush(queue, [heauristic(end_state, "goal"), end_state, WIDTH - 1, WIDTH - 1, 0, "goal"])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
visited[hashnum(ini_state)] = [0, "open", "start"]
visited[end_hash] = [0, "open", "goal"]
answer = float("inf")
max_heauristic = float("inf")
if hashnum(ini_state) == answer:
    print(0)
else:
    while queue:
        q = hq.heappop(queue)
        heauristic_sum_cost, state, zero_x, zero_y, now_cost, direction = q
        if heauristic_sum_cost >= answer:
            break
        here = hashnum(state)
        if here not in visited or visited[here][1] == "open":
            visited[here][1] = "close"
            for i in range(4):
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < WIDTH and 0 <= new_y < WIDTH:
                    new_state = copy.deepcopy(state)
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][2]:
                        answer = min(answer, now_cost + visited[perm][0] + 1)
                        if heauristic_sum_cost < queue[0][0]:
                            queue = []
                            break
                        max_heauristic = heauristic_sum_cost
                    elif perm not in visited:
                        estimated_cost = heauristic(new_state, direction)
                        visited[perm] = [now_cost + 1, "open", direction]
                        hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
                    elif now_cost + 1 < visited[perm][0]:
                        visited[perm][0] = now_cost + 1
                        estimated_cost = heauristic(new_state, direction)
                        if visited[perm][1] == "close":
                            visited[perm][1] = "open"
                            hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy
import heapq as hq
WIDTH = 4

def hashnum(state):
    num = ""
    for i in range(WIDTH):
        for j in range(WIDTH):
            num += str(state[i][j])
    return num

def make_heauristic_table(state):
    answer = defaultdict(list)
    for i in range(WIDTH):
        for j in range(WIDTH):
            answer[state[i][j]] = [j, i]
    return answer

def heauristic(state, direction):
    if direction == "start":
        global end_eval
        evaluation = end_eval
    else:
        global start_eval
        evaluation = start_eval
    estimated_cost = 0
    for i in range(WIDTH):
        for j in range(WIDTH):
            this = state[i][j]
            if this == 0:
                continue
            here = evaluation[this]
            estimated_cost += abs(here[0] - j) + abs(here[1] - i)
    return estimated_cost

answer = "1234567891011121314150"
ini_state = []
start_x = -1
start_y = -1
for i in range(WIDTH):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        start_x, start_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]
end_hash = hashnum(end_state)
end_eval = make_heauristic_table(end_state)
start_eval = make_heauristic_table(ini_state)
queue = []
hq.heapify(queue)
hq.heappush(queue, [heauristic(ini_state, "start"), ini_state, start_x, start_y, 0, "start"])
hq.heappush(queue, [heauristic(end_state, "goal"), end_state, WIDTH - 1, WIDTH - 1, 0, "goal"])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
visited[hashnum(ini_state)] = [0, "open", "start"]
visited[end_hash] = [0, "open", "goal"]
answer = float("inf")
max_heauristic = float("inf")
if hashnum(ini_state) == answer:
    print(0)
else:
    while queue:
        q = hq.heappop(queue)
        heauristic_sum_cost, state, zero_x, zero_y, now_cost, direction = q
        # if heauristic_sum_cost >= answer:
        #     break
        here = hashnum(state)
        if here not in visited or visited[here][1] == "open":
            visited[here][1] = "close"
            for i in range(4):
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < WIDTH and 0 <= new_y < WIDTH:
                    new_state = copy.deepcopy(state)
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][2]:
                        answer = min(answer, now_cost + visited[perm][0] + 1)
                        if heauristic_sum_cost < queue[0][0]:
                            queue = []
                            break
                        # max_heauristic = heauristic_sum_cost
                    elif perm not in visited:
                        estimated_cost = heauristic(new_state, direction)
                        visited[perm] = [now_cost + 1, "open", direction]
                        hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
                    elif now_cost + 1 < visited[perm][0]:
                        visited[perm][0] = now_cost + 1
                        estimated_cost = heauristic(new_state, direction)
                        if visited[perm][1] == "close":
                            visited[perm][1] = "open"
                            hq.heappush(queue, [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        x_goal = i%4
        y_goal = i//4
        x_now = (node_list[i] - 1)%4
        y_now = (node_list[i] - 1)//4
        if y_now == -1:
            continue
        dx = abs(x_now - x_goal)
        dy = abs(y_now - y_goal)
        s += dx + dy
    return s

def moveNodeE(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 1] = node_tmp[space + 1], node_tmp[space]
    return node_tmp
def moveNodeW(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 1] = node_tmp[space - 1], node_tmp[space]
    return node_tmp
def moveNodeN(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 4] = node_tmp[space - 4], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 4] = node_tmp[space + 4], node_tmp[space]
    return node_tmp

class board:
    def __init__(self, node_list, g):
        self.node = node_list
        self.space = node_list.index(0)
        self.g = g
        self.h = d_manhattan(node_list)
        self.f = self.g + self.h

    def makeBoard(self):
        space = self.space
        cost_now = self.f
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNodeE(self.node, space)
            yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s < 3:
            node_tmp = moveNodeS(self.node, space)
            yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            yield board(node_tmp, self.g + 1)

b_open = []
n_close = {}
n_goal = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
n_start = []

for i in range(4):
    inp = list(map(int, input().split()))
    n_start.extend(inp)

b_start = board(n_start, 0)
heapq.heappush(b_open, (b_start.f, b_start.h, 0, b_start))

i = 0
while b_open:
    _, _, _, b_now = heapq.heappop(b_open)
    if b_now.node == n_goal:
        b_goal = b_now
        break
    n_close["".join(map(str, b_now.node))] = i
    for b_new in b_now.makeBoard():
        if "".join(map(str, b_new.node)) in n_close:
            continue
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.g)