Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

15 Puzzle

  The goal of the 15 puzzle problem is to complete pieces on $4 \times 4$ cells where one of the cells is empty space.

  In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 15 as shown below.

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15

  You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

  Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Input

  The $4 \times 4$ integers denoting the pieces or space are given.

Output

  Print the fewest steps in a line.

Constraints

The given puzzle is solvable in at most 45 steps.

Sample Input

1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15

Sample Output

8



Sample input:
1 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
import heapq

CORRECT = 0x0fedcba987654321
heap_puzzle = []
cache = {}


class Puzzle:
    DEST_BOARD_DICT = {CORRECT >> (4 * i) & 0b1111: i for i 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 __init__(self, board, pid0, count, prev, heuristic=None):
        self.board = board
        self.pid0 = pid0
        self.count = count
        self.prev = prev
        self.invalid = False
        self.heuristic = heuristic

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

    def get_sum_heuristic(self):
        if self.heuristic is not None:
            return self.heuristic

        orig_board_dict = {i: self.board >> (4 * i) & 0b1111 for i in range(16)}
        self.heuristic = sum(self.HEURISTICS[pid][self.DEST_BOARD_DICT[val]] for pid, val in orig_board_dict.items())

        return self.heuristic

    def __lt__(self, other):
        return True


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


def get_candidate(pid):
    global MOVE_CANDIDATE

    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):
    global OFFSET_MASTER, SWAP_CANDIDATE
    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))


def put_next_puzzle():
    global heap_puzzle, cache, SWAP_CANDIDATE, CORRECT
    (cost, puzzle) = heapq.heappop(heap_puzzle)
    if puzzle.invalid:
        return -1
    board, pid0, count, prev = puzzle.board, puzzle.pid0, puzzle.count, puzzle.prev
    for new_pid0 in SWAP_CANDIDATE[pid0]:
        if new_pid0 == prev:
            continue

        new_board = puzzle.swap(new_pid0)

        if new_board == CORRECT:
            return count + 1

        heuristic = None
        if new_board in cache:
            closed_puzzle = cache[new_board]
            if closed_puzzle.count <= count:
                continue
            else:
                closed_puzzle.invalid = True
                heuristic = closed_puzzle.heuristic

        new_puzzle = Puzzle(
                board=new_board,
                count=count + 1,
                pid0=new_pid0,
                prev=pid0,
                heuristic=heuristic
        )
        new_cost = count + 1 + new_puzzle.get_sum_heuristic()
        heapq.heappush(heap_puzzle, (new_cost, new_puzzle))
        cache[new_board] = new_puzzle
    return -1


first_board = 0
first_pid0 = -1

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

s_puzzle = Puzzle(board=first_board, count=0, pid0=first_pid0, prev=-1)
heapq.heappush(heap_puzzle, (s_puzzle.get_sum_heuristic(), s_puzzle))
cache[first_board] = s_puzzle
result = None

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

print(result)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
from heapq import heappush, heappop

def get_patten(B):
    return ''.join(map(str, B))

def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C

def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C

def change_top(index, B):
    C = B.copy()
    C[index], C[index - 4] = C[index - 4], C[index]
    return C

def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 4] = C[index + 4], C[index]
    return C

