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:
goal = ((1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 0))
goal_position = [
[3, 3],
[0, 0],
[0, 1],
[0, 2],
[0, 3],
[1, 0],
[1, 1],
[1, 2],
[1, 3],
[2, 0],
[2, 1],
[2, 2],
[2, 3],
[3, 0],
[3, 1],
[3, 2]
]

N = 4

stack = []
steps = []
positions = []
hash_stack = []

initial = []
position = []
hash_table = set()
for i in range(N):
	a, b, c, d = map(int, input().split())
	if a == 0:
		position.extend([i, 0])
	elif b == 0:
		position.extend([i, 1])
	elif c == 0:
 		position.extend([i, 2])
	elif d == 0:
 		position.extend([i, 3])
	initial.append( [a, b, c, d] )

stack.append(initial)
steps.append(0)
positions.append(position)

hash_table.add(''.join(map(str, initial[0])) + ''.join(map(str, initial[1])) + ''.join(map(str, initial[2])) + ''.join(map(str, initial[3])))
hash_stack.append(hash_table)


limit = 45


def calc_heuristic(state):
	dis_sum = 0
	for i in range(N):
		for j in range(N):
			if state[i][j] != 0:
				dis_sum += abs(i - goal_position[state[i][j]][0])
				dis_sum += abs(j - goal_position[state[i][j]][1])
	return dis_sum


while len(stack) != 0:
	state = stack.pop()
	step = steps.pop()
	position = positions.pop()
	hash_table = hash_stack.pop()

	step += 1

	if position[0] < 3:
		child = [x[:] for x in state]
		child[position[0]][position[1]] = child[position[0]+1][position[1]]
		child[position[0]+1][position[1]] = 0
		h = calc_heuristic(child)
		child_tuple = ''.join(map(str, child[0])) + ''.join(map(str, child[1])) + ''.join(map(str, child[2])) + ''.join(map(str, child[3]))
		if h == 0:
			limit = step
			continue
		elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
			stack.append(child)
			steps.append(step)
			positions.append([position[0]+1, position[1]])

			hash_tmp = hash_table.copy()
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)

	if position[1] < 3:
		child = [x[:] for x in state]
		child[position[0]][position[1]] = child[position[0]][position[1]+1]
		child[position[0]][position[1]+1] = 0
		h = calc_heuristic(child)
		child_tuple = ''.join(map(str, child[0])) + ''.join(map(str, child[1])) + ''.join(map(str, child[2])) + ''.join(map(str, child[3]))
		if h == 0:
			limit = step
			continue
		elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
			stack.append(child)
			steps.append(step)
			positions.append([position[0], position[1]+1])

			hash_tmp = hash_table.copy()
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[0] > 0:
		child = [x[:] for x in state]
		child[position[0]][position[1]] = child[position[0]-1][position[1]]
		child[position[0]-1][position[1]] = 0
		h = calc_heuristic(child)
		child_tuple = ''.join(map(str, child[0])) + ''.join(map(str, child[1])) + ''.join(map(str, child[2])) + ''.join(map(str, child[3]))
		if h == 0:
			limit = step
			continue
		elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
			stack.append(child)
			steps.append(step)
			positions.append([position[0]-1, position[1]])

			hash_tmp = hash_table.copy()
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[1] > 0:
		child = [x[:] for x in state]
		child[position[0]][position[1]] = child[position[0]][position[1]-1]
		child[position[0]][position[1]-1] = 0
		h = calc_heuristic(child)
		child_tuple = ''.join(map(str, child[0])) + ''.join(map(str, child[1])) + ''.join(map(str, child[2])) + ''.join(map(str, child[3]))
		if h == 0:
			limit = step
			continue
		elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
			stack.append(child)
			steps.append(step)
			positions.append([position[0], position[1]-1])

			hash_tmp = hash_table.copy()
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)



print(limit)

Submission status: Time Limit Exceeded

