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:
#!/usr/bin/python
#coding:utf-8

import sys,heapq
if sys.version_info[0]>=3: raw_input=input

OPEN = 0
CLOSE = 1
FORE = 0
BACK = 1

X=4
Y=4

adjacent=[]
for coor in range(X*Y):
	lst=[]
	x=coor%X
	y=coor//X
	if 0<x: lst.append(coor-1)
	if x<X-1: lst.append(coor+1)
	if 0<y: lst.append(coor-X)
	if y<Y-1: lst.append(coor+X)
	adjacent.append(lst)

def output(a):
	#for i in range(1,len(a)):
	#	for j in range(len(a[i])):
	#		if a[i][j]==0:
	#			print(a[i-1][j])
	#			break
	print(len(a)-1)
def backtrack(x):
	if x is not None:
		return backtrack(x.prev)+[x.board]
	return []
def forwardtrack(x):
	r=[]
	while x is not None:
		r.append(x.board)
		x = x.prev
	return r

def make_distance_table(board, wide):
	size = len(board)
	table = [[0]*size for _ in range(size)]
	for i in range(size):
		p = board[i]
		if p == 0: continue
		x1 = i / wide
		y1 = i % wide
		for j in range(size):
			x2 = j / wide
			y2 = j % wide
			table[p][j] += max(x1 - x2, x2 - x1)
			table[p][j] += max(y1 - y2, y2 - y1)
	return table

def get_distance(board, distance):
	v = 0
	for x in range(X*Y):
		p = board[x]
		if p == 0: continue
		v += distance[p][x]
	return v

class State:
	def __init__(self, board, space, prev, move, dir, kind):
		self.board = board
		self.space = space
		self.prev = prev
		self.move = move
		self.dir = dir
		self.kind = kind
		if dir == FORE:
			dt = start_distance
		else:
			dt = goal_distance
		if prev is None:
			self.cost = move + get_distance(board, dt)
		else:
			p = board[prev.space]
			self.cost = prev.cost + 1 - dt[p][space] + dt[p][prev.space]
	def __lt__(x, y):
		return x.cost<y.cost

def a_star_search(start, goal):
	global start_distance, goal_distance
	q = []
	table ={}
	# start
	start_distance = make_distance_table(goal, X)
	a = State(start, start.index(0), None, 0, FORE, OPEN)
	heapq.heappush(q,a)
	table[tuple(start)] = a
	# goal
	goal_distance = make_distance_table(start, X)
	a = State(goal, goal.index(0), None, 0, BACK, OPEN)
	heapq.heappush(q,a)
	table[tuple(goal)] = a
	while q:
		a = heapq.heappop(q)
		if a.kind == CLOSE: continue
		for x in adjacent[a.space]:
			b = a.board[:]
			b[a.space] = b[x]
			b[x] = 0
			key = tuple(b)
			if key in table:
				c = table[key]
				if a.dir != c.dir:
					if a.dir == FORE:
						output(backtrack(a)+forwardtrack(c))
					else:
						output(backtrack(c)+forwardtrack(a))
					return
			else:
				c = State(b, x, a, a.move + 1, a.dir, OPEN)
				heapq.heappush(q,c)
				table[key] = c
		a.kind = CLOSE

goal = list(range(1,X*Y))+[0]
a = []
try:
    while True:
        a+=[int(e) for e in raw_input().replace('*','0').split()]
except EOFError:
    pass

a_star_search(a, goal)

Submission status: Wrong Answer

Solution code:
from queue import Queue
from collections import namedtuple


def get_offset(x, y):
    return 16 * y + 4 * x


def get_candidate(pid):
    return tuple(pid + move for move in MOVE_CANDIDATE if 0 <= pid + move < 16)


def get_swap_values(orig):
    return {dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest]) for dest in SWAP_CANDIDATE[orig]}


MOVE_CANDIDATE = (-4, -1, 1, 4)
SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))


# print(MOVE_CANDIDATE)
# print(SWAP_CANDIDATE)
# print(OFFSET_MASTER)
# print(SWAP_VALUE_MASTER)


def swap(board, orig, dest):
    dest_val = (board >> OFFSET_MASTER[dest]) & 0b1111
    return board + dest_val * SWAP_VALUE_MASTER[orig][dest]


