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: Memory Limit Exceeded

Solution code:
from sys import stdin
import queue

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

# ?±???¢?????????
class State:
    def __init__(self,board,space,prev):
        self.board = board # ?????¢?????¨?????????
        self.space = space # ?????´????????????(0?????????)
        self.prev = prev   # 1??????????±???¢(State??????????????§??????)

def bf_search(start,end):
    q = queue.Queue()
    q.put(State(start,start.index(0),None)) #item???Q?????\??????
    table = {} # ??????????????????
    table[tuple(start)] = True # ???????±???¢????????§???????????????????????????

    while not q.empty(): # empty()???Q???????????´??????True????????????????????§????????´??????False?????????
        a = q.get() # Q??????item????????????????????????????????????
        for i in adjacent[a.space]: # i????????????0?????????
            b = a.board[:] # ???????????¢???b????????????
            b[a.space] = b[i] # ?¬?????????¢?????????
            b[i] = 0          # ?¬?????????¢?????????
            
            
            key = tuple(b) # b???????????¨??????table????????¨??????????¢??????????
            if key in table:
                continue # ?????¨?????????for?????????????????£?????°???????????¢b?????????

            # table????????¨???????????´????????°???????±???¢c?????????
            # b?????°???????????¢?????¨????????????i????????????0????????????a???1??????????±???¢
            c = State(b,i,a) 

            # b???end????????´?????????printAns()??§???????????°?????¨???
            if b == end:
                return printAns(c)

            # ?????´???????????£??????Q???c????????????
            q.put(c)
            # key????????£???True?????????
            table[key] = True

count = -1
def printAns(c):
    global count
    if c is not None: 
        count += 1
        printAns(c.prev) # c.prev??????????????????????????¨????????£????????°?????°??????
    return count


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

# ??\???
start = [ int(n) for _ in range(4) for n in stdin.readline().split() ]

if start == end:
    print(0)
else:
    print(bf_search(start,end))

Submission status: Memory Limit Exceeded

Solution code:
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]

# Bidirectional search using breadth-first search
def solve(start):
    if start == GOAL:
        return 0
    # 0: forward, 1: backward
    generated_state = {tuple(start): 0, tuple(GOAL): 1}
    step = {tuple(start): 0, tuple(GOAL): 0}
    s = 0
    state1 = [(start, 0), (GOAL, 1)]
    while state1:
        state2 = state1[:]
        state1 = []
        s += 1
        for s2, d in state2:
            i = s2.index(0)
            for p in adjacent[i]:
                s1 = s2[:]
                s1[i], s1[p] = s1[p], 0
                key = tuple(s1)
                if key in generated_state:
                    if generated_state[key] != d:
                        return s + step[key]
                    continue
                state1.append((s1, d))
                generated_state[key] = d
                step[key] = s

import sys

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

print(solve(start))

Submission status: Memory Limit Exceeded

Solution code:
from collections import deque
N = 4
goal = "123456789abcdef0"
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}}
def g(i, j, a):
    if i > j:
        i, j = j, i
    return a[:i] + a[j] + a[i + 1:j] + a[i] + a[j + 1:]
def solve():
    start = "".join(f"{int(i):x}" for _ in range(N) for i in input().split())
    if start == goal:
        return 0
    zero = start.find("0")
    dp = deque([(0, start, zero, 1), (0, goal, 15, 0)])
    TABLE = {start:(1, 0), goal:(0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()

Submission status: Memory Limit Exceeded

Solution code:
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 // (16 ** j) % 16
    return a - t * (16 ** j) + t * (16 ** 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 = deque([(0, start, zero, 1), (0, goal, 0, 0)])
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()

Submission status: Memory Limit Exceeded

Solution code:
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, zero, -1)]
    for i in range(1, 46):
        dp0 = []
        while dp:
            M, space, lower = dp.pop()
            for nyx in m[space]:
                if nyx != lower:
                    key = g(space, nyx, M)
                    if key == goal:
                        return i
                    dp0.append((key, nyx, space))
        dp = dp0
def MAIN():
    print(solve())
MAIN()

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import chain


def get_completed_board(height, width):
    return [str((i + 1) % (width * height)) for i in range(width * height)]


def serialize_board(board):
    return ":".join(board)


def get_empty_pos(board, width, height):
    for i, cell in enumerate(board):
        if cell == "0":
            return i


def get_all_possible_next_boards(board, height, width, empty_pos=None):
    if empty_pos is None:
        empty_pos = get_empty_pos(board, height, width)
    next_boards = []
    x, y = empty_pos % width, empty_pos // height
    # 左との入れ替え
    if x > 0:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos - 1
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    # 右との入れ替え
    if x < width - 1:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos + 1
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    # 上との入れ替え
    if y > 0:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos - height
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))
    # 下との入れ替え
    if y < height - 1:
        next_board = []
        next_board.extend(board)
        dest_pos = empty_pos + height
        next_board[empty_pos], next_board[dest_pos] = next_board[dest_pos], next_board[empty_pos]
        next_boards.append((next_board, dest_pos))

    return next_boards


