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

def d_manhattan(node_list):
    s = 0
    for i in range(16):
        x_goal = i%4
        y_goal = i//4
        x_now = (node_list[i] - 1)%4
        y_now = (node_list[i] - 1)//4
        if y_now == -1:
            continue
        dx = abs(x_now - x_goal)
        dy = abs(y_now - y_goal)
        s += dx + dy
    return s

def moveNodeE(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 1] = node_tmp[space + 1], node_tmp[space]
    return node_tmp
def moveNodeW(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 1] = node_tmp[space - 1], node_tmp[space]
    return node_tmp
def moveNodeN(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 4] = node_tmp[space - 4], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 4] = node_tmp[space + 4], node_tmp[space]
    return node_tmp

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

    def makeBoard(self, node_close):
        space = self.space
        cost_now = self.f
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNodeE(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if y_s < 3:
            node_tmp = moveNodeS(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)

b_open = []
n_close = {}
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["".join(map(str, b_now.node))] = i
    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.g)

Submission status: Time Limit Exceeded

Solution code:
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):
    global distance
    s = 0
    for i in range(16):
        if node_list[i] == 0:
            continue
        s += distance[i][node_list[i] - 1]
    return s

def moveNodeE(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 1] = node_tmp[space + 1], node_tmp[space]
    return node_tmp
def moveNodeW(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 1] = node_tmp[space - 1], node_tmp[space]
    return node_tmp
def moveNodeN(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space - 4] = node_tmp[space - 4], node_tmp[space]
    return node_tmp
def moveNodeS(node_list, space):
    node_tmp = node_list[:]
    node_tmp[space], node_tmp[space + 4] = node_tmp[space + 4], node_tmp[space]
    return node_tmp

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

    def makeBoard(self, node_close):
        space = self.space
        cost_now = self.f
        x_s = space%4
        y_s = space//4
        if x_s < 3:
            node_tmp = moveNodeE(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if x_s > 0:
            node_tmp = moveNodeW(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if y_s < 3:
            node_tmp = moveNodeS(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)
        if y_s > 0:
            node_tmp = moveNodeN(self.node, space)
            if "".join(map(str, node_tmp)) not in node_close:
                yield board(node_tmp, self.g + 1)

b_open = []
n_close = {}
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["".join(map(str, b_now.node))] = i
    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.g)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
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 = [(0, start, zero, 1), (0, goal, 0, 0)]
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = heappop(dp)
        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)
            heappush(dp, (cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()

Submission status: Time 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 // (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 = [(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: Time Limit Exceeded

Solution code:
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 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
def solve():
    board = sum((list(map(int, input().split())) for _ in range(4)), [])
    zero = board.index(0)
    if board == GOAL:
        return 0
    def df_lower_search(limit, move, space, before):
        if move == limit:
            if board == GOAL:
                return True
        else:
            for i in m[space]:
                if i == before:
                    continue
                p = board[i]
                board[space] = p
                board[i] = 0
                if move + 1 <= limit:
                    if df_lower_search(limit, move + 1, i, space):
                        return True
                board[space] = 0
                board[i] = p
    for l in range(1, 46):
        if df_lower_search(l, 0, zero, None):
            return l
def MAIN():
    print(solve())
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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 = deque([(estimation_init, board_init, blank_init)])
visited = set()
while True:
    estimation, board, blank = queue.popleft()
    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
        queue.append((new_estimation, new_board, new_blank))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
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 = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
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 >> 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 = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            TABLE.add(key)
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
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 = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        if M == goal:
            return cnt
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                continue
            TABLE.add(key)
            if cnt > 45:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
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
manhattan = (0, 1, 2, 3,
             1, 2, 3, 4,
             2, 3, 4, 5,
             3, 4, 5, 6)
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 = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        cnt += 1
        for nyx in m[yx]:
            num = (M >> 4 * nyx) & 15
            key = M - (num << 4 * nyx) + (num << 4 * yx)
            if key == goal:
                return cnt
            if key in TABLE:
                continue
            TABLE.add(key)
            new_cnt = cnt + manhattan[nyx]
            if new_cnt > 45:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
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
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))
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 = [(0, start, zero)]
    TABLE = {start}
    while dp:
        cnt, M, yx = heappop(dp)
        cnt += 1
        for nyx in m[yx]:
            num = (M >> 4 * nyx) & 15
            key = M - (num << 4 * nyx) + (num << 4 * yx)
            if key == goal:
                return cnt
            if key in TABLE:
                continue
            TABLE.add(key)
            new_cnt = cnt - manhattan[nyx][num] + manhattan[yx][num]
            if new_cnt > 45:
                continue
            heappush(dp, (cnt, key, nyx))
def MAIN():
    print(solve())
