搜索算法练习——拼图问题

本文主要是介绍搜索算法练习——拼图问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

拼图问题是一个经典的搜索问题，其中目标是将一个拼图板恢复到初始状态，或者找到一个初始状态到目标状态的最短路径。

我们可以使用广度优先搜索（BFS）来解决这个问题，将每个状态作为节点，并尝试所有可能的移动。

from collections import dequedef swap(board, i, j, ni, nj):"""交换拼图板上两个方块的位置。Parameters:board (list): 当前拼图板状态。i (int): 第一个方块的行号。j (int): 第一个方块的列号。ni (int): 第二个方块的行号。nj (int): 第二个方块的列号。"""board[i][j], board[ni][nj] = board[ni][nj], board[i][j]def get_neighbors(board):"""获取当前拼图板状态的所有可能邻居状态。Parameters:board (list): 当前拼图板状态。Returns:list: 所有可能的邻居状态列表。"""neighbors = []empty_row, empty_col = find_empty_square(board)moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 可以向上、下、左、右移动的方向for dr, dc in moves:nr, nc = empty_row + dr, empty_col + dcif 0 <= nr < len(board) and 0 <= nc < len(board[0]):new_board = [row[:] for row in board]  # 创建当前拼图板的副本swap(new_board, empty_row, empty_col, nr, nc)  # 移动空方块neighbors.append(new_board)return neighborsdef find_empty_square(board):"""在拼图板上找到空方块的位置。Parameters:board (list): 拼图板状态。Returns:tuple: 空方块的行号和列号。"""for i in range(len(board)):for j in range(len(board[0])):if board[i][j] == 0:return i, jdef is_goal_state(board, target):"""检查当前拼图板状态是否为目标状态。Parameters:board (list): 当前拼图板状态。target (list): 目标拼图板状态。Returns:bool: 如果当前状态与目标状态相同，则返回True，否则返回False。"""return board == targetdef bfs_puzzle(initial, target):"""使用广度优先搜索（BFS）解决拼图问题。Parameters:initial (list): 初始拼图板状态。target (list): 目标拼图板状态。Returns:list: 到达目标状态的最短路径，如果不存在路径则返回空列表。"""queue = deque([(initial, [])])  # 使用队列存储当前拼图板状态和到达该状态的路径visited = set([tuple(map(tuple, initial))])  # 使用集合记录已经访问过的拼图板状态while queue:board, path = queue.popleft()if is_goal_state(board, target):return pathfor neighbor in get_neighbors(board):if tuple(map(tuple, neighbor)) not in visited:visited.add(tuple(map(tuple, neighbor)))queue.append((neighbor, path + [neighbor]))return []# 示例初始拼图板状态和目标拼图板状态
initial_board = [[1, 2, 3],[0, 4, 5],[6, 7, 8]
]
target_board = [[1, 2, 3],[4, 5, 6],[7, 8, 0]
]# 使用广度优先搜索解决拼图问题
shortest_path = bfs_puzzle(initial_board, target_board)
if shortest_path:print("到达目标状态的最短路径：")for step in shortest_path:for row in step:print(row)print()
else:print("未找到到达目标状态的路径。")