def resolve(board, height, width):
    # 既知の盤面を保存
    known_serialized_boards = set([serialize_board(board)])
    # 正解の盤面を保存
    current_completed_boards = [(get_completed_board(width, height), None)]
    serialized_completed_boards = set([serialize_board(current_completed_boards[0][0])])
    step_count = 0
    current_boards = [(board, None)]
    while step_count <= 45:
        # 一致する正解盤面があるかをチェック
        if known_serialized_boards & serialized_completed_boards:
            return step_count

        # インプット側の盤面を一つ進める
        next_boards = []
        for board, empty_pos in current_boards:
            # 次のステップでの現れ得る局面を全て取得
            tmp_next_boards = get_all_possible_next_boards(board, height, width, empty_pos)
            filtered_next_board = []
            for board, empty_pos in tmp_next_boards:
                serialized_board = serialize_board(board)
                if serialized_board not in known_serialized_boards:
                    known_serialized_boards.add(serialized_board)
                    filtered_next_board.append((board, empty_pos))
            next_boards.extend(filtered_next_board)
        step_count = step_count + 1

        # 一致する正解盤面があるかをチェック
        if known_serialized_boards & serialized_completed_boards:
            return step_count
        current_boards = next_boards

        # 正解盤面側を１つ進める
        next_completed_boards = []
        for board, empty_pos in current_completed_boards:
            # 次のステップでの現れ得る局面を全て取得
            tmp_next_boards = get_all_possible_next_boards(board, height, width, empty_pos)
            filtered_next_board = []
            for board, empty_pos in tmp_next_boards:
                serialized_board = serialize_board(board)
                if serialized_board not in serialized_completed_boards:
                    serialized_completed_boards.add(serialized_board)
                    filtered_next_board.append((board, empty_pos))
            next_completed_boards.extend(filtered_next_board)
        step_count = step_count + 1
        current_completed_boards = next_completed_boards

    return None


def main():
    inputStr = sys.stdin.read()
    lines = inputStr.split("\n")
    lines = filter(lambda line: line, lines)
    board = list(map(lambda line: line.split(" "), lines))
    height = len(board)
    width = len(board[0])
    board = list(chain.from_iterable(board))
    print(resolve(board, height, width))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import heapq

def move(P,p):
    if p > 3:
        tmp = P[:]
        tmp[p],tmp[p-4] = tmp[p-4],tmp[p]
        tmpp = p - 4
        yield tmp,tmpp
    if p < 12:
        tmp = P[:]
        tmp[p],tmp[p+4] = tmp[p+4],tmp[p]
        tmpp = p + 4
        yield tmp,tmpp
    if p%4 > 0:
        tmp = P[:]
        tmp[p],tmp[p-1] = tmp[p-1],tmp[p]
        tmpp = p - 1
        yield tmp,tmpp
    if p%4 < 3:
        tmp = P[:]
        tmp[p],tmp[p+1] = tmp[p+1],tmp[p]
        tmpp = p + 1
        yield tmp,tmpp

def evaluate(P,Q):
    mht = 0
    for i in range(16):
        pi = P.index(i)
        qi = Q.index(i)
        pc,pr = pi//4,pi%4
        qc,qr = qi//4,qi%4
        mht += abs(pc-qc)+abs(pr-qr)
    return mht
        
A = []
B = [int(i)%16 for i in range(1,17)]
for i in range(4):
        A+=[int(i) for i in input().split()]
