prolog - 解决魔方问题的 BFS 算法

Question

我想知道如何为 rubik 立方体运行 BFS 算法，这是我函数的输入参数。到目前为止，我已经创建了函数

rotateUp(cubeIn, cubeOut), rotateDown(cubeIn, cubeOut2), rotateFront(cubeIn, cubeOut), rotateBack(cubeIn, cubeOut), rotateLeft(cubeIn, cubeOut), rotateRight(cubeIn, cubeOut)

来旋转魔方的每一面。

现在我要运行一些递归函数，我可以以各种可能的方式旋转我的立方体，然后检查魔方是否已解决。

我已经尝试过这个解决方案，但它只会越来越深入：

bfs(cubeIn) :-
        rotateUp(cubeIn, cubeOut1), bfs(cubeOut1),
        rotateDown(cubeIn, cubeOut2), bfs(cubeOut2),
        rotateFront(cubeIn, cubeOut3), bfs(cubeOut3),
        rotateBack(cubeIn, cubeOut4), bfs(cubeOut4),
        rotateLeft(cubeIn, cubeOut5), bfs(cubeOut5),
        rotateRight(cubeIn, cubeOut6), bfs(cubeOut6).

所以我想为我的魔方问题实现 BFS 算法，我做了这个：

bfs(cubeIn) :-
        rotateUp(cubeIn, cubeOut1),
        rotateDown(cubeIn, cubeOut2),
        rotateFront(cubeIn, cubeOut3),
        rotateBack(cubeIn, cubeOut4),
        rotateLeft(cubeIn, cubeOut5),
        rotateRight(cubeIn, cubeOut6),
        bfs(cubeOut1),bfs(cubeOut2),bfs(cubeOut3),
        bfs(cubeOut4),bfs(cubeOut5),bfs(cubeOut6).

但最终还是没有像BFS那样工作。 难道你不知道我做错了什么吗？

Answer 1

对于 BFS，您需要展开一级的所有节点，然后展开下一级的节点。但伪代码扩展一个节点，然后通过迭代调用 bfs() 进入下一级。它不是 BFS，而更像是 DFS。

BFS 本身不足以解决魔方问题。你有 6 个面，每个面可以旋转 90 度、180 度或 270 度。所以你将有 3*6=18 个可能的回合。拥有如此大的分支因子，很快就会耗尽 BFS 的内存。一种可能的解决方案是将其分解为几个阶段，然后每个阶段都可以使用 IDDFS 来解决。对于任何有兴趣解魔方的人来说，Thistlethwaite 的算法是一个很好的起点。