我正在尝试解决这个显然是初学者级别的问题。但甚至无法想出一个蛮力的方法。
这是问题陈述：
约翰尼在记住小的素数方面有些困难。所以，他的计算机科学老师让他经常玩下面的益智游戏。
拼图是一个 3x3 的棋盘，由 1 到 9 的数字组成。拼图的目的是交换瓷砖，直到达到以下最终状态：
1 2 3 4 5 6 7 8 9在每一步，如果它们的和是质数，Johnny 可以交换两个相邻的牌。如果两个瓷砖有共同的边缘，则它们被认为是相邻的。
帮助约翰尼找到达到目标状态所需的最短步数。
输入
第一行包含t，即测试用例的数量（大约 50 个）。然后是 t 个测试用例。每个测试用例都包含一个 3x3 的表格，描述了 Johnny 想要解决的难题。
连续测试用例的输入数据由空行分隔。
输出
对于每个测试用例，打印一行，其中包含解决相应难题所需的最短步骤数。如果无法达到最终状态，则打印数字 -1。
例子
输入：
2 7 3 2 4 1 5 6 8 9 9 8 5 2 4 1 3 7 6输出：
6 -1
这是 Python 的开始，用于查找从一开始就可以到达的所有板的距离。
start = '123456789'
needed_moves = {start: 0}
work_queue = [start]
while (len(work_queue)):
board = work_queue.pop(0)
for next_board in next_move(board):
if next_board not in needed_moves:
needed_moves[next_board] = needed_moves[board] + 1
work_queue.append(next_board)
这是广度优先搜索的标准模式。只需next_move为测试用例提供一个功能和一些胶水，你就很好了。
对于深度优先搜索，只需将队列切换为堆栈。这实际上意味着work_stack.pop()弹出最后一个元素而不是work_queue.pop(0)获取第一个元素。