以下是在Windows环境下使用Python 3.x实现八数码问题的深度优先搜索（DFS）和广度优先搜索（BFS）的代码示例： ```python from collections import deque # 目标状态 goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]] # 定义节点类 class Node: def __init__(self, state, parent=None, action=None): self.state = state self.parent = parent self.action = action def __eq__(self, other): return self.state == other.state def __hash__(self): return hash(str(self.state)) # 找到空白块的位置 def find_blank(state): for i in range(3): for j in range(3): if state[i][j] == 0: return i, j # 生成可能的后继状态 def get_successors(node): successors = [] i, j = find_blank(node.state) moves = [(0, 1), (0, -1), (1, 0), (-1, 0)] for di, dj in moves: ni, nj = i + di, j + dj if 0 <= ni < 3 and 0 <= nj < 3: new_state = [row[:] for row in node.state] new_state[i][j], new_state[ni][nj] = new_state[ni][nj], new_state[i][j] new_node = Node(new_state, node, (di, dj)) successors.append(new_node) return successors # 深度优先搜索 def dfs(initial_state): stack = [Node(initial_state)] visited = set() while stack: current_node = stack.pop() if current_node.state == goal_state: path = [] while current_node: path.append(current_node) current_node = current_node.parent return path[::-1] if str(current_node.state) not in visited: visited.add(str(current_node.state)) successors = get_successors(current_node) stack.extend(successors) return None # 广度优先搜索 def bfs(initial_state): queue = deque([Node(initial_state)]) visited = set() while queue: current_node = queue.popleft() if current_node.state == goal_state: path = [] while current_node: path.append(current_node) current_node = current_node.parent return path[::-1] if str(current_node.state) not in visited: visited.add(str(current_node.state)) successors = get_successors(current_node) queue.extend(successors) return None # 示例初始状态 initial_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]] # 执行深度优先搜索 dfs_path = dfs(initial_state) if dfs_path: print("DFS路径找到：") for node in dfs_path: print(node.state) else: print("DFS未找到路径") # 执行广度优先搜索 bfs_path = bfs(initial_state) if bfs_path: print("BFS路径找到：") for node in bfs_path: print(node.state) else: print("BFS未找到路径") ```