Solution code:
goal = ((1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 0))
goal_position = [
[3, 3],
[0, 0],
[0, 1],
[0, 2],
[0, 3],
[1, 0],
[1, 1],
[1, 2],
[1, 3],
[2, 0],
[2, 1],
[2, 2],
[2, 3],
[3, 0],
[3, 1],
[3, 2]
]

N = 4

stack = []
steps = []
positions = []
hash_stack = []

initial = []
init_position = []
init_hash_table = set()
for i in range(N):
	a, b, c, d = map(int, input().split())
	if a == 0:
		init_position.extend([i, 0])
	elif b == 0:
		init_position.extend([i, 1])
	elif c == 0:
 		init_position.extend([i, 2])
	elif d == 0:
 		init_position.extend([i, 3])
	initial.append( [a, b, c, d] )

init_hash_table.add(tuple(initial[0]) + tuple(initial[1]) + tuple(initial[2]) + tuple(initial[3]))

def calc_heuristic(state):
	dis_sum = 0
	for i in range(N):
		for j in range(N):
			if state[i][j] != 0:
				dis_sum += abs(i - goal_position[state[i][j]][0])
				dis_sum += abs(j - goal_position[state[i][j]][1])
	return dis_sum


limit = calc_heuristic(initial)

while True:
	limit_init = limit

	stack.append(initial)
	steps.append(0)
	positions.append(init_position)

	hash_stack.append(init_hash_table)

	while len(stack) != 0:

		state = stack.pop()
		step = steps.pop()
		position = positions.pop()
		hash_table = hash_stack.pop()

		step += 1

		if position[0] < 3:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]+1][position[1]]
			child[position[0]+1][position[1]] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				continue
			elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
				stack.append(child)
				steps.append(step)
				positions.append([position[0]+1, position[1]])

				hash_tmp = hash_table.copy()
				hash_tmp.add(child_tuple)
				hash_stack.append(hash_tmp)

		if position[1] < 3:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]][position[1]+1]
			child[position[0]][position[1]+1] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				continue
			elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
				stack.append(child)
				steps.append(step)
				positions.append([position[0], position[1]+1])

				hash_tmp = hash_table.copy()
				hash_tmp.add(child_tuple)
				hash_stack.append(hash_tmp)


		if position[0] > 0:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]-1][position[1]]
			child[position[0]-1][position[1]] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				continue
			elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
				stack.append(child)
				steps.append(step)
				positions.append([position[0]-1, position[1]])

				hash_tmp = hash_table.copy()
				hash_tmp.add(child_tuple)
				hash_stack.append(hash_tmp)


		if position[1] > 0:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]][position[1]-1]
			child[position[0]][position[1]-1] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				continue
			elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
				stack.append(child)
				steps.append(step)
				positions.append([position[0], position[1]-1])

				hash_tmp = hash_table.copy()
				hash_tmp.add(child_tuple)
				hash_stack.append(hash_tmp)

	if limit_init != limit:
		break
	else :
		limit += 2

print(limit)

Submission status: Time Limit Exceeded

Solution code:
goal = ((1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 0))
goal_position = [
[3, 3],
[0, 0],
[0, 1],
[0, 2],
[0, 3],
[1, 0],
[1, 1],
[1, 2],
[1, 3],
[2, 0],
[2, 1],
[2, 2],
[2, 3],
[3, 0],
[3, 1],
[3, 2]
]

N = 4

stack = []
steps = []
positions = []
hash_stack = []

initial = []
init_position = []
init_hash_table = set()
for i in range(N):
	a, b, c, d = map(int, input().split())
	if a == 0:
		init_position.extend([i, 0])
	elif b == 0:
		init_position.extend([i, 1])
	elif c == 0:
 		init_position.extend([i, 2])
	elif d == 0:
 		init_position.extend([i, 3])
	initial.append( [a, b, c, d] )