dp = {str(A) : (1,0),str(B) : (2,0)}
h = [(evaluate(A,B),A,0,A.index(0))]
e = [(evaluate(A,B),B,0,15)]
heapq.heapify(h)
heapq.heapify(e)
sw = False
ans = 46
while(len(h)>0 and len(e)>0):
    mht,tmp,count,p = heapq.heappop(h)
    if sw and len(h)>0:
        tmph = (mht,tmp,count,p)
        mht,tmp,count,p = heapq.heappop(h)
        heapq.heappush(h,tmph)
        sw = True
    else:
        if sw:
            sw = False
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht*14//13 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    _,tmp,count,p = heapq.heappop(e)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                tmpcount = count + 1 + dp[key][1]
                if tmpcount < ans:
                    ans = tmpcount
            else:
                continue
        else:
            dp[key] = (2,count+1)
            mht = evaluate(A,i)
            if count+mht*14//13 < ans:
                heapq.heappush(e,(mht//2+count,i,count+1,j))

if str(A) == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline


GOAL = [i for i in range(1, 16)] + [0]
MAX_DEPTH = 45  # 80
count = 0

# ??£??\?????????
adjacent = (
    (1, 4),          # 0
    (0, 2, 5),       # 1
    (1, 6, 3),       # 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
)

# ???????????????????????¢
distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6),
    (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5),
    (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4),
    (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3),
    (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5),
    (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4),
    (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3),
    (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2),
    (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4),
    (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3),
    (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2),
    (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1),
    (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3),
    (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2),
    (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1)
)


def manhattan_distance(board):
    return sum(distance[bi][i] for i, bi in enumerate(board))


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


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


def nxt_board(board, space, prev):
    for nxt in adjacent[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt


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


def main():
    start = (map(int, readline().split()) for _ in range(4))
    start = [y for x in start for y in x]
    print(search(start))
main()

Submission status: Accepted

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

distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0, 0, 0),
    (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6),
    (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5),
    (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4),
    (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3),
    (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5),
    (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4),
    (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3),
    (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2),
    (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4),
    (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3),
    (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2),
    (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1),
    (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3),
    (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2),
    (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1),
    (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0)
        )
 
def get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[v][i]
    return diff
 
def get_next_board(board, space, prev):
    for nxt in neighbor[space]:
        if nxt == prev:
            continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt

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

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

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

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{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}]
swap_cache = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210


def swap(board, move_from, move_to):
    return board + swap_cache[move_from][move_to] * (15 - ((board >> (4 * move_from)) & 15))


i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        new_board = swap(board, new_blank, blank)
        if new_board in visited:
            continue
        num = (board >> (4 * new_blank)) & 15
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{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}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))

Submission status: Accepted

Solution code:
from sys import stdin
from heapq import heappush, heappop
solution = [i for i in range(1, 16)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = (
    (1, 4),
    (0, 2, 5),
    (1, 6, 3),
    (2, 7),
    (0, 5, 8),
    (1, 4, 6, 9),
    (2, 5, 7, 10),
    (3, 6, 11),
    (4, 9, 12),
    (5, 8, 10, 13),
    (6, 9, 11, 14),
    (7, 10, 15),
    (8, 13),
    (9, 12, 14),
    (10, 13, 15),
    (11, 14)
)
distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6),
    (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5),
    (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4),
    (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3),
    (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5),
    (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4),
    (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3),
    (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2),
    (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4),
    (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3),
    (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2),
    (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1),
    (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3),
    (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2),
    (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1),
    (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0)
)
def get_diff(B):
    return sum([distance[v][i] for i, v in enumerate(B)])
def get_next_board(board, space, prev):
    for nxt in neighbor[space]:
        if nxt == prev: continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt
def answer_is_odd(board):
    return sum(divmod(board.index(0), 4)) % 2
def search(board):
    lower = get_diff(board)
    start_depth = lower
    if (lower % 2) ^ answer_is_odd(board): start_depth += 1
    for limit in range(start_depth, MAX_DEPTH + 1, 2):
        get_next(board, limit, 0, board.index(0), None, lower)
        if count > 0: return limit
def get_next(board, limit, move, space, prev, lower):
    global count
    if move == limit:
        if board == solution: count += 1
    else:
        for b, nxt in get_next_board(board, space, prev):
            p = board[nxt]
            new_lower = lower - distance[p][nxt] + distance[p][space]
            if new_lower + move <= limit:
                get_next(b, limit, move + 1, nxt, space, new_lower)
boad = [int(a) for _ in range(4) for a in stdin.readline().split()]
print(search(boad))

