第一名解决方案
在 454 步内解决 10x10x10 立方体（272）
在三种类型的谜题中，花环谜题并未特别关注，因为使用简单的束搜索可以找到非常短的解法，且与其他谜题相比总得分较低，优先级较低。因此，我们专注于剩余两种类型——立方体和地球仪谜题的解法。解决这两种谜题的策略基于相同的原则。
由于每次移动都会同时影响大量块，简单地直接应用移动可能导致某种有序状态，但完全解开谜题变得极其困难。因此，关键在于找到仅交换少数几块而保持其余块不变的移动序列。值得注意的是，对于这两种谜题，都存在仅旋转三块而保持其余块不变的移动序列，称为3-rot。
- 立方体谜题示例：d3.f2.d2.-f2.-d3.f2.-d2.-f2
- 地球仪谜题示例：f0.r0.f0.r1.f0.-r1.f0.-r0
在考虑所有块的簇分解时（簇指通过移动可以互换的一组块），除了立方体的角块等特殊部分外，大多数簇中任意三个元素都存在一个3-rot。
- 对于立方体谜题：角块、面中心和边中心是例外。对于其他簇，考虑到对称性，只需考虑4x4x4的对角部分（1,1）、5x5x5的十字部分（1,2）、6x6x6的非对角非十字部分（1,2）以及4x4x4的边块部分（0,1）。针对每种情况，执行了双向搜索以枚举任意三个元素的所有最短3-rot，最长为14步。
- 对于地球仪谜题：当行数为奇数时，中心行是一个例外。对于其他簇，行数为2，列数为2c时，R=f0.r0.f0.r1.f0.-r1.f0.-r0 对应一个3-rot ((0,0) (1,c) (1,c-1))。任意三个块的3-rot可以通过首先找到一个移动序列A，使用广度优先搜索将这三个块移动到一个可以应用R的状态（其他块可以自由移动），然后3-rot可通过 A.R.-A 获得。
在使用3-rot解决每个簇时，需要注意的是所有3-rot都是偶排列，因此整体排列也必须是偶排列。结合这些见解，我们可以采用以下方法：
- 解决特殊部分。
- 在不破坏已解决部分的情况下进行操作，使所有剩余簇变为偶排列。
- 使用3-rot独立解决每个簇。
为了获得更短的解法，我们采用以下关键思路：
- 由于3-rot至少需要8步且较长，在最终使用3-rot之前，使用基本移动或短序列将谜题带入某种已解决状态更有效率。
- 当将新序列B添加到现有序列A时，将A的末尾与B的开头相抵消可以缩短整体序列。例如，如果 A=A'.ri 且 B=-ri.B'，则 A.B 变为 A'.ri.-ri.B'=A'.B'，从而节省2步。
- 如果当前序列是 A=a[0]…a[T-1]，与其在末尾追加一个针对 (i j k) 的3-rot B 形成 a[0]…a[T-1].B，不如在任意时刻 t 插入一个针对某个 (i' j' k') 的3-rot B'，得到 a[0]…a[t-1].B'.a[t]…a[T-1]，结果状态相同。选择合适的时刻 t 可以使 B' 比 B 更短或产生更多抵消。因此，与其从序列前端构建，不如尝试在所有时刻插入并选择最佳时机。
基于这些思路，我们采用以下方法：
- 解决特殊部分。
- 使用基本移动使所有簇变为偶排列，同时大致对齐。
- 使用短序列将谜题带入某种已解决状态。
- 在任意时刻插入3-rot。
每个部分的详细信息和得分表可以在我们的仓库中找到：https://github.com/wata-orz/santa2023_permutation_puzzle