Problem:
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

Solution (Python):
import heapq

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),
            (6,5,4,3,5,4,3,2,4,3,2,1,3,2,1,0),
           )

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        j = node_list[i] - 1
        if j == -1: continue
        s += distance[i][j]
    return s

def moveNode(node_list, space, direction):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + direction] = node_tmp[space + direction], node_tmp[space]
    return node_tmp

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

    def makeBoard(self, node_close):
        node_now = self.node
        space = self.space
        move = self.move
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNode(node_now, space, 1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if x_s > 0:
            node_tmp = moveNode(node_now, space, -1)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s < 3:
            node_tmp = moveNode(node_now, space, 4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)
        if y_s > 0:
            node_tmp = moveNode(node_now, space, -4)
            if tuple(node_tmp) not in node_close:
                yield board(node_tmp, move + 1)

b_open = []
n_close =set()
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.add(tuple(b_now.node))
    for b_new in b_now.makeBoard(n_close):
        heapq.heappush(b_open, (b_new.f, b_new.h, i, b_new))
        i += 1

print(b_goal.move)

Solution (Python):
from heapq import heappop, heappush
manhattan = (
 (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))
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))

Solution (Python):
from heapq import heappop, heappush
manhattan = (
 (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))
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 = tuple(tuple((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))

Solution (Python):
from heapq import heappop, heappush
manhattan = tuple(tuple(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 = tuple(tuple((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))

Solution (Python):

from heapq import heappop, heappush
from functools import lru_cache


@lru_cache(maxsize=None)  
def manhattan(size, i, n):
    if n == 0:
        return 0
    else:
        dn, mn = divmod(n-1, size)
        di, mi = divmod(i, size)
        return abs(dn-di) + abs(mn-mi)


class Board:
    __slots__ = ('size', 'nums', 'code', '_hash')

    def __init__(self, size, nums, code=None):
        self.size = size  
        self.nums = nums  
        self._hash = hash(nums)
        if code is None:  
            self.code = sum([manhattan(self.size, i, n)
                             for i, n in enumerate(self.nums) if n != i+1])
        else:
            self.code = code

    def __eq__(self, other):
        return self.code == other.code

    def __lt__(self, other):
        return self.code < other.code

    def __gt__(self, other):
        return self.code > other.code

    def __hash__(self):   
        return self._hash 

    def same(self, other):
        if other is None: 
            return False  
        if self.__class__ != other.__class__:
            return False

        for i in range(self.size * self.size):
            if self.nums[i] != other.nums[i]:
                return False
        return True

    def solved(self):
        for i in range(self.size * self.size):
            if self.nums[i] > 0 and self.nums[i] - 1 != i:
                return False
        return True

    def find(self, num):
        for i in range(self.size * self.size):
            if self.nums[i] == num:
                return i
        raise IndexError()

    def move(self, p1, p2):
        nums = list(self.nums)
        v1, v2 = nums[p1], nums[p2]
        code = (self.code - manhattan(self.size, p1, v1)
                - manhattan(self.size, p2, v2)
                + manhattan(self.size, p2, v1)
                + manhattan(self.size, p1, v2))
        nums[p1], nums[p2] = v2, v1
        return self.__class__(self.size, tuple(nums), code)

    def moves(self):
        i = self.find(0)
        if i > self.size-1:
            yield self.move(i, i-self.size)
        if i % self.size > 0:
            yield self.move(i, i-1)
        if i < self.size*(self.size-1):
            yield self.move(i, i+self.size)
        if (i+1) % self.size > 0:
            yield self.move(i, i+1)

    def __str__(self):
        s = ''
        for i in range(self.size*self.size):
            s += ' {}'.format(self.nums[i])
            if (i + 1) % self.size == 0:
                s += '\n'
        return s

class FifteenPuzzle:
    def __init__(self, board, maxmove):
        self.board = board
        self.maxmove = maxmove
        if not board.solved():
            self.steps = self._solve()
        else:
            self.steps = 0

    def _solve(self):
        bs = []
        checked = set()
        i = 0
        heappush(bs, (self.board.code, self.board.code, i, self.board, 0))

        while len(bs) > 0:
            w, _, _, b, step = heappop(bs)
            checked.add(b)
            step += 1
            for nb in b.moves():
                if nb.solved():
                    return step
                elif self.maxmove < nb.code + step:
                    continue
                elif nb in checked:
                    continue
                else:
                    i += 1
                    heappush(bs, (nb.code + step, nb.code, i, nb, step))
        return -1


def run():
    ns = []
    for i in range(4):
        ns.extend([int(i) for i in input().split()])

    board = Board(4, tuple(ns))
    puzzle = FifteenPuzzle(board, 45)
    print(puzzle.steps)


if __name__ == '__main__':
    run()

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

Solution (Python):



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


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

adjacent = (
    (1, 4),         
    (0, 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)        
)

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


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

import sys

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

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

n = get_distance(board)

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

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

Solution (Python):



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


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

adjacent = (
    (1, 4),         
    (0, 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)        
)

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


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

import sys

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

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

n = get_distance(board)

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

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

Solution (Python):
import sys
from heapq import heappop, heappush


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

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


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


def search(limit, move, space, lower, prev_space):
    global board

    if move == limit:
        if board == end:
            return True

    else:
        for next_space in adjacent[space]:
            if next_space == prev_space:
                continue
            board[space] = board[next_space]
            board[next_space] = 0

            new_lower = lower - distance[board[space]][next_space] + distance[board[space]][space]

            if new_lower + move <= limit:
                if search(limit, move + 1, next_space, new_lower, space):
                    return True
            board[next_space] = board[space]
            board[space] = 0


board = []
for _ in range(4):
    board.extend(list(map(int, sys.stdin.readline().strip().split())))


n = get_distance()  
first_space = board.index(0)
e_o = (0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0)
if n % 2 != e_o[first_space]:
    n += 1

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

Solution (Python):
import sys
from typing import List


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


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


if __name__ == "__main__":
    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)
    )

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

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

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

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

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

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

Solution (Python):
board = [int(s) for _ in range(4) for s in input().split()]
move_piece = [None]* 46
GOAL = list(range(1,16)) + [0]


def create_adjacent(h, w):
  adjacent = [[] for _ in range(h*w)]
  for i in range(h * w):
    if i % w != w-1:
      adjacent[i].append(i+1)
    if i % w != 0:
      adjacent[i].append(i-1)
    if i // h < h-1:
      adjacent[i].append(i+w)
    if i // h > 0:
      adjacent[i].append(i-w)
  return adjacent

def id_search(limit, move, space, lower):
  if move == limit:
    if board == GOAL:
      global count
      count += 1
      print(move)
      exit()
  else:
    for x in adjacent[space]:
      p = board[x]
      if move_piece[move] == p:
        continue
      board[space], board[x] = p, 0
      move_piece[move + 1] = p
      new_lower = lower - distance[p][x] + distance[p][space]

      if new_lower + move <= limit:
        id_search(limit, move+1, x, new_lower)
      board[space], board[x] = 0, p

def create_distance(h, w):
  distance = [[0] * h * w for _ in range(h *w)]
  for i in range(h*w):
    if i == 0:
      continue
    ye, xe = divmod(i-1, w)
    for j in range(h *w):
      y, x = divmod(j,w)
      distance[i][j] = abs(ye-y) + abs(xe-x)
  return distance

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

adjacent = create_adjacent(4, 4)
distance = create_distance(4,4)
n = get_distance(board)
count = 0
for x in range(n,46):
  id_search(x, 0, board.index(0), n)
  if count > 0:
    break

Solution (Python):
board = [int(s) for _ in range(4) for s in input().split()]
move_piece = [None] * 46
GOAL = list(range(1, 16)) + [0]
def create_adjacent(h, w):
    adjacent = [[] for _ in range(h * w)]
    for i in range(h * w):
        if i % w != w - 1:
            adjacent[i].append(i + 1)
        if i % w != 0:
            adjacent[i].append(i - 1)
        if i // h < h - 1:
            adjacent[i].append(i + w)
        if i // h > 0:
            adjacent[i].append(i - w)
    return adjacent

def id_search(limit, move, space, lower):
    if move == limit:
        if board == GOAL:
            global count
            count += 1
            
            print(move)
            exit()
    else:
        for x in adjacent[space]:
            p = board[x]
            if move_piece[move] == p:
                continue
            board[space], board[x] = p, 0
            move_piece[move + 1] = p
            new_lower = lower - distance[p][x] + distance[p][space]
            
            if new_lower + move <= limit:
                id_search(limit, move + 1, x, new_lower)
            
            board[space], board[x] = 0, p

def create_distance(h, w):
    distance = [[0] * h * w for _ in range(h * w)]
    for i in range(h * w):
        if i == 0:
            continue
        ye, xe = divmod(i - 1, w)
        for j in range(h * w):
            y, x = divmod(j, w)
            distance[i][j] = abs(ye - y) + abs(xe - x)
    return distance

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

adjacent = create_adjacent(4, 4)

distance = create_distance(4, 4)

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