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:
# 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
for i in range(N):
    start.append(list(map(int, input().split())))
    check = start[i].count(0)
    if check != 0:
            [s_r, s_c] = [i, start[i].index(0)]


def manhattan(value, pairs):
    h = 0
    if value != 0:
        h = abs(pairs[0] - int((value - 1)/4)) + abs(pairs[1] - (value - 4*int((value - 1)/4) - 1))
    return h

def calculate(queue, d):
    if d > 45:
        return 0
    while len(queue) != 0:
        short_n = queue.pop(0)
        h = short_n[0] - short_n[2]
        state = short_n[1]
        g = short_n[2]
        [r, c] = short_n[3]
        flag = short_n[4]
        #print("left_Q: ", len(queue), "depth: ", d, "h: ", h, "g: ", g, "state: ", state, "g+h: ", short_n[0])
        if h == 0:
            return short_n[2]

        if r - 1 >= 0 and flag != 3:
            temp = copy.deepcopy(state)
            h2 = short_n[0] - short_n[2] - manhattan(temp[r - 1][c], [r - 1, c]) + manhattan(temp[r - 1][c], [r, c])
            [temp[r][c], temp[r - 1][c]] = [temp[r - 1][c], temp[r][c]]
            if g + 1 + h2 <= d:
                queue.append([h2 + g + 1, temp, g + 1, [r - 1, c], 1])

        if c + 1 < N and flag != 4:
            temp = copy.deepcopy(state)
            h2 = short_n[0] - short_n[2] - manhattan(temp[r][c + 1], [r, c + 1]) + manhattan(temp[r][c + 1], [r, c])
            [temp[r][c], temp[r][c + 1]] = [temp[r][c + 1], temp[r][c]]
            if g + 1 + h2 <= d:
                queue.append([h2 + g + 1, temp, g + 1, [r, c + 1], 2])

        if r + 1 < N and flag != 1:
            temp = copy.deepcopy(state)
            h2 = short_n[0] - short_n[2] - manhattan(temp[r + 1][c], [r + 1, c]) + manhattan(temp[r + 1][c], [r, c])
            [temp[r][c], temp[r + 1][c]] = [temp[r + 1][c], temp[r][c]]
            if g + 1 + h2 <= d:
                queue.append([h2 + g + 1, temp, g + 1, [r + 1, c], 3])

        if c - 1 >= 0 and flag != 2:
            temp = copy.deepcopy(state)
            h2 = short_n[0] - short_n[2] - manhattan(temp[r][c - 1], [r, c - 1]) + manhattan(temp[r][c - 1], [r, c])
            [temp[r][c], temp[r][c - 1]] = [temp[r][c - 1], temp[r][c]]
            if g + 1 + h2 <= d:
                queue.append([h2 + g + 1, temp, g + 1, [r, c - 1], 4])
                
        queue.sort(key = lambda data:data[0])
        queue.sort(key = lambda data:data[2], reverse = True)

    return -1

s_h = 0
for i in range(N):
    for j in range(N):
        s_h += manhattan(start[i][j], [i, j])

d = s_h
while True:
    queue = [[s_h, start, 0, [s_r, s_c], 0]]
    result = calculate(queue, d)
    d += 1
    if result >= 0:
        print(result)
        break

Submission status: Time Limit Exceeded

Solution code:
# 幅優先探索 #双方向探索
import sys
import queue

SPACE = 0

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

class State:
    def __init__(self, board, space, prev):
        self.board = board
        self.space = space
        self.prev = prev

def mininum_steps(start, goal):
    if start == goal:
        return 0
    q = queue.Queue()
    q.put(State(start, start.index(0), None))
    history = {} # 辞書は速度上げ
    history[tuple(start)] = True
    while not q.empty():
        state = q.get()
        for adjacent in adjacents_list[state.space]:
            board = state.board[:]
            board[state.space] = board[adjacent]
            board[adjacent] = SPACE
            if tuple(board) in history:
                 continue
            if board == goal:
                return go_back(state)
            history[tuple(board)] = True
            next_state = State(board, adjacent, state)
            q.put(next_state)

step = 0
def go_back(state):
    global step
    if state is not None:
        step += 1
        go_back(state.prev)
    return step


initial_board = list(map(int, sys.stdin.read().split()))
goal = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]

print(mininum_steps(initial_board, goal))

Submission status: Time Limit Exceeded

Solution code:
goal = ((1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 0))
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(tuple(initial))
steps.append(0)
positions.append(position)

hash_table.add(tuple(initial))
hash_stack.append(hash_table)


import sys
limit = 45


def calc_heuristic(state):
	count = 0
	for i in range(N):
		for j in range(N):
			if goal[i][j] != state[i][j]:
				count += 1
	return count


