八数码难题代码及其注释

这里提供一份 Python 代码及其注释，用来求解八数码难题。

# 八数码难题代码及其注释

# 定义一个八数码类
class EightPuzzle:
# 初始化函数，输入初始状态和目标状态
def __init__(self, init_state, goal_state):
self.init_state = init_state
self.goal_state = goal_state
self.width = 3 # 定义八数码矩阵的宽度
self.actions = ['Up', 'Down', 'Left', 'Right'] # 定义可行的操作

# 定义状态转换函数，返回一个新状态
def move(self, state, action):
new_state = state.copy() # 复制当前状态
index = new_state.index(0) # 找到空格的位置
if action == 'Up' and index > self.width - 1:
new_state[index], new_state[index - self.width] = new_state[index - self.width], new_state[index]
elif action == 'Down' and index < len(state) - self.width:
new_state[index], new_state[index + self.width] = new_state[index + self.width], new_state[index]
elif action == 'Left' and index % self.width != 0:
new_state[index], new_state[index - 1] = new_state[index - 1], new_state[index]
elif action == 'Right' and (index + 1) % self.width != 0:
new_state[index], new_state[index + 1] = new_state[index + 1], new_state[index]
else:
return None # 如果操作不可行，返回 None
return new_state

# 定义状态比较函数
def state_equal(self, state1, state2):
return state1 == state2

# 定义启发函数，使用曼哈顿距离
def heuristic(self, state):
distance = 0
for i in range(self.width):
for j in range(self.width):
value = state[i * self.width + j]
if value != 0:
goal_i = (value - 1) // self.width
goal_j = (value - 1) % self.width
distance += abs(i - goal_i) + abs(j - goal_j)
return distance

# 定义 A* 算法
def A_star(self):
open_list = [(self.init_state, 0, self.heuristic(self.init_state))] # 存储未扩展的结点，包括状态、代价和启发值
closed_list = [] # 存储已经扩展的结点
parent = {self.init_state: None} # 存储每个状态的父结点，用于还原路径

while open_list:
current_state, current_cost, current_heuristic = min(open_list, key=lambda x: x[1] + x[2]) # 选择代价和启发值之和最小的结点进行扩展
open_list.remove((current_state, current_cost, current_heuristic))
closed_list.append(current_state)

if self.state_equal(current_state, self.goal_state): # 如果当前状态为目标状态，则返回路径
path = [current_state]
while parent[path[0]] is not None:
path.insert(0, parent[path[0]])
return path

for action in self.actions: # 扩展所有可行的操作
new_state = self.move(current_state, action)
if new_state is not None and new_state not in closed_list: # 如果新状态可行且未被扩展过，则加入 open_list 中
new_cost = current_cost + 1
new_heuristic = self.heuristic(new_state)
if (new_state, new_cost, new_heuristic) not in open_list:
open_list.append((new_state, new_cost, new_heuristic))
parent[new_state] = current_state

return None # 如果 open_list 为空，说明无法到达目标状态，返回 None

# 测试代码
if __name__ == '__main__':
init_state = [2, 8, 3, 1, 6, 4, 7, 0, 5]
goal_state = [1, 2, 3, 8, 0, 4, 7, 6, 5]
puzzle = EightPuzzle(init_state, goal_state)
path = puzzle.A_star()
if path is not None:
for state in path:
print(state)
else:
print('No solution')