class solution: def salvepuzzle(self, init, targ): ''' 求解8数码问题 参数: i
时间: 2023-12-25 15:01:24 浏览: 37
class Solution:
def salvepuzzle(self, init, targ):
'''解决8数码问题 参数: init - 初始状态的列表 targ - 目标状态的列表'''
# 定义一个列表,用于表示数码的移动方向
direction = ["上", "下", "左", "右"]
# 定义一个队列,用于存储状态
queue = [init]
# 定义一个集合,用于存储已经访问过的状态
visited = set()
# 定义一个字典,用于存储每个状态对应的移动步骤
step = {tuple(init): 0}
while queue:
# 从队列中取出第一个状态
current = queue.pop(0)
# 如果当前状态和目标状态相同,则返回移动步骤
if current == targ:
return step[tuple(current)]
# 遍历当前状态的每一个位置
for i in range(9):
if current[i] == 0:
break
# 分别尝试向上下左右移动
for d in [-3, 3, -1, 1]:
new_i = i + d
# 如果新位置合法
if 0 <= new_i < 9 and not (i in [2, 5] and d == 1) and not (i in [3, 6] and d == -1):
new_state = current[:]
new_state[i], new_state[new_i] = new_state[new_i], new_state[i]
if tuple(new_state) not in visited:
queue.append(new_state)
visited.add(tuple(new_state))
step[tuple(new_state)] = step[tuple(current)] + 1
# 如果未能找到解法,返回-1
return -1
# 调用函数
s = Solution()
init = [1, 2, 3, 4, 0, 5, 6, 7, 8]
targ = [1, 2, 3, 4, 5, 8, 6, 0, 7]
print(s.salvepuzzle(init, targ))