def get_diff(B):
    diff = 0
    for i in range(16):
        if i == 0:
            place = 15
        else:
            place = i - 1
        index = B.index(i)
        
        d = abs(place - index) 
        if d >= 4:
            diff += (d // 4) + (d % 4)
        elif place // 4 == index // 4:
            diff += d
        elif d == 0:
            continue
        else: # d = 1 or 2 or 3
            diff += 1 + (4 - d)

    return diff

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

q = []
diff = get_diff(boad)
# (diff, boad, prev, count)
heappush(q, (diff + 0, boad, None, 0))

while len(q) > 0:
    diff_count, B, prev, count = heappop(q)
    if diff_count > 45:
        continue

    p = get_patten(B)
    if p == '1234567891011121314150':
        print(count)
        exit()

    index = B.index(0)

    if index % 4 != 0 and prev != 'right':
        C = change_left(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'left', count + 1))

    if index % 4 != 3 and prev != 'left':
        C = change_right(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'right', count + 1))

    if index >= 4 and prev != 'bottom':
        C = change_top(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'top', count + 1))

    if index <= 11 and prev != 'top':
        C = change_bottom(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'bottom', count + 1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
from heapq import heappush, heappop
solution = [i + 1 for i in range(15)]
solution.append(0)

def get_patten(B):
    return ''.join(map(str, B))

def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C

def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C

def change_top(index, B):
    C = B.copy()
    C[index], C[index - 4] = C[index - 4], C[index]
    return C

def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 4] = C[index + 4], C[index]
    return C

def get_diff(B):
    index_list = [0] * 16
    for i, v in enumerate(B):
        index_list[v] = i

    diff = 0
    for i, v in enumerate(solution):
        index = index_list[v]
        d = abs(i - index)
        if d >= 4:
            diff += (d // 4) + (d % 4)
        elif i // 4 == index // 4:
            diff += d
        elif d == 0:
            continue
        else: # d = 1 or 2 or 3
            diff += 1 + (4 - d)

    return diff


def get_diff_old(B):
    diff = 0
    for i in range(16):
        if i == 0:
            place = 15
        else:
            place = i - 1
        index = B.index(i)
        
        d = abs(place - index) 
        if d >= 4:
            diff += (d // 4) + (d % 4)
        elif place // 4 == index // 4:
            diff += d
        elif d == 0:
            continue
        else: # d = 1 or 2 or 3
            diff += 1 + (4 - d)

    return diff

def judge(B):
    for i in range(16):
        if solution[i] != B[i]:
            return False
    return True


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

q = []
diff = get_diff(boad)
exist = set()
# (diff, boad, prev, count)
heappush(q, (diff + 0, boad, None, 0))
exist.add(get_patten(boad))

while len(q) > 0:
    diff_count, B, prev, count = heappop(q)
    if diff_count > 45:
        continue

    if judge(B) == True:
        print(count)
        exit()

    index = B.index(0)

    if index % 4 != 0 and prev != 'right':
        C = change_left(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'left', count + 1))

    if index % 4 != 3 and prev != 'left':
        C = change_right(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'right', count + 1))

    if index >= 4 and prev != 'bottom':
        C = change_top(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'top', count + 1))

    if index <= 11 and prev != 'top':
        C = change_bottom(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'bottom', count + 1))

Submission status: Time Limit Exceeded

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]

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 get_patten(B):
    return ''.join(map(str, B))

def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C

def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C

def change_top(index, B):
    C = B.copy()
    C[index], C[index - 4] = C[index - 4], C[index]
    return C

def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 4] = C[index + 4], C[index]
    return C

def get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[sol_idx[v]][i]
    return diff


def get_diff_old(B):
    diff = 0
    for i in range(16):
        if i == 0:
            place = 15
        else:
            place = i - 1
        index = B.index(i)
        
        d = abs(place - index) 
        if d >= 4:
            diff += (d // 4) + (d % 4)
        elif place // 4 == index // 4:
            diff += d
        elif d == 0:
            continue
        else: # d = 1 or 2 or 3
            diff += 1 + (4 - d)

    return diff

def judge(B):
    for i in range(16):
        if solution[i] != B[i]:
            return False
    return True


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

q = []
diff = get_diff(boad)
exist = set()
# (diff, boad, prev, count)
heappush(q, (diff + 0, boad, None, 0))
exist.add(get_patten(boad))

while len(q) > 0:
    diff_count, B, prev, count = heappop(q)
    if diff_count > 45:
        continue

    if judge(B) == True:
        print(count)
        exit()

    index = B.index(0)

    if index % 4 != 0 and prev != 'right':
        C = change_left(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'left', count + 1))

    if index % 4 != 3 and prev != 'left':
        C = change_right(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'right', count + 1))

    if index >= 4 and prev != 'bottom':
        C = change_top(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'top', count + 1))

    if index <= 11 and prev != 'top':
        C = change_bottom(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'bottom', count + 1))