init_hash_table.add(tuple(initial[0]) + tuple(initial[1]) + tuple(initial[2]) + tuple(initial[3]))

def calc_heuristic(state):
	dis_sum = 0
	for i in range(N):
		for j in range(N):
			if state[i][j] != 0:
				dis_sum += abs(i - goal_position[state[i][j]][0])
				dis_sum += abs(j - goal_position[state[i][j]][1])
	return dis_sum


limit = calc_heuristic(initial)
flag = True

while flag:

	stack.append(initial)
	steps.append(0)
	positions.append(init_position)

	hash_stack.append(init_hash_table)

	while len(stack) != 0:

		state = stack.pop()
		step = steps.pop()
		position = positions.pop()
		hash_table = hash_stack.pop()

		step += 1

		if position[0] < 3:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]+1][position[1]]
			child[position[0]+1][position[1]] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				flag = False
				break
			elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
				stack.append(child)
				steps.append(step)
				positions.append([position[0]+1, position[1]])

				hash_tmp = hash_table.copy()
				hash_tmp.add(child_tuple)
				hash_stack.append(hash_tmp)

		if position[1] < 3:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]][position[1]+1]
			child[position[0]][position[1]+1] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				flag = False
				break
			elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
				stack.append(child)
				steps.append(step)
				positions.append([position[0], position[1]+1])

				hash_tmp = hash_table.copy()
				hash_tmp.add(child_tuple)
				hash_stack.append(hash_tmp)


		if position[0] > 0:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]-1][position[1]]
			child[position[0]-1][position[1]] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				flag = False
				break
			elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
				stack.append(child)
				steps.append(step)
				positions.append([position[0]-1, position[1]])

				hash_tmp = hash_table.copy()
				hash_tmp.add(child_tuple)
				hash_stack.append(hash_tmp)


		if position[1] > 0:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]][position[1]-1]
			child[position[0]][position[1]-1] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				flag = False
				break
			elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
				stack.append(child)
				steps.append(step)
				positions.append([position[0], position[1]-1])

				hash_tmp = hash_table.copy()
				hash_tmp.add(child_tuple)
				hash_stack.append(hash_tmp)

	if flag:
		limit += 2

print(limit)

Submission status: Time Limit Exceeded

Solution code:
goal = ((1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 0))
goal_position = [
[3, 3],
[0, 0],
[0, 1],
[0, 2],
[0, 3],
[1, 0],
[1, 1],
[1, 2],
[1, 3],
[2, 0],
[2, 1],
[2, 2],
[2, 3],
[3, 0],
[3, 1],
[3, 2]
]

N = 4

stack = []
steps = []
positions = []
hash_map = {}

initial = []
init_position = []
for i in range(N):
	a, b, c, d = map(int, input().split())
	if a == 0:
		init_position.extend([i, 0])
	elif b == 0:
		init_position.extend([i, 1])
	elif c == 0:
 		init_position.extend([i, 2])
	elif d == 0:
 		init_position.extend([i, 3])
	initial.append( [a, b, c, d] )

init_hash = tuple(initial[0]) + tuple(initial[1]) + tuple(initial[2]) + tuple(initial[3])

def calc_heuristic(state):
	dis_sum = 0
	for i in range(N):
		for j in range(N):
			if state[i][j] != 0:
				dis_sum += abs(i - goal_position[state[i][j]][0])
				dis_sum += abs(j - goal_position[state[i][j]][1])
	return dis_sum


limit = calc_heuristic(initial)
flag = True

