# -*- coding: UTF-8 -*- import numpy as np import queue import prettytable as pt def find_zero(num): tmp_x, tmp_y = np.where(num == 0) return tmp_x[0], tmp_y[0] def swap(num_data, direction): x, y = find_zero(num_data) num = np.copy(num
时间: 2023-06-17 12:02:22 浏览: 51
_data) if direction == 'up': num[x][y], num[x-1][y] = num[x-1][y], num[x][y] elif direction == 'down': num[x][y], num[x+1][y] = num[x+1][y], num[x][y] elif direction == 'left': num[x][y], num[x][y-1] = num[x][y-1], num[x][y] elif direction == 'right': num[x][y], num[x][y+1] = num[x][y+1], num[x][y] return num def is_valid(num): if np.array_equal(num, [[1,2,3],[4,5,6],[7,8,0]]): return True else: return False def bfs(start): q = queue.Queue() q.put(start) visited = set() visited.add(start.tobytes()) while not q.empty(): curr = q.get() if is_valid(curr): return curr for direction in ['up', 'down', 'left', 'right']: new_state = swap(curr, direction) if new_state.tobytes() not in visited: visited.add(new_state.tobytes()) q.put(new_state) def main(): start_state = np.array([[2,8,3],[1,6,4],[7,0,5]]) end_state = np.array([[1,2,3],[4,5,6],[7,8,0]]) print('Start state:') tb_start = pt.PrettyTable() tb_start.add_rows(start_state) print(tb_start) print('End state:') tb_end = pt.PrettyTable() tb_end.add_rows(end_state) print(tb_end) result = bfs(start_state) print('Solution:') tb_result = pt.PrettyTable() tb_result.add_rows(result) print(tb_result) if __name__ == '__main__': main()
这是一个使用 BFS 算法解决八数码问题的 Python 代码。算法的主要思路是从起始状态开始,每次尝试将数字 0 上下左右移动,生成新的状态。然后判断这个状态是否是目标状态,如果是,就返回。如果不是,就将这个状态加入队列,并标记为已访问过。接着继续从队列中取出下一个状态,重复上述过程,直到找到目标状态或者队列为空为止。
代码中使用了 NumPy 库来处理矩阵,使用了 Queue 库来实现队列。使用了 PrettyTable 库来美化输出结果。