algorithm - 如何最佳地确定魔方上的边是否正确定向？

Question

如果仅通过旋转右面、左面、上面和下面就可以解决一条边，则认为它的方向正确。如果求解边缘需要转动正面或背面，则被认为是定向错误或“不好”。不允许旋转立方体，使正面和背面变得不同。

这是一个例子:

^{图片来自here}

This该网站详细介绍了人类确定边缘方向的演绎方法。我想知道是否有更优化的方法可以通过程序来完成此操作(此外，打乱立方体所采取的步骤是已知的)。

Answer 1

网站上似乎已经有您的问题的答案。

Look at the U/D faces. If you see:

   - L/R colour (orange/red) it's bad.
   - F/B colour means you need to look round the side of the edge. If the side is U/D (white/yellow) it is bad.


Then look at the F/B faces of the E-slice (middle layer). The same rules apply. If you see:

   - L/R colour (orange/red) it's bad.
   - F/B colour (green/blue) means you need to look round the side of the edge. If the side is U/D (white/yellow) it is bad.

所以这只是一个循环遍历 U/D/F/B 面上的颜色的问题(或者您可以在单个边缘的基础上进行)，如果其中任何一个违反了规则，您就知道该边缘是坏的。这种方式只查看每个边缘一次，所以我认为它相当有效。但这忽略了对加扰算法的了解。

简单地使用打乱算法来确定边缘方向会困难得多，因为您必须观察转弯中的模式，并且如果打乱足够长，则最终可能会花费比上面解释的更多的时间。但为了完整起见，我将给出一个简短的示例来说明如何完成此操作。

• 从所有边的定向状态及其所在位置开始(只有 12 个位置，因此要相应编号)。或者，如果您只对其中一首感兴趣。
• 然后迭代地遍历列表
  • 每当 F/B 转动奇数次时，无论转动哪个面，其边缘方向都会翻转。

当您将边缘移回完整性时，可以向后运行，跟踪边缘的状态，如果最终您的边缘声称“方向错误”，您会知道它实际上与您开始时的状态相反(因为解决的立方体的所有边都定向)。

然而，这在 O(n) 中运行，其中 n 是打乱的长度，第一个在 O(1) 中运行，因此如果您期望非常短的打乱，则第二种方法可能会更好。但第一次就能保证您快速获得结果。

我会提供伪代码，但我不认为这些算法非常复杂，而且我不确定如何存储数据。