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

Solution code:
# 反復深化

# 距離
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
    (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]

# 下限値枝刈り法
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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    # Never reaches here.
    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
        (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]

    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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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_piece[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)
# print(adjacent)
distance = create_distance(4, 4)
# print(distance)
n = get_distance(board)
count = 0
for x in range(n, 46):
    # print('move', x)
    id_search(x, 0, board.index(0), n)
    if count > 0:
        break

Submission status: Runtime Error

Solution code:
from collections import deque
def move(P):
    for i in range(4):
        for j in range(4):
            if P[i][j] == 0:
                r,c = i,j
    if not r == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [i[:] for i in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

A = [[int(i) for i in input().split()] for _ in range(4)]
dp = {dpkey(A) : 1}
d = deque([(A,0)])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = str(i)
        if key == "[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]]":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
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: Runtime Error

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):
    mht = 0
    for i,j in enumerate(P):
        if i+1 == 0:
            a,b = 3,3
        else:
            a,b = i//4,i%4
        if j == 0:
            c,d = 3,3
        else:
            c,d = (j-1)//4,(j-1)%4
        mht += abs(a-c) + abs(b-d)
    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),A,0,A.index(0))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(len(h)>0):
    mht,tmp,count,p = heapq.heappop(h)
    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(i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht//2+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = dp[key][1] + count + 1
                break
            else:
                continue
        else:
            dp[key] = (2,count+1)
            e.appendleft((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: Runtime Error

Solution code:
from collections import deque
def move(P):

    if not r == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r-1][c] = tmp[r-1][c],tmp[r][c]
        yield tmp
    if not r == 3:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r+1][c] = tmp[r+1][c],tmp[r][c]
        yield tmp
    if not c == 0:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c-1] = tmp[r][c-1],tmp[r][c]
        yield tmp
    if not c == 3:
        tmp = [[i for i in j] for j in P]
        tmp[r][c],tmp[r][c+1] = tmp[r][c+1],tmp[r][c]
        yield tmp

def check(A):
    for i,j in enumerate(A):
        for k,l in A:
            if not i*4+k == l:
                return False
    return True
        
A = [[int(i) for i in input().split()] for _ in range(4)]
for i in range(4):
    for j in range(4):
        if P[i][j] == 0:
            r,c = i,j
dp = {"" : 1}
d = deque([(A,0,"",(r,c))])
c = 0
flag = True
while(flag):
    tmp,c = d.pop()
    for i in move(tmp):
        key = dpkey(i)
        if key == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
            ans = c + 1
            flag = False
        elif not key in dp:
            dp[key] = 1
            d.appendleft((i,c+1))
