8-puzzle数码游戏

大家好，欢迎来到IT知识分享网。

8数码问题

8数码问题，也被称为“滑动谜题”或“数字方块谜题”，是一个经典的益智游戏和计算机科学中的一个常见问题，用于演示搜索算法如广度优先搜索（BFS）、深度优先搜索（DFS）、A*搜索等。

在这个问题中，有一个3×3的矩阵，里面填充了数字1到8，以及一个空格。目标是从一个随机的初始配置移动数字，使得它们按照某种顺序排列，通常是按行从左至右，从上至下递增，而空格在矩阵的最右下角。数字只能水平或垂直移动到空格位置，不能斜向移动。

玩家或算法的任务是通过一系列合法的移动，将初始布局转换为目标布局。这种问题可以用来测试和比较不同搜索算法的效率，因为算法需要找到从任意初始状态到达目标状态所需的最少步数。

puzzle类的实现

定义一个类，记录puzzle状态的基本信息（state,parent,action,path_cost,needs_hueristic）。
下面对各个名词进行解释：

• state(当前状态)：当前九宫格各个位置的值
• parent(父节点)：上一步的状态，就是当前状态是从哪一步变来的
• action(动作)：表示上一步即父节点是通过是通过上下左右（“U”,“D”,“L”,“R”）哪一步变来的，每执行完一个动作，状态就更新一次
• path_cost(路径成本)：执行动作的次数，一般执行一次动作的成本为1
• needs_hueristic(是否需要启发式函数)：需要启发式函数为True，不需要为False，一般使用启发式算法时设为True

 def __init__(self,state,parent,action,path_cost,needs_hueristic=False): self.parent=parent # 父节点 self.state=state # 当前状态，状态即为当前九宫格的数值 self.action=action if parent: self.path_cost = parent.path_cost + path_cost # 如果有父节点，就把父节点的路径加上 else: self.path_cost = path_cost if needs_hueristic: self.needs_hueristic=True self.generate_heuristic() # 产生启发式函数 self.evaluation_function=self.heuristic+self.path_cost # 评估函数 Puzzle.num_of_instances+=1 

启发式函数

当需要启发式函数时就会产生启发式函数generate_heuristic，而此时的成本就不只是路径成本，还包括启发式成本，启发式成本越大，表示到达目标状态的难度越大，反之，启发式成本越小，表示到达目标状态越容易。启发式成本加上原本的路径成本表示总成本，这里我们用evaluation_function表示。

• 这里根据当前状态和目标状态进行比较，根据准确度来表示启发式成本。

 def generate_heuristic(self): # 产生启发式函数 self.heuristic=0 # 启发式成本初始化为0 """ 实现八数码问题的启发式信息值计算，计算出来赋值给self.heuristic。 提示：根据self.state和self.goal_state中一些值进行计算。 """ for i in range(len(self.state)): # 根据状态和目标状态进行比较 if self.state[i] != self.goal_state[i]: self.heuristic += 1 

产生子节点的方法

在产生子节点之前，我们要知道如何才能产生子节点，前面说过，每移动一步就会产生一个新的状态，每一个新的状态都表示一个子节点，在产生新的子节点之前，要先弄清楚如何移动。通过移动空格的位置（在这里我们空格的位置用0表示）来实现动作的执行，实现状态的转换，产生新的子节点。

• 动作的执行
  空格的位置不同，从而能够执行的动作的选项也就不同，比如当空格在第一行的时候，空格就不能往上走，就要把向上的步骤移除。当在第一列的时候就不能向左走，就要把向左走的步骤移除。

 def find_legal_actions(i,j): legal_action = ['U', 'D', 'L', 'R'] # (上，下，左，右) if i == 0: # 如果是九宫格第一行的数，就不能往上走 legal_action.remove('U') # 移除向上“U” elif i == 2: # 如果是第三行就不能往下走 legal_action.remove('D') # 移除向下“D” if j == 0: legal_action.remove('L') elif j == 2: legal_action.remove('R') return legal_action 