import copy

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 = [list(state[0]), list(state[1]), list(state[2]), list(state[3])]
		child[position[0]][position[1]] = child[position[0]+1][position[1]]
		child[position[0]+1][position[1]] = 0
		child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]), tuple(child[3]))
		h = calc_heuristic(child_tuple)
		if h == 0:
			limit = step
		elif h + step < limit and set(child_tuple).isdisjoint(hash_table):
			stack.append(child_tuple)
			steps.append(step)
			positions.append([position[0]+1, position[1]])

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

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

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


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

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


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

			hash_tmp = copy.deepcopy(hash_table)
			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))
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(tuple(initial))
steps.append(0)
positions.append(position)

hash_table.add(tuple(initial))
hash_stack.append(hash_table)


limit = 45


def calc_heuristic(state):
	count = 0
	for i in range(N):
		for j in range(N):
			if goal[i][j] != state[i][j] and (i != 2 or j != 2):
				count += 1
	return count


import copy

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 = [list(state[0]), list(state[1]), list(state[2]), list(state[3])]
		child[position[0]][position[1]] = child[position[0]+1][position[1]]
		child[position[0]+1][position[1]] = 0
		child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]), tuple(child[3]))
		h = calc_heuristic(child_tuple)
		if h == 0:
			limit = step
		elif h + step <= limit and set(child_tuple).isdisjoint(hash_table):
			stack.append(child_tuple)
			steps.append(step)
			positions.append([position[0]+1, position[1]])

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

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

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


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

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


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

			hash_tmp = copy.deepcopy(hash_table)
			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))
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((tuple(initial[0]), tuple(initial[1]), tuple(initial[2]), tuple(initial[3])))
hash_stack.append(hash_table)


limit = 45


def calc_heuristic(state):
	count = 0
	for i in range(N):
		for j in range(N):
			if goal[i][j] != state[i][j] and (i != 2 or j != 2):
				count += 1
	return count


import copy

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 = copy.deepcopy(state)
		child[position[0]][position[1]] = child[position[0]+1][position[1]]
		child[position[0]+1][position[1]] = 0
		child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]), tuple(child[3]))
		h = calc_heuristic(child_tuple)
		if h == 0:
			limit = step
		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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)

	if position[1] < 3:
		child = copy.deepcopy(state)
		child[position[0]][position[1]] = child[position[0]][position[1]+1]
		child[position[0]][position[1]+1] = 0
		child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]), tuple(child[3]))
		h = calc_heuristic(child_tuple)
		if h == 0:
			limit = step
		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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[0] > 0:
		child = copy.deepcopy(state)
		child[position[0]][position[1]] = child[position[0]-1][position[1]]
		child[position[0]-1][position[1]] = 0
		child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]), tuple(child[3]))
		h = calc_heuristic(child_tuple)
		if h == 0:
			limit = step
		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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[1] > 0:
		child = copy.deepcopy(state)
		child[position[0]][position[1]] = child[position[0]][position[1]-1]
		child[position[0]][position[1]-1] = 0
		child_tuple = (tuple(child[0]), tuple(child[1]), tuple(child[2]), tuple(child[3]))
		h = calc_heuristic(child_tuple)
		if h == 0:
			limit = step
		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 = copy.deepcopy(hash_table)
			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))
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(tuple(initial[0]) + tuple(initial[1]) + tuple(initial[2]) + tuple(initial[3]))
hash_stack.append(hash_table)


limit = 45


def calc_heuristic(state):
	count = 0
	for i in range(N):
		for j in range(N):
			if goal[i][j] != state[i][j] and (i != 2 or j != 2):
				count += 1
	return count


import copy

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 = copy.deepcopy(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
		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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)

	if position[1] < 3:
		child = copy.deepcopy(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
		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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[0] > 0:
		child = copy.deepcopy(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
		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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[1] > 0:
		child = copy.deepcopy(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
		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 = copy.deepcopy(hash_table)
			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 = []
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(tuple(initial[0]) + tuple(initial[1]) + tuple(initial[2]) + tuple(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


import copy

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 = copy.deepcopy(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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)

	if position[1] < 3:
		child = copy.deepcopy(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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[0] > 0:
		child = copy.deepcopy(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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[1] > 0:
		child = copy.deepcopy(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 = copy.deepcopy(hash_table)
			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 = []
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(tuple(initial[0]) + tuple(initial[1]) + tuple(initial[2]) + tuple(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


import copy

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

	step += 1

	if position[0] > 0:
		child = copy.deepcopy(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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[1] > 0:
		child = copy.deepcopy(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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)


	if position[0] < 3:
		child = copy.deepcopy(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 = copy.deepcopy(hash_table)
			hash_tmp.add(child_tuple)
			hash_stack.append(hash_tmp)

	if position[1] < 3:
		child = copy.deepcopy(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 = copy.deepcopy(hash_table)
			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 = []
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(tuple(initial[0]) + tuple(initial[1]) + tuple(initial[2]) + tuple(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 = 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)



print(limit)