if dpkey(A) == "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ":
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
#双方向　両方 deque
from collections import deque

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

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,str(B) : 2}
d = deque([(A,0,A.index(0))])
e = deque([(B,0,15)])
flag = True
while(flag):
    tmp,count,p = d.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        elif key == "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]":
            ans = count + 1
            flag = False
        else:
            dp[key] = (1,count+1)
            d.appendleft((i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
            else:
                continue
        else:
            dp[key] == (2,count+1)
            e.appendleft((i,countL+))
            
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: Runtime Error

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))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][2]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((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: Runtime Error

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))]
heapq.heapify(h)
e = deque([(B,0,15)])
ans = 46
flag = True
while(flag):
    mht,tmp,count,p = heapq.heappop(h)
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 2:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (1,count+1)
            mht = evaluate(B,i)
            if count+mht//2 < ans:
                heapq.heappush(h,(mht+count*5,i,count+1,j))
    tmp,count,p = e.pop()
    for i,j in move(tmp,p):
        key = str(i)
        if key in dp:
            if dp[key][0] == 1:
                ans = count + 1 + dp[key][1]
                flag = False
        else:
            dp[key] = (2,count+1)
            e.appendleft((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: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 4
#define N2 16
#define LIMIT 80

typedef struct {
  int b[N2+1];
} Board;
Board board;
int minstep;
typedef enum { R, U, L, D } Direction;
typedef struct { int pos; Direction dir; } Motion;

//  0  1  2  3
//  4  5  6  7
//  8  9 10 11
// 12 13 14 15
 
const Motion motion[N2][5] =
  {{{1,L},{4,U},{-1}}, {{0,R},{2,L},{5,U},{-1}}, {{1,R},{3,L},{6,U},{-1}},{{2,R},{7,U},{-1}},
   {{0,D},{5,L},{8,U},{-1}}, {{1,D},{6,L},{9,U},{4,R},{-1}},  {{2,D},{7,L},{10,U},{5,R},{-1}}, {{3,D},{11,U},{6,R},{-1}},
   {{4,D},{9,L},{12,U},{-1}}, {{5,D},{10,L},{13,U},{8,R},{-1}},  {{6,D},{11,L},{14,U},{9,R},{-1}}, {{7,D},{15,U},{10,R},{-1}},
   {{8,D},{13,L},{-1}}, {{9,D},{14,L},{12,R},{-1}}, {{10,D},{15,L},{13,R},{-1}},{{11,D},{14,R},{-1}}};

const int rr[4][5] = {{0,0,1,0,0},{0,0,0,1,0},{1,0,0,0,0},{0,1,0,0,0}};

int dd[N2][N2];
int dist(int *b)
{
  int i, n, d = 0;
  for (i=0; i<N2; i++) {
    n = b[i]-1;
    if (n<0) {
      continue;
    }
    d += dd[n][i];
  }
  return d;
}

void search(int step, Motion prev)
{
  int i, d=0;
  d = dist(board.b);
  if (step+d>minstep) return;
  if (d==0) {
    printf("%d\n", step);
    exit(0);
  }
  Board board_bak = board;
  for (i=0; motion[prev.pos][i].pos>=0; i++) {
    Motion m = motion[prev.pos][i];
    if (rr[m.dir][prev.dir]) continue; //元に戻るのを防止
    board.b[prev.pos] = board.b[m.pos];
    board.b[m.pos] = 0;
    search(step+1, m);
    board = board_bak;
  }
}

int main()
{
  int i, j;
  for (i=0; i<N2; i++)
    for (j=0; j<N2; j++)
      dd[i][j] = abs(i%N-j%N) + abs(i/N-j/N);
  
  Board ini_board;
  fscanf(stdin, "%d %d %d %d\n", &ini_board.b[0],&ini_board.b[1],&ini_board.b[2],&ini_board.b[3]);
  fscanf(stdin, "%d %d %d %d\n", &ini_board.b[4],&ini_board.b[5],&ini_board.b[6],&ini_board.b[7]);
  fscanf(stdin, "%d %d %d %d\n", &ini_board.b[8],&ini_board.b[9],&ini_board.b[10],&ini_board.b[11]);
  fscanf(stdin, "%d %d %d %d\n", &ini_board.b[12],&ini_board.b[13],&ini_board.b[14],&ini_board.b[15]);
  
  ini_board.b[N2]=0;

  Motion m;
  m.dir = 4;
  for (i=0; i<N2; i++)
    if (ini_board.b[i]==0) {
      m.pos = i;
      break;
    }

  for (minstep=dist(ini_board.b); minstep<=LIMIT; minstep++) {
    board = ini_board;
    search(0, m);
  }
  puts("no result.");
  return 0;
}

Submission status: Runtime Error

Solution code:
import sys, itertools
f = sys.stdin
start = [line.split() for line in f]
start = tuple(int(x) for y in start for x in y)
end =(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)


def next_board(b):
    brank = b.index(0)
    if brank % 4:
        yield b[:brank - 1] + (b[brank], b[brank - 1]) + b[brank + 1:]
    if brank // 4:
        yield b[:brank - 4] + (b[brank],)+ b[brank - 3:brank] +  (b[brank - 4],) + b[brank + 1:]
    if brank % 4 != 3:
        yield b[:brank] + (b[brank + 1], b[brank]) + b[brank + 2:]
    if brank // 4 != 3:
        yield b[:brank] + (b[brank + 4],)+ b[brank + 1:brank + 4] +  (b[brank],) + b[brank + 5:]

d = {start:1, end:-1}
#queue = set([(start, 1), (end, -1)])
queue = list([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.pop(0)
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.append((b, way))
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break

Submission status: Runtime Error

Solution code:
start = [input().split() for _ in range(4)]
start = tuple(int(x) for y in start for x in y)
end =(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)

def next_board(b):
    brank = b.index(0)
    if brank % 4:
        yield b[:brank - 1] + (b[brank], b[brank - 1]) + b[brank + 1:]
    if brank // 4:
        yield b[:brank - 4] + (b[brank],)+ b[brank - 3:brank] +  (b[brank - 4],) + b[brank + 1:]
    if brank % 4 != 3:
        yield b[:brank] + (b[brank + 1], b[brank]) + b[brank + 2:]
    if brank // 4 != 3:
        yield b[:brank] + (b[brank + 4],)+ b[brank + 1:brank + 4] +  (b[brank],) + b[brank + 5:]

d = {start:1, end:-1}
queue = list([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.pop(0)
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.append((b, way))
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break

Submission status: Runtime Error

Solution code:
start = [input().split() for _ in range(4)]
start = [x for y in start for x in y]
start[start.index('10')] = 'a'
start[start.index('11')] = 'b'
start[start.index('12')] = 'c'
start[start.index('13')] = 'd'
start[start.index('14')] = 'e'
start[start.index('15')] = 'f'
start = ''.join(start)

end = '123456789abcdef0'

def next_board(b):
    brank = b.index('0')
    if brank % 4:
        yield b[:brank - 1] + b[brank] + b[brank - 1] + b[brank + 1:]
    if brank // 4:
        yield b[:brank - 4] + b[brank] + b[brank - 3:brank] + b[brank - 4] + b[brank + 1:]
    if brank % 4 != 3:
        yield b[:brank] + b[brank + 1] + b[brank] + b[brank + 2:]
    if brank // 4 != 3:
        yield b[:brank] + b[brank + 4]+ b[brank + 1:brank + 4] + b[brank] + b[brank + 5:]

d = {start:1, end:-1}
queue = collections.deque([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.popleft()
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.append((b, way))
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break

Submission status: Runtime Error

Solution code:
import sys
start = [line.split() for line in sys.stdin]
start = [x for y in start for x in y]
start[start.index('10')] = 'a'
start[start.index('11')] = 'b'
start[start.index('12')] = 'c'
start[start.index('13')] = 'd'
start[start.index('14')] = 'e'
start[start.index('15')] = 'f'
start = ''.join(start)

end = '123456789abcdef0'

def next_board(b):
    z = b.index('0')
    if z % 4:
        yield swap(b, z, z - 1)
    if z // 4:
        yield swap(b, z, z - 4)
    if z % 4 != 3:
        yield swap(b, z, z + 1)
    if z // 4 != 3:
        yield swap(b, z, z + 4)

def swap(b, i, j):
    b = list(b)
    b[i], b[j] = b[j], b[i]
    return ''.join(b)
        
d = {start:1, end:-1}
queue = collections.deque([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.popleft()
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.append((b, way))
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break

Submission status: Runtime Error

Solution code:
import sys
start = [sys.stdin.readline().split() for _ in range(4)]
start = [x for y in start for x in y]
start[start.index('10')] = 'a'
start[start.index('11')] = 'b'
start[start.index('12')] = 'c'
start[start.index('13')] = 'd'
start[start.index('14')] = 'e'
start[start.index('15')] = 'f'
start = ''.join(start)

end = '123456789abcdef0'

def next_board(b):
    z = b.index('0')
    if z % 4:
        yield swap(b, z, z - 1)
    if z // 4:
        yield swap(b, z, z - 4)
    if z % 4 != 3:
        yield swap(b, z, z + 1)
    if z // 4 != 3:
        yield swap(b, z, z + 4)

def swap(b, i, j):
    b = list(b)
    b[i], b[j] = b[j], b[i]
    return ''.join(b)
        
d = {start:1, end:-1}
queue = collections.deque([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.popleft()
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.append((b, way))
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break

Submission status: Runtime Error

Solution code:
start = [input().split() for _ in range(4)]
start = [x for y in start for x in y]
start[start.index('10')] = 'a'
start[start.index('11')] = 'b'
start[start.index('12')] = 'c'
start[start.index('13')] = 'd'
start[start.index('14')] = 'e'
start[start.index('15')] = 'f'
start = ''.join(start)

end = '123456789abcdef0'

def next_board(b):
    z = b.index('0')
    if z % 4:
        yield swap(b, z, z - 1)
    if z // 4:
        yield swap(b, z, z - 4)
    if z % 4 != 3:
        yield swap(b, z, z + 1)
    if z // 4 != 3:
        yield swap(b, z, z + 4)

def swap(b, i, j):
    b = list(b)
    b[i], b[j] = b[j], b[i]
    return ''.join(b)
        
d = {start:1, end:-1}
queue = collections.deque([(start, 1), (end, -1)])
while len(queue):
    u, way = queue.popleft()
    for b in next_board(u):
        if b not in d:
            d[b] = d[u] + way
            queue.append((b, way))
        elif d[b] * way < 0:
            print(abs(d[b]) + abs(d[u]) - 1)
            queue.clear()
            break