• 子节点的产生
  获取空格（数字0）的索引，从而得到空格表示的行数和列数，遍历空格能走的所有方向从而得到所有的子节点。

 def generate_child(self): children=[] x = self.state.index(0) #数字0的索引 i = int(x / 3)# 行数 j = int(x % 3)# 列数 legal_actions=self.find_legal_actions(i,j) # 把不能走的方向去掉 for action in legal_actions: new_state = self.state.copy() # 创建副本 if action == 'U':# 上移 new_state[x], new_state[x-3] = new_state[x-3], new_state[x] # 数字0和它上面那个值交换位置 elif action == 'D': new_state[x], new_state[x+3] = new_state[x+3], new_state[x] elif action == 'L': new_state[x], new_state[x-1] = new_state[x-1], new_state[x] elif action == 'R': new_state[x], new_state[x+1] = new_state[x+1], new_state[x] children.append(Puzzle(new_state,self,action,1,self.needs_hueristic)) # 每一步产生一个子节点，路径成本为1 return children 

• 获得解题步骤
  因为每一步都有表示父节点，只需要每一步的父节点连起来就可以表示解题的步骤。

 def find_solution(self): solution = [] # 储存解题步骤 solution.append(self.action) path = self # 创建一个变量path并将其设置为当前Puzzle对象，即解题路径的当前节点 while path.parent != None: # 加上父节点的路径 path = path.parent solution.append(path.action) solution = solution[:-1] # 去除最后一个元素，根节点的动作 solution.reverse() # 反转列表 return solution 

广度优先搜索

广度优先搜索（Breadth-First Search，简称BFS）是一种用于图和树数据结构的搜索算法。它的基本思想是从根节点（选择的起始节点）开始，然后探索尽可能近的所有节点，然后再移至下一层节点，依此类推，直到找到目标节点或遍历完整个图。
使用队列先进先出（FIFO）的思想很容易实现广度优先搜索，遍历子节点之后，子节点被加入到open表，当从open中遍历的时候，会最先遍历最先加进去的那一批子节点（即最开始从根节点的所有action后产生的子节点，这些节点的path_cost都为1）。

from queue import Queue from puzzle import Puzzle def breadth_first_search(initial_state): start_node = Puzzle(initial_state, None, None, 0) q = Queue() #FOFI q.put(start_node) explored=[] # 记录已经探索过的状态 while not(q.empty()): node=q.get() if node.goal_test(): return node.find_solution() explored.append(node.state) children=node.generate_child() # 生成所有可能的子节点 for child in children: if child.state not in explored: q.put(child) return 

深度优先搜索

from puzzle import Puzzle class Stack: # 定义栈 def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def is_empty(self): return not bool(self.items) def size(self): return len(self.items) def depth_first_search(initial_state): start_node = Puzzle(initial_state, None, None, 0) stack = Stack() # 使用栈代替队列 stack.push(start_node) explored = [] while not stack.is_empty(): node = stack.pop() # 从栈顶取出节点 if node.goal_test(): return node.find_solution() explored.append(node.state) children = node.generate_child() for child in children: if child.state not in explored: stack.push(child) # 将子节点压入栈中 return 

A*算法

from queue import PriorityQueue # 优先队列：在队列中按照优先级进行处理 from puzzle import Puzzle def Astar_search(initial_state): start_node = Puzzle(initial_state, None, None, 0,needs_hueristic=True) priority_queue = PriorityQueue() # 使用优先队列：优先级高的先处理 初始化open_list priority_queue.put((0, start_node)) # 评估函数初始优先级为0 explored = set() # close_list while not priority_queue.empty():# 当优先队列不为空时 _, current_node = priority_queue.get() # 获取当前最小成本的节点，忽略第一个元素，current_node是puzzle类的一个实例 if current_node.goal_test(): # 判断是否满足目标状态 return current_node.find_solution() # 如果满足就返回路径 explored.add(tuple(current_node.state)) # 节点加入close_list children = current_node.generate_child() # 产生子节点 for child in children: # 遍历所有的子节点 if tuple(child.state) not in explored: # 如果子节点的状态没有走过，就加入优先队列 # 计算A*评估函数：实际路径成本 + 启发式成本 child.evaluation_function = child.path_cost + child.heuristic priority_queue.put((child.evaluation_function, child)) return "No solution found" 

示范