Submission status: Accepted

Solution code:
from sys import stdin
from heapq import heappush, heappop
solution = [i for i in range(1, 16)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = (
    (1, 4),
    (0, 2, 5),
    (1, 6, 3),
    (2, 7),
    (0, 5, 8),
    (1, 4, 6, 9),
    (2, 5, 7, 10),
    (3, 6, 11),
    (4, 9, 12),
    (5, 8, 10, 13),
    (6, 9, 11, 14),
    (7, 10, 15),
    (8, 13),
    (9, 12, 14),
    (10, 13, 15),
    (11, 14)
)
distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6),
    (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5),
    (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4),
    (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3),
    (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5),
    (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4),
    (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3),
    (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2),
    (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4),
    (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3),
    (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2),
    (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1),
    (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3),
    (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2),
    (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1),
    (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0)
)
def get_diff(B):
    return sum([distance[v][i] for i, v in enumerate(B)])
def get_next_board(board, space, prev):
    for nxt in neighbor[space]:
        if nxt == prev: continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt
def answer_is_odd(board):
    return sum(divmod(board.index(0), 4)) % 2
def search(board):
    lower = get_diff(board)
    start_depth = lower
    if (lower % 2) ^ answer_is_odd(board): start_depth += 1
    for limit in range(start_depth, MAX_DEPTH + 1, 2):
        get_next(board, limit, 0, board.index(0), None, lower)
        if count > 0: return limit
def get_next(board, limit, move, space, prev, lower):
    global count
    if move == limit:
        if board == solution: count += 1
    else:
        for b, nxt in get_next_board(board, space, prev):
            p = board[nxt]
            new_lower = lower - distance[p][nxt] + distance[p][space]
            if new_lower + move <= limit:
                get_next(b, limit, move + 1, nxt, space, new_lower)
boad = []
for i in range(4):
    boad.extend(map(int, stdin.readline().split()))
print(search(boad))

Submission status: Accepted

Solution code:
from sys import stdin
from heapq import heappush, heappop
solution = [i for i in range(1, 16)] + [0]
sol_idx = (15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
MAX_DEPTH = 45
count = 0
neighbor = (
    (1, 4),
    (0, 2, 5),
    (1, 6, 3),
    (2, 7),
    (0, 5, 8),
    (1, 4, 6, 9),
    (2, 5, 7, 10),
    (3, 6, 11),
    (4, 9, 12),
    (5, 8, 10, 13),
    (6, 9, 11, 14),
    (7, 10, 15),
    (8, 13),
    (9, 12, 14),
    (10, 13, 15),
    (11, 14)
)
distance = (
    (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
    (0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6),
    (1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4, 4, 3, 4, 5),
    (2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3, 5, 4, 3, 4),
    (3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2, 6, 5, 4, 3),
    (1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5),
    (2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4),
    (3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3),
    (4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2),
    (2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4),
    (3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3),
    (4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2),
    (5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1),
    (3, 4, 5, 6, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3),
    (4, 3, 4, 5, 3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2),
    (5, 4, 3, 4, 4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1),
    (6, 5, 4, 3, 5, 4, 3, 2, 4, 3, 2, 1, 3, 2, 1, 0)
)
def get_diff(B):
    return sum(distance[v][i] for i, v in enumerate(B))
def get_next_board(board, space, prev):
    for nxt in neighbor[space]:
        if nxt == prev: continue
        b = board[:]
        b[space], b[nxt] = b[nxt], 0
        yield b, nxt
def answer_is_odd(board):
    return sum(divmod(board.index(0), 4)) % 2
def search(board):
    lower = get_diff(board)
    start_depth = lower
    if (lower % 2) ^ answer_is_odd(board): start_depth += 1
    for limit in range(start_depth, MAX_DEPTH + 1, 2):
        get_next(board, limit, 0, board.index(0), None, lower)
        if count > 0: return limit
def get_next(board, limit, move, space, prev, lower):
    if move == limit:
        if board == solution:
            global count
            count += 1
    else:
        for b, nxt in get_next_board(board, space, prev):
            p = board[nxt]
            new_lower = lower - distance[p][nxt] + distance[p][space]
            if new_lower + move <= limit:
                get_next(b, limit, move + 1, nxt, space, new_lower)
print(search([int(a) for _ in range(4) for a in stdin.readline().split()]))