while flag:

	stack.append(initial)
	steps.append(0)
	positions.append(init_position)

	hash_map.clear()
	hash_map[init_hash] = 0

	while len(stack) != 0:

		state = stack.pop()
		step = steps.pop()
		position = positions.pop()

		step += 1

		if position[0] < 3:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]+1][position[1]]
			child[position[0]+1][position[1]] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				flag = False
				break
			elif h + step <= limit :
				if child_tuple not in hash_map or hash_map[child_tuple] > step:
					stack.append(child)
					steps.append(step)
					positions.append([position[0]+1, position[1]])
					hash_map[child_tuple] = step

		if position[1] < 3:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]][position[1]+1]
			child[position[0]][position[1]+1] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				flag = False
				break
			elif h + step <= limit :
				if child_tuple not in hash_map or hash_map[child_tuple] > step:
					stack.append(child)
					steps.append(step)
					positions.append([position[0], position[1]+1])
					hash_map[child_tuple] = step


		if position[0] > 0:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]-1][position[1]]
			child[position[0]-1][position[1]] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				flag = False
				break
			elif h + step <= limit :
				if child_tuple not in hash_map or hash_map[child_tuple] > step:
					stack.append(child)
					steps.append(step)
					positions.append([position[0]-1, position[1]])
					hash_map[child_tuple] = step


		if position[1] > 0:
			child = [x[:] for x in state]
			child[position[0]][position[1]] = child[position[0]][position[1]-1]
			child[position[0]][position[1]-1] = 0
			h = calc_heuristic(child)
			child_tuple = tuple(child[0]) + tuple(child[1]) + tuple(child[2]) + tuple(child[3])
			if h == 0:
				limit = step
				flag = False
				break
			elif h + step <= limit :
				if child_tuple not in hash_map or hash_map[child_tuple] > step:
					stack.append(child)
					steps.append(step)
					positions.append([position[0], position[1]-1])
					hash_map[child_tuple] = step

	if flag:
		limit += 2

print(limit)

Submission status: Time Limit Exceeded

