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

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 = 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: Wrong Answer

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 > max_heauristic:
            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: Wrong Answer

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

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

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 max_heauristic < 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: Wrong Answer

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 = {"start":[], "goal":[]}
hq.heapify(queue["start"])
hq.heapify(queue["goal"])
hq.heappush(queue["start"], [heauristic(ini_state, "start"), ini_state, start_x, start_y, 0, "start"])
hq.heappush(queue["goal"], [heauristic(end_state, "goal"), end_state, WIDTH - 1, WIDTH - 1, 0, "goal"])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = defaultdict(dict)
visited["start"][hashnum(ini_state)] = [0, "open", "start"]
visited["goal"][end_hash] = [0, "open", "goal"]
answer = float("inf")
choose = ["start", "goal"]
ch_i = 0
if hashnum(ini_state) == answer:
    print(0)
else:
    while queue["start"] and queue["goal"]:
        q = hq.heappop(queue[choose[ch_i]])
        ch_i = (ch_i + 1) % 2
        heauristic_sum_cost, state, zero_x, zero_y, now_cost, direction = q
        here = hashnum(state)
        if here not in visited[direction] or visited[direction][here][1] == "open":
            visited[direction][here][1] = "close"
            try:
                if visited["start"][here][1] == visited["goal"][here][1] == "close":
                    # print(heauristic_sum_cost)
                    break
            except:
                pass
            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 not in visited[direction]:
                        estimated_cost = heauristic(new_state, direction)
                        visited[direction][perm] = [now_cost + 1, "open", direction]
                        hq.heappush(queue[direction], [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
                    elif now_cost + 1 < visited[direction][perm][0]:
                        visited[direction][perm][0] = now_cost + 1
                        estimated_cost = heauristic(new_state, direction)
                        if visited[direction][perm][1] == "close":
                            visited[direction][perm][1] = "open"
                        hq.heappush(queue[direction], [estimated_cost + now_cost + 1, new_state, new_x, new_y, now_cost + 1, direction])
    same_keys = set(visited["goal"].keys()) & set(visited["start"].keys())
    # print(same_keys)
    for i in same_keys:
        answer = min(answer, visited["start"][i][0] + visited["goal"][i][0])
    print(answer)

Submission status: Wrong Answer

Solution code:
import heapq

def d_manhattan(node_list):
    s = 0
    for i in range(15):
        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:
            y_now = 3
        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)

Submission status: Wrong Answer

Solution code:
print("aa")

Submission status: Wrong Answer

Solution code:
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 = [(start, 0, zero)]
    TABLE = {start}
    while dp:
        M, cnt, 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, (key, cnt, nyx))
def MAIN():
    print(solve())
MAIN()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys;
import heapq

def iterative(i,j):
    q = []
    heapq.heappush(q,(sumcost,(0,i,j,0,puz)))
    global finding

    while len(q):
        cost, items = heapq.heappop(q)
        c_depth = items[0]
        _i = items[1]
        _j = items[2]
        prev_move = items[3]
        c_puz = items[4]
        _sum_cost = cost - c_depth
        if(_sum_cost == 0):
            finding = 1
            print(c_depth)
            break
        if(cost > depth):
            continue

        c_cost = HS(_i,_j,c_puz[_i*3+_j])

        if(_i != 0 and prev_move != 1):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i-1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i-1,_j,c_puz[(_i-1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i-1,_j,swap_puz[(_i-1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i-1,_j,2,swap_puz)))
        if(_i != 3 and prev_move != 2):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i+1,_j)
            n_cost = cost+1+checkCost(c_cost,HS(_i+1,_j,c_puz[(_i+1)*3+_j]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i+1,_j,swap_puz[(_i+1)*3+_j]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i+1,_j,1,swap_puz,)))
        if(_j != 0 and prev_move != 3):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j-1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j-1,c_puz[_i*3+_j-1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j-1,swap_puz[_i*3+_j-1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j-1,4,swap_puz)))
        if(_j != 3 and prev_move != 4):
            swap_puz = swapPuz(c_puz[0:],_i,_j,_i,_j+1)
            n_cost = cost+1+checkCost(c_cost,HS(_i,_j+1,c_puz[_i*3+_j+1]),HS(_i,_j,swap_puz[_i*3+_j]),HS(_i,_j+1,swap_puz[_i*3+_j+1]))
            if(n_cost <= depth):
                heapq.heappush(q,(n_cost,(c_depth+1,_i,_j+1,3,swap_puz)))

def checkCost(c_cost,m_cost,c2_cost,m2_cost):
    return c2_cost - c_cost + m2_cost - m_cost

def sumCost(puz):
    value = 0
    for i in range(4):
        value += HS(i,0,puz[i*4])
        value += HS(i,1,puz[i*4+1])
        value += HS(i,2,puz[i*4+2])
        value += HS(i,2,puz[i*4+3])
    return value

def HS(i,j,num):
    if(num != 0):
        k = num-1
    else:
        k = 15
    ki = (int)(k/4)
    kj = k - ki*4
    value = abs(i-ki)+abs(j-kj)
    return value


def swapPuz(c_puz, i, j, i2,j2):
    c_puz[i2*4+j2],c_puz[i*4+j] = c_puz[i*4+j],c_puz[i2*4+j2]
    return c_puz

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

for i in range(4):
    puz[i*4],puz[i*4+1],puz[i*4+2],puz[i*4+3] = map(int, input().split());
    if(puz[i*4] == 0):
        i_start,j_start = i,0
    elif(puz[i*4+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*4+2] == 0):
        i_start,j_start = i,2
    elif(puz[i*4+3] == 0):
        i_start,j_start = i,3

sumcost = sumCost(puz)

finding = 0
depth = 0
while True:
    if(finding == 1 or depth > 45):
        break
    iterative(i_start,j_start)
    depth+=1