利用搜索树加速rubik立方体算法的编码

Question

我是一名机械工程专业的学生，目前正在建造一个魔方运算器。我想编写一个VSCode程序(用于与arduino mega接口)，该程序使用基本的CFOP方法(解决跨->角、->第二层边缘、->、OLL -> PLL)。

最简单的方法就是对立方体的每个部分进行一系列的硬编码。对于前4个边和角，这将是一个绝对荒谬的数量的代码。以白色-橙色-蓝色角为例，在3个不同的方向上有8个可能的位置，导致了24个完全独特的移动序列，我不得不考虑。总之，我预测它最终将是一个3000+行程序。

它是否有可能，而不是简单地知道如何解决每一件有序，拿一块和混乱，直到它被放置在它需要去的地方，并跟踪最短的路径回来，并设置为移动顺序？对于边缘和拐角，大多数可以在2-4个移动范围内求解，并且给定标准的运动符号，每个块一次只有4个自由度，所以我不认为它应该是计算量太大的？

问题是，我对树、理论或实现没有任何经验，如果这是可能的话，我也没有任何想法。然而，如果是这样的话，这会使编码变得不那么乏味了。

Answer 1

“拿一块乱七八糟的”将不适用于魔方问题--当你任意移动“乱七八糟”的时候，你就会破坏你预先正确放置的碎片的顺序。构建一个完整的搜索树也不能工作，由于指数增长，该树需要43 252 003 274 489 856 000节点。

因此，您通常需要应用特定的移动序列，这些序列不会破坏所获得的部分解决方案。但是，没有必要为每一个可能的位置和方向编写单独的代码。就像人类所做的那样，遵循一种著名的解决算法。

• 用某种符号对某些移动序列进行一般描述，以实现某些中间目标。
• 实现一个能够解释这些移动序列的程序，并将其应用于程序的“魔方模拟器”
• 实现程序的一部分，允许您探索立方体的对称性，这样您就可以将相同的移动序列应用于不同的对称情况。
• 在求解上两层时，您可以利用下面层可以任意旋转的事实，然后再应用预定义的移动序列。
• 最后，让您的程序选择一个接一个，选择合适的移动顺序，并正确定位，并应用该移动序列。

在尝试解决更困难的问题(如魔方)之前，先从一个比较简单的类似问题开始，例如“15益智”，并收集一些经验，这也是一个好主意。