def put_next_puzzle(is_reverse):
    global puzzles, cache
    puzzle = puzzles[is_reverse].get()
    board, id0, count, prev = puzzle.board, puzzle.id0, puzzle.count, puzzle.prev
    for new_id0 in SWAP_CANDIDATE[id0]:
        if new_id0 == prev:
            continue

        new_board = swap(board, id0, new_id0)
        if new_board in cache[is_reverse]:
            continue
        # print('%x' % board, '%x' % new_board, count)
        if new_board in cache[not is_reverse]:
            return cache[not is_reverse][new_board] + count + 1
        cache[is_reverse][new_board] = count + 1
        puzzles[is_reverse].put(Puzzle(
                board=new_board,
                count=count + 1,
                id0=new_id0,
                prev=id0
        ))
    return -1


CORRECT = 0x0fedcba987654321
Puzzle = namedtuple('Puzzle', 'board count id0 prev')
puzzles = (Queue(), Queue())
cache = ({}, {})
board = 0
id0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        board += v << get_offset(i, j)
        if v == 0:
            id0 = 4 * j + i

puzzles[0].put(Puzzle(board=board, count=0, id0=id0, prev=-1))
cache[0][board] = 0
puzzles[1].put(Puzzle(board=CORRECT, count=0, id0=15, prev=-1))
cache[1][CORRECT] = 0
result = None
is_reverse = False

while True:
    result = put_next_puzzle(is_reverse)
    if result > -1:
        break
    is_reverse = not is_reverse

print(result)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import namedtuple


def get_offset(x, y):
    return 16 * y + 4 * x


def get_candidate(pid):
    def check(pid, move):
        if abs(move) == 1:
            return pid // 4 == (pid + move) // 4
        else:
            return 0 <= pid + move < 16

    return tuple(pid + move for move in MOVE_CANDIDATE if check(pid, move))


def get_swap_values(orig):
    return {dest: (1 << OFFSET_MASTER[orig]) - (1 << OFFSET_MASTER[dest]) for dest in SWAP_CANDIDATE[orig]}