MAIN()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from copy import deepcopy, copy
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)
dir = ('r', 'u', 'l', 'd')
N = 4
N2 = 16
LIMIT = 46
MDT = tuple(tuple(abs(i // N - j // N) + abs(i % N - j % N) for j in range(N2)) for i in range(N2))
class Puzzle:
    def __init__(self):
        self.f = []
        self.space, self.MD = 0, 0
state = Puzzle()
path = [0] * LIMIT
def getAllMD(pz):
    global MDT
    sum_mdt = 0
    for i in range(N2):
        if pz.f[i] == N2:
            continue
        sum_mdt += MDT[i][pz.f[i] - 1]
    return sum_mdt
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
    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 = 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):
            return True
        state = deepcopy(tmp)
    return False
def iterative_deepening(pin, state, path):
    pin.MD = getAllMD(pin)
    ans = ""
    for limit in range(pin.MD, LIMIT + 1):
        state = deepcopy(pin)
        if dfs(0, -100, limit, state, path):
            return limit
    return "unsolvable"
in0 = Puzzle()
in0.f = sum([list(map(int, input().split())) for _ in range(N)], [])
t = in0.f.index(0)
in0.f[t] = N2
in0.space = t
print(iterative_deepening(in0, state, path))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy


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


def serialize_board(board):
    return ":".join(list(map(lambda cell: ",".join(cell), board)))


def get_empty_pos(board):
    for y, row in enumerate(board):
        for x, cell in enumerate(row):
            if cell == "0":
                return (x, y)


def get_all_possible_next_boards(board, height, width, empty_pos=None):
    if empty_pos is None:
        empty_pos = get_empty_pos(board)
    next_boards = []
    # 左との入れ替え
    if empty_pos[0] > 0:
        next_board = copy.deepcopy(board)
        next_board[empty_pos[1]][empty_pos[0]], next_board[empty_pos[1]][empty_pos[0] - 1] = \
            next_board[empty_pos[1]][empty_pos[0] - 1], next_board[empty_pos[1]][empty_pos[0]]
        next_boards.append((next_board, (empty_pos[0] - 1, empty_pos[1])))
    # 右との入れ替え
    if empty_pos[0] < width - 1:
        next_board = copy.deepcopy(board)
        next_board[empty_pos[1]][empty_pos[0]], next_board[empty_pos[1]][empty_pos[0] + 1] = \
            next_board[empty_pos[1]][empty_pos[0] + 1], next_board[empty_pos[1]][empty_pos[0]]
        next_boards.append((next_board, (empty_pos[0] + 1, empty_pos[1])))
    # 上との入れ替え
    if empty_pos[1] > 0:
        next_board = copy.deepcopy(board)
        next_board[empty_pos[1]][empty_pos[0]], next_board[empty_pos[1] - 1][empty_pos[0]] = \
            next_board[empty_pos[1] - 1][empty_pos[0]], next_board[empty_pos[1]][empty_pos[0]]
        next_boards.append((next_board, (empty_pos[0], empty_pos[1] - 1)))
    # 下との入れ替え
    if empty_pos[1] < height - 1:
        next_board = copy.deepcopy(board)
        next_board[empty_pos[1]][empty_pos[0]], next_board[empty_pos[1] + 1][empty_pos[0]] = \
            next_board[empty_pos[1] + 1][empty_pos[0]], next_board[empty_pos[1]][empty_pos[0]]
        next_boards.append((next_board, (empty_pos[0], empty_pos[1] + 1)))
    return next_boards


def resolve(board, height, width):
    # 既知の盤面を保存
    known_serialized_boards = set([])
    # 正解の盤面を保存
    completed_serialized_board = serialize_board(get_completed_board(width, height))
    step_count = 0
    current_boards = [(board, None)]
    while step_count <= 45:
        next_boards = []
        for board, empty_pos in current_boards:
            serialized_board = serialize_board(board)
            # 正答があった場合はステップ数を返して終了
            if serialized_board == completed_serialized_board:
                return step_count
            # 既知の盤面は後続の処理対象としない
            if serialized_board in known_serialized_boards:
                continue
            else:
                known_serialized_boards.add(serialized_board)
            # 次のステップでの現れ得る局面を全て取得
            next_boards.extend(get_all_possible_next_boards(board, height, width, empty_pos))
        current_boards = next_boards
        step_count = step_count + 1
    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])
    step_count = resolve(board, height, width)
    print(step_count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys;
import queue;

def iterative(i,j,c_depth,c_puz):
    if(puzzleCheck(c_puz)):
        global finding
        finding = 1
        print(c_depth)

    if(finding == 1 or (c_depth+simpleHS(c_puz)) > depth):
        return

    if(i != 0 and finding != 1):
        iterative(i-1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i-1,j))
    if(i != 3 and finding != 1):
        iterative(i+1,j,c_depth+1,swapPuz(c_puz[0:],i,j,i+1,j))
    if(j != 0 and finding != 1):
        iterative(i,j-1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j-1))
    if(j != 3 and finding != 1):
        iterative(i,j+1,c_depth+1,swapPuz(c_puz[0:],i,j,i,j+1))

def simpleHS(c_puz):
    count = 0
    for i in range(len(correctPuz)):
        if(correctPuz[i] != c_puz[i]):
            count+=1
    return count

def HS(c_puz):
    value = 0
    for i in range(len(c_puz)):
        k = correctPuz.index(c_puz[i])
        _i = (int)(i/4)
        _j = i - _i*4
        ki = (int)(k/4)
        kj = k - ki*4
        value = abs(_i-ki)+abs(_j-kj) 

    return value