Submission status: Time Limit Exceeded

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)

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_patten(B):
    return ''.join(map(str, B))
 
def change_left(index, B):
    C = B.copy()
    C[index], C[index - 1] = C[index - 1], C[index]
    return C
 
def change_right(index, B):
    C = B.copy()
    C[index], C[index + 1] = C[index + 1], C[index]
    return C
 
def change_top(index, B):
    C = B.copy()
    C[index], C[index - 4] = C[index - 4], C[index]
    return C
 
def change_bottom(index, B):
    C = B.copy()
    C[index], C[index + 4] = C[index + 4], C[index]
    return C

def get_diff(B):
    diff = 0
    for i, v in enumerate(B):
        diff += distance[v][i]
    return diff
 
def get_next(board, index, prev):
    for nxt in neighbor[index]:
        if nxt == prev:
            continue
        b = board[:]
        b[index], b[nxt] = b[nxt], 0
        yield b, nxt
 
# main
boad = []
for i in range(4):
    boad.extend(map(int, input().split()))
 
q = []
diff = get_diff(boad)
# (diff, boad, prev, count)
heappush(q, (diff + 0, boad, None, 0))
 
while len(q) > 0:
    diff_count, B, prev, count = heappop(q)
    if diff_count > 45:
        continue
 
    if B == solution:
        print(count)
        exit()
 
    index = B.index(0)
 
    if index % 4 != 0 and prev != 'right':
        C = change_left(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'left', count + 1))
 
    if index % 4 != 3 and prev != 'left':
        C = change_right(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'right', count + 1))
 
    if index >= 4 and prev != 'bottom':
        C = change_top(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'top', count + 1))
 
    if index <= 11 and prev != 'top':
        C = change_bottom(index, B)
        diff = get_diff(C)
        heappush(q, (diff + count, C, 'bottom', count + 1))

Submission status: Time Limit Exceeded

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


def swap(board, move_from, move_to):
    mf, mt = 4 * move_from, 4 * move_to
    return board + ((1 << mf) - (1 << mt)) * (15 - ((board >> mf) & 15))


def estimate(board):
    return sum(manhattan[i][(board >> (4 * i)) & 15] for i in range(15))


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

while True:
    _, cost, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(cost)
        break
    visited.add(board)
    cost += 1
    for new_blank in movables[blank]:
        new_board = swap(board, new_blank, blank)
        if new_board in visited:
            continue
        new_estimation = cost + estimate(new_board)
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, cost, new_board, new_blank))

Submission status: Time Limit Exceeded

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

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


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


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

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

Submission status: Time Limit Exceeded

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
 
    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)
AL = []
for x in range(n, 46):
    id_lower_search(x, 0, board.index(0), n)
    if count > 0:
        print(str(x))
        break

Submission status: Time Limit Exceeded

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

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 = (map(int, readline().split()) for _ in range(4))
board = [y for x in board for y in x]
   
move_piece = [None] * 46
   
def id_lower_search(limit, move, space, lower):
    if move == limit:
        if board == GOAL:
            global count
            count += 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

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

count = 0
n = get_distance(board)
if (n % 2) ^ answer_is_odd(board):
        n += 1
AL = []
for x in range(n, 46):
    id_lower_search(x, 0, board.index(0), n)
    if count > 0:
        print(str(x))
        break

Submission status: Time Limit Exceeded

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,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]]
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 = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)

Submission status: Time Limit Exceeded

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,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))
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 = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)

Submission status: Time Limit Exceeded

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,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))
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 = copy.deepcopy(In)
    if (dfs(0, -100, limit, state, path)):
        break
print(limit)