Solution code:

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, N2 = 4, 16
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
dir = ['r', 'u', 'l', 'd']
MDT = [[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, field=None, space=None, MD=None, cost=None):
        self.field = field
        self.space = space
        self.MD = MD
        self.cost = cost

    def __lt__(self, pzl): # <
        for i in range(N2):
            if self.field[i] == pzl.field[i]:
                continue
            return self.field[i] > pzl.field[i]
        return False

    def set_MD(self):
        sum = 0
        for i in range(N2):
            if self.field[i] == N2: continue
            sum += MDT[i][self.field[i]-1]
        self.MD = sum

class State():
    def __init__(self, pzl=None, estimated=None):
        self.puzzle = pzl
        self.estimated = estimated

    def __lt__(self, stat):
        return self.estimated < stat.estimated

def astar(pzl):
    pqueue = []
    pzl.set_MD()
    pzl.cost = 0
    V = {}
    u, v = Puzzle(), Puzzle()
    initial = State(pzl, pzl.MD)
    heapq.heappush(pqueue, initial)

    while len(pqueue) != 0:
        st = heapq.heappop(pqueue)
        u = st.puzzle
        
        if u.MD == 0: return u.cost
        V[str(u.field)] = True

        sx = u.space//N
        sy = u.space%N
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= N or ty >= N: continue
            v = Puzzle(field=[u.field[i] for i in range(N2)], space=u.space, MD=u.MD, cost=u.cost)

            v.MD -= MDT[tx*N + ty][v.field[tx*N + ty]-1]
            v.MD += MDT[sx*N + sy][v.field[tx*N + ty]-1]

            v.field[sx*N + sy], v.field[tx*N + ty] = v.field[tx*N + ty], v.field[sx*N + sy]
            v.space = tx*N + ty
            if not V.get(str(v.field)):
                v.cost += 1
                news = State()
                news.puzzle = v
                news.estimated = v.cost + v.MD
                heapq.heappush(pqueue, news)
    return -1

field = []
for i in range(4):
    field.extend(list(map(int, input().split(' '))))

space = None
for i in range(N2):
    if field[i] == 0:
        field[i] = N2
        space = i
        break

s = Puzzle(field=field, space=space)
print(astar(s))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, N2 = 4, 16
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
dir = ['r', 'u', 'l', 'd']
MDT = [[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, field=None, space=None, MD=None, cost=None):
        self.field = field
        self.space = space
        self.MD = MD
        self.cost = cost

    def __lt__(self, pzl): # <
        for i in range(N2):
            if self.field[i] == pzl.field[i]:
                continue
            return self.field[i] > pzl.field[i]
        return False

    def set_MD(self):
        sum = 0
        for i in range(N2):
            if self.field[i] == N2: continue
            sum += MDT[i][self.field[i]-1]
        self.MD = sum

class State():
    def __init__(self, pzl=None, estimated=None):
        self.puzzle = pzl
        self.estimated = estimated

    def __lt__(self, stat):
        return self.estimated < stat.estimated

def astar(pzl):
    pqueue = []
    pzl.set_MD()
    pzl.cost = 0
    V = {}
    u, v = Puzzle(), Puzzle()
    initial = State(pzl, pzl.MD)
    heapq.heappush(pqueue, initial)

    if pzl.MD == 0: return pzl.cost

    while len(pqueue) != 0:
        st = heapq.heappop(pqueue)
        u = st.puzzle

        V[str(u.field)] = True

        sx = u.space//N
        sy = u.space%N
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= N or ty >= N: continue
            v = Puzzle(field=[u.field[i] for i in range(N2)], space=u.space, MD=u.MD, cost=u.cost)

            v.MD -= MDT[tx*N + ty][v.field[tx*N + ty]-1]
            v.MD += MDT[sx*N + sy][v.field[tx*N + ty]-1]

            v.field[sx*N + sy], v.field[tx*N + ty] = v.field[tx*N + ty], v.field[sx*N + sy]
            v.space = tx*N + ty
            if not V.get(str(v.field)):
                v.cost += 1
                if v.MD == 0: return v.cost
                news = State()
                news.puzzle = v
                news.estimated = v.cost + v.MD
                heapq.heappush(pqueue, news)
    return -1

field = []
for i in range(4):
    field.extend(list(map(int, input().split(' '))))

space = None
for i in range(N2):
    if field[i] == 0:
        field[i] = N2
        space = i
        break

s = Puzzle(field=field, space=space)
print(astar(s))

Submission status: Time Limit Exceeded

Solution code:
import heapq, copy

N, N2 = 4, 16
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
dir = ['r', 'u', 'l', 'd']
MDT = [[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, field=None, space=None, MD=None, cost=None):
        self.field = field
        self.space = space
        self.MD = MD
        self.cost = cost

    def __lt__(self, pzl): # <
        for i in range(N2):
            if self.field[i] == pzl.field[i]:
                continue
            return self.field[i] > pzl.field[i]
        return False

    def set_MD(self):
        sum = 0
        for i in range(N2):
            if self.field[i] == N2: continue
            sum += MDT[i][self.field[i]-1]
        self.MD = sum

class State():
    def __init__(self, pzl=None, estimated=None):
        self.puzzle = pzl
        self.estimated = estimated

    def __lt__(self, stat):
        return self.estimated < stat.estimated

def astar(pzl):
    pqueue = []
    pzl.set_MD()
    pzl.cost = 0
    V = {}
    u, v = Puzzle(), Puzzle()
    initial = State(pzl, pzl.MD)
    heapq.heappush(pqueue, initial)

    if pzl.MD == 0: return pzl.cost

    while len(pqueue) != 0:
        st = heapq.heappop(pqueue)
        u = st.puzzle

        V[str(u.field)] = True

        sx = u.space//N
        sy = u.space%N
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= N or ty >= N: continue
            v = Puzzle(field=copy.copy(u.field), space=u.space, MD=u.MD, cost=u.cost)

            v.MD -= MDT[tx*N + ty][v.field[tx*N + ty]-1]
            v.MD += MDT[sx*N + sy][v.field[tx*N + ty]-1]

            v.field[sx*N + sy], v.field[tx*N + ty] = v.field[tx*N + ty], v.field[sx*N + sy]
            v.space = tx*N + ty
            if not V.get(str(v.field)):
                v.cost += 1
                if v.MD == 0: return v.cost
                news = State()
                news.puzzle = v
                news.estimated = v.cost + v.MD
                heapq.heappush(pqueue, news)
    return -1

field = []
for i in range(4):
    field.extend(list(map(int, input().split(' '))))

space = None
for i in range(N2):
    if field[i] == 0:
        field[i] = N2
        space = i
        break

s = Puzzle(field=field, space=space)
print(astar(s))

Submission status: Time Limit Exceeded

Solution code:
class Puzzle:
    def __init__(self, state):
        self.WIDTH = 4
        self.HIGHT = 4

        self.state = state
        self.x, self.y = self.idx_to_xy(self.state.index('0'))

    def idx_to_xy(self, idx):
        return idx % self.HIGHT, idx // self.WIDTH

    def xy_to_idx(self, x, y):
        return y * self.WIDTH + x

    def swap(self, x, y):
        zero = self.xy_to_idx(self.x, self.y)
        idx = self.xy_to_idx(x, y)

        tmp = self.state[zero]
        self.state[zero] = self.state[idx]
        self.state[idx] = tmp

        self.x, self.y = x, y
    
    def is_completed(self):
        for i in range(1, 16):
            if self.state[i - 1] != str(i):
                return False
        return True
    
    def pretty_print(self):
        for r in range(self.HIGHT):
            print(self.state[r*self.WIDTH:(r+1)*self.WIDTH])

from sys import stdin
def stdinput():
    return stdin.readline().strip()

MAX_ITER = 45
def shortest_steps(p, iter, cache):
    # print(iter)
    # p.pretty_print()
    key = ' '.join(p.state)
    if key in cache and cache[key][0] < 10**3:
        return cache[key]
    elif p.is_completed():
        return 0, [p]
    else:
        if iter == MAX_ITER:
            return 10**3, [p]
        else:
            canditees = []
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                next_x = p.x + dx
                next_y = p.y + dy
                if 0 <= next_x and next_x < p.WIDTH and 0 <= next_y and next_y < p.HIGHT:
                    next_p = Puzzle(list(p.state))
                    next_p.swap(next_x, next_y)
                    canditees.append(next_p)
            steps, hist  = min(map(lambda np: shortest_steps(np, iter+1, cache), canditees),key=lambda i:i[0])
            steps += 1
            hist = list(hist)
            hist.append(p)
            cache[key] = [steps, hist]
            return steps, hist

def main():
    puzzle = Puzzle(stdinput().split() + stdinput().split() +stdinput().split() +stdinput().split())
    steps, hist = shortest_steps(puzzle, 0, {})
    print(steps)

if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
import collections

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

Solution code:
# coding=utf-8
import heapq as hq

def get_next_board(board, space):
    for next_space in adjacent[space]:
        next_board = board.copy()
        next_board[space], next_board[next_space] = next_board[next_space], 0
        yield next_board, next_space

def search(start):
    if start == goal:
        return 0

    while heap:
        i, board, space, prev, direction = hq.heappop(heap)
        i += 1
        for next_board, next_space in get_next_board(board, space):
            key = tuple(next_board)
            if key in arrive:
                if arrive[key][0] != direction:
                    return arrive[key][1] + i
            else:
                arrive[key] = (direction, i)
            hq.heappush(heap, (i, next_board, next_space, space, direction))

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 = [i for i in range(1, 16)]
goal += [0]
start = []
arrive = {}
FORE = 1
BACK = -1

for _ in range(4):
    x = list(map(int, input().split()))
    start += x

arrive[tuple(start)] = (FORE, 0)
arrive[tuple(goal)] = (BACK, 0)
heap = [(0, start, start.index(0), None, FORE), (0, goal, goal.index(0), None, BACK)]

print(search(start))