def swapPuz(c_puz, i, j, i2,j2):
    swap = c_puz[i*4+j]
    c_puz[i*4+j] = c_puz[i2*4+j2]
    c_puz[i2*4+j2] = swap
    return c_puz

def puzzleCheck(c_puz):
    if(c_puz[15] == 0):
        for i in range(len(correctPuz)):
            if(correctPuz[i] != c_puz[i]):
                return False
        return True
    return False

correctPuz = [i+1 for i in range(16)]
correctPuz[15] = 0
puz = [0 for i in range(16)]

i_start = 0
j_start = 0

for i in range(4):
    puz[i*4],puz[i*4+1],puz[i*4+2],puz[i*4+3] = map(int, input().split());
    if(puz[i*4] == 0):
        i_start,j_start = i,0
    elif(puz[i*4+1] == 0):
        i_start,j_start = i,1
    elif(puz[i*4+2] == 0):
        i_start,j_start = i,2
    elif(puz[i*4+3] == 0):
        i_start,j_start = i,3

finding = 0
depth = 0
while True:
    if(finding == 1 or depth > 45):
        break
    iterative(i_start,j_start,0,puz[0:])
    depth+=1

Submission status: Time Limit Exceeded

Solution code:
# 15 Puzzle
import copy

[N, d] = [4, 0]
start = []
goal = [[i + j*N for i in range(1, N + 1)] for j in range(N)]
goal[3][3] = 0
#print(goal)
for i in range(N):
    start.append(list(map(int, input().split())))

def manhattan(state):
    global N
    h = 0
    for i in range(N):
        for j in range(N):
            if state[i][j] == 1:
                h += (i + j)
                #print(h)
            if state[i][j] == 2:
                h += (i + abs(j - 1))
                #print(h)
            if state[i][j] == 3:
                h += (i + abs(j - 2))
                #print(h)
            if state[i][j] == 4:
                h += (i + 3 - j)
                #print(h)

            if state[i][j] == 5:
                h += (abs(i - 1) + j)
                #print(h)
            if state[i][j] == 6:
                h += (abs(i - 1) + abs(j - 1))
                #print(h)
            if state[i][j] == 7:
                h += (abs(i - 1) + abs(j - 2))
                #print(h)
            if state[i][j] == 8:
                h += (abs(i - 1) + 3 - j)
                #print(h)

            if state[i][j] == 9:
                h += (abs(i - 2) + j)
                #print(h)
            if state[i][j] == 10:
                h += (abs(i - 2) + abs(j - 1))
                #print(h)
            if state[i][j] == 11:
                h += (abs(i - 2) + abs(j - 2))
                #print(h)
            if state[i][j] == 12:
                h += (abs(i - 2) + 3 - j)
                #print(h)

            if state[i][j] == 13:
                h += (3 - i + j)
                #print(h)
            if state[i][j] == 14:
                h += (3 - i + abs(j - 1))
                #print(h)
            if state[i][j] == 15:
                h += (3 - i + abs(j - 2))
                #print(h)
    return h
"""
def calculate(state, g):
    h = manhattan(state)
    return [h + g, state, g]
"""

while True:
    d += 1
    """
    if d == 3:
        break
    """
    #print("depth: ", d)
    queue = []
    queue.append([-1, start, 0])
    count = 0

    #while True:
    while len(queue) != 0:
        short_n = queue.pop(0)
        #if short_n[0] > d:
        #    break
        state = short_n[1]
        g = short_n[2]

        #if d == 1:
            #print(short_n[0])
            #print(state)
            #print(g)

        if state == goal:
            #print("This is the answer.", short_n[2])
            print(short_n[2])
            break

        count += 1

        for i in range(N):
            check = state[i].count(0)
            if check != 0:
                [r, c] = [i, state[i].index(0)]
                break
            if i == 3:
                print("Error")

        if r - 1 >= 0:
            temp = copy.deepcopy(state)
            [temp[r][c], temp[r - 1][c]] = [temp[r - 1][c], temp[r][c]]
            h = manhattan(state)
            #print("1: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1])
        
        if c + 1 < N:
            temp = copy.deepcopy(state)
            [temp[r][c], temp[r][c + 1]] = [temp[r][c + 1], temp[r][c]]
            #queue.append(calculate(temp, g + 1))
            h = manhattan(state)
            #print("2: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1])

        if r + 1 < N:
            temp = copy.deepcopy(state)
            [temp[r][c], temp[r + 1][c]] = [temp[r + 1][c], temp[r][c]]
            #queue.append(calculate(temp, g + 1))
            h = manhattan(state)
            #print("3: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1])
        
        if c - 1 >= 0:
            temp = copy.deepcopy(state)
            [temp[r][c], temp[r][c - 1]] = [temp[r][c - 1], temp[r][c]]
            #queue.append(calculate(temp, g + 1))
            h = manhattan(state)
            #print("4: ", h, temp)
            if g + 1 + h <= d:
                queue.append([h + g + 1, temp, g + 1])
        
        #print(queue)
        queue.sort()

        #if d == 1:
            #print(len(queue))

    if state == goal:
        break