Language: C++

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)


Compiler output:
a.cc:1:1: error: 'goal' does not name a type
    1 | goal = ((1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 0))
      | ^~~~