MOVE_CANDIDATE = (-4, -1, 1, 4)
SWAP_CANDIDATE = tuple(get_candidate(pid) for pid in range(16))
OFFSET_MASTER = tuple(get_offset(x, y) for y in range(4) for x in range(4))
SWAP_VALUE_MASTER = tuple(get_swap_values(pid) for pid in range(16))
HEURISTICS = tuple(
        tuple(abs(dest // 4 - orig // 4) + abs(dest % 4 - orig % 4) for dest in range(16)) for orig in range(16))


def swap(board, orig, dest):
    dest_val = (board >> OFFSET_MASTER[dest]) & 0b1111
    return board + dest_val * SWAP_VALUE_MASTER[orig][dest]


def get_sum_heuristics(orig_board, is_reverse):
    global dest_board_dicts
    orig_board_dict = {i: orig_board >> (4 * i) & 0b1111 for i in range(16)}
    dest_board_dict = dest_board_dicts[is_reverse]

    return sum(HEURISTICS[pid][dest_board_dict[val]] for pid, val in orig_board_dict.items())


def put_next_puzzle(is_reverse):
    global puzzles, cache
    (heur, puzzle) = heapq.heappop(puzzles[is_reverse])
    board, id0, count, prev = puzzle.board, puzzle.id0, puzzle.count, puzzle.prev
    for new_id0 in SWAP_CANDIDATE[id0]:
        if new_id0 == prev:
            continue

        new_board = swap(board, id0, new_id0)

        if new_board in cache[not is_reverse]:
            return cache[not is_reverse][new_board].count + count + 1

        new_heur = count + 1 + get_sum_heuristics(new_board, is_reverse)
        if new_board in cache[is_reverse]:
            closed_puzzle = cache[is_reverse][new_board]
            if closed_puzzle.heur <= new_heur:
                continue

        new_puzzle = Puzzle(
                board=new_board,
                count=count + 1,
                id0=new_id0,
                prev=id0,
                trace=puzzle.trace * 16 + new_id0,
                heur=new_heur
        )
        heapq.heappush(puzzles[is_reverse], (new_heur, new_puzzle))
        cache[is_reverse][new_board] = new_puzzle
    return -1


CORRECT = 0x0fedcba987654321
Puzzle = namedtuple('Puzzle', 'board count id0 prev trace heur')
puzzles = ([], [])
cache = ({}, {})
board = 0
id0 = -1

for j in range(4):
    for i, v in enumerate(map(int, input().strip().split())):
        board += v << get_offset(i, j)
        if v == 0:
            id0 = 4 * j + i

dest_board_dicts = (
    {CORRECT >> (4 * i) & 0b1111: i for i in range(16)},
    {board >> (4 * i) & 0b1111: i for i in range(16)}
)
s_heur = get_sum_heuristics(board, False)
g_heur = get_sum_heuristics(CORRECT, True)
s_puzzle = Puzzle(board=board, count=0, id0=id0, prev=-1, trace=0, heur=get_sum_heuristics(board, 0))
g_puzzle = Puzzle(board=CORRECT, count=0, id0=15, prev=-1, trace=0, heur=get_sum_heuristics(CORRECT, 1))
heapq.heappush(puzzles[0], (s_heur, s_puzzle))
heapq.heappush(puzzles[1], (g_heur, g_puzzle))
cache[0][board] = s_puzzle
cache[1][CORRECT] = g_puzzle
result = None
is_reverse = False

while True:
    result = put_next_puzzle(is_reverse)
    if result > -1:
        break
    is_reverse = not is_reverse

print(result)

Submission status: Wrong Answer

Solution code:
import queue
adjacent=(
    (1,4), 
    (0,2,5),
    (1,3,6),
    (2,7),
    (0,5,8),
    (1,4,6,9),
    (2,5,7,10),
    (3,6,11),
    (4,9,12),
    (5,8,10,13),
    (6,9,11,14),
    (7,10,15),
    (8,13),
    (9,12,14),
    (10,13,15),
    (11,14),
)

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):
    v = 0
    for x in range(16):
        p = board[x]
        if p == 0: continue
        v += distance[p][x]
    return v
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,0]

board = []
for i in range(4):
    a,b,c,d = map(int, input().split())
    board += [a,b,c,d]

move_piece = [None] * 46

# ?????????????????????
def id_lower_search(limit, move, space, lower):
    if move == limit:
        if board == GOAL:
            global count
            count += 1
            i = move_piece[1:].index(None)
            print(len(move_piece[1:i + 1]))
    else:
        for x in adjacent[space]:
            p = board[x]
            if move_piece[move] == p: continue
            # ?§?????????????
            board[space] = p
            board[x] = 0
            move_piece[move + 1] = p
            new_lower = lower - distance[p][x] + distance[p][space]
            # ?????????????????????
            if new_lower + move <= limit:
                id_lower_search(limit, move + 1, x, new_lower)
            # ????????????
            board[space] = 0
            board[x] = p

# ??????
count = 0
n = get_distance(board)
for x in range(n, 46):
    id_lower_search(x, 0, board.index(0), n)
    if count > 0: break

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    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, 0]]
queue = [[ini_state, zero_x, zero_y, 0], [end_state, 2, 2, 1]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
visited[hashnum(ini_state)] = [0, 0]
visited[answer] = [0, 1]
trial = 0
while answer not in visited:
    new_queue = []
    trial += 1
    for q in queue:
        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 < 3 and 0 <= new_y < 3:
                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])
                    exit()
                if perm not in visited:
                    visited[perm] = [trial, direction]
                    new_queue.append([new_state, new_x, new_y, direction])
    queue = new_queue

Submission status: Wrong Answer

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, direction):
    if direction == "start":
        return abs((WIDTH - 1) - here_x) + abs((WIDTH - 1) - here_y)
    else:
        global start_x
        global start_y
        return abs(here_x - start_x) + abs(here_y - start_y)

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)
queue = []
hq.heapify(queue)
hq.heappush(queue, [heauristic(start_x, start_y, "start"), ini_state, start_x, start_y, 0, "start"])
hq.heappush(queue, [heauristic(WIDTH - 1, WIDTH - 1, "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"]
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
        here = hashnum(state)
        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 in visited and direction != visited[perm][2]:
                        print(now_cost + visited[perm][0] + 1)
                        queue = []
                        break
                    elif perm not in visited:
                        estimated_cost = heauristic(new_x, new_y, 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
                        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])

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):
            here = evaluation[state[i][j]]
            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"]
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
        here = hashnum(state)
        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 in visited and direction != visited[perm][2]:
                        print(now_cost + visited[perm][0] + 1)
                        queue = []
                        break
                    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
                        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])

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"]
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
        here = hashnum(state)
        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 in visited and direction != visited[perm][2]:
                        print(now_cost + visited[perm][0] + 1)
                        queue = []
                        break
                    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
                        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])

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:
                estimated_cost += int(evaluation[this][0] == j and evaluation[this][1] == i)
                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"]
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
        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]:
                        print(now_cost + visited[perm][0] + 1)
                        queue = []
                        break
                    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])

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])