from time import time from BFS_search import breadth_first_search from DFS_search import depth_first_search from Astar_search import Astar_search from puzzle import Puzzle state=[[1, 3, 4, 8, 6, 2, 7, 0, 5], [2, 8, 1, 0, 4, 3, 7, 6, 5], [2, 8, 1, 4, 6, 3, 0, 7, 5]] for i in range(0,1): Puzzle.num_of_instances=0 t0=time() bfs=breadth_first_search(state[i]) t1=time()-t0 print('BFS:', bfs) print('space:',Puzzle.num_of_instances) print('time:',t1) print() Puzzle.num_of_instances = 0 t0 = time() dfs = depth_first_search(state[i]) t1 = time() - t0 print('DFS:',dfs) print('space:', Puzzle.num_of_instances) print('time:', t1) print() Puzzle.num_of_instances = 0 t0 = time() astar = Astar_search(state[i]) t1 = time() - t0 print('A*:',astar) print('space:', Puzzle.num_of_instances) print('time:', t1) print() print('------------------------------------------') 

puzzle类代码实现

class Puzzle: goal_state=[1,2,3,8,0,4,7,6,5] # 0表示空位 heuristic=None # 启发式信息值 evaluation_function=None # 评估启发式函数 needs_hueristic=False #是否需要启发式函数 num_of_instances=0 # puzzle类被创建的次数 def __init__(self,state,parent,action,path_cost,needs_hueristic=False): self.parent=parent # 父节点 self.state=state # 当前状态，状态即为当前九宫格的数值 self.action=action if parent: self.path_cost = parent.path_cost + path_cost # 如果有父节点，就把父节点的路径加上 else: self.path_cost = path_cost if needs_hueristic: self.needs_hueristic=True self.generate_heuristic() # 产生启发式函数 self.evaluation_function=self.heuristic+self.path_cost # 评估函数 Puzzle.num_of_instances+=1 def __str__(self): # 打印状态，九宫格形式 return str(self.state[0:3])+'\n'+str(self.state[3:6])+'\n'+str(self.state[6:9]) def generate_heuristic(self): # 产生启发式函数 self.heuristic=0 # 启发式成本初始化为0 """ 实现八数码问题的启发式信息值计算，计算出来赋值给self.heuristic。 提示：根据self.state和self.goal_state中一些值进行计算。 """ for i in range(len(self.state)): # 根据状态和目标状态进行比较 if self.state[i] != self.goal_state[i]: self.heuristic += 1 def goal_test(self): if self.state == self.goal_state: return True return False @staticmethod def find_legal_actions(i,j): legal_action = ['U', 'D', 'L', 'R'] # (上，下，左，右) if i == 0: # 如果是九宫格第一行的数，就不能往上走 legal_action.remove('U') # 移除向上“U” elif i == 2: # 如果是第三行就不能往下走 legal_action.remove('D') # 移除向下“D” if j == 0: legal_action.remove('L') elif j == 2: legal_action.remove('R') return legal_action def generate_child(self): children=[] x = self.state.index(0) #数字0的索引 i = int(x / 3)# 行数 j = int(x % 3)# 列数 legal_actions=self.find_legal_actions(i,j) # 把不能走的方向去掉 for action in legal_actions: new_state = self.state.copy() # 创建副本 if action == 'U':# 上移 new_state[x], new_state[x-3] = new_state[x-3], new_state[x] # 数字0和它上面那个值交换位置 elif action == 'D': new_state[x], new_state[x+3] = new_state[x+3], new_state[x] elif action == 'L': new_state[x], new_state[x-1] = new_state[x-1], new_state[x] elif action == 'R': new_state[x], new_state[x+1] = new_state[x+1], new_state[x] children.append(Puzzle(new_state,self,action,1,self.needs_hueristic)) # 每一步产生一个子节点，路径成本为1 return children def find_solution(self): solution = [] # 储存解题步骤 solution.append(self.action) path = self # 创建一个变量path并将其设置为当前Puzzle对象，即解题路径的当前节点 while path.parent != None: # 加上父节点的路径 path = path.parent solution.append(path.action) solution = solution[:-1] # 去除最后一个元素，根节点的动作 solution.reverse() # 反转列表 return solution def __lt__(self, other): # 这里假设evaluation_function属性包含了节点的优先级 return self.evaluation_function < other.evaluation_function