第25名解决方案+思路过程

本文概述了我们获得25名的解决方案思路。

首先感谢@codicon、@timothygao、@alvaroborras和@marksix在整个比赛期间的团队合作和贡献，也感谢Kaggle组织这次比赛。

魔方(Cube)

最初我们使用了公开代码库：DWalton处理棱块，RCube处理中心块。AB型魔方使用了奇偶性技巧。仅这些就让我们在281和282题上获得了23k分，并在比赛一周后获得了614k分的第三名成绩。然而，它无法解决N型魔方。

N型魔方更具挑战性。我们首先尝试像普通魔方一样解决它，通过重新着色（例如，对于4/4/4魔方，将N1到N16标记为A，N17到N32标记为B等）。解决后，我们注意到魔方的棱块已经完全解决，只剩下中心块。这让我们想到了使用魔方 commutators 的方法。

例如，以蓝色下划线的方块为例。每个面有4个这样的方块，整个魔方共有24个。绿色下划线的方块同理。仅针对中心块，魔方可以简化为解决多个24个小方块的子问题。

我们首先尝试使用双向BFS解决子问题，但这太慢不可行，因此改用束搜索(beam search)。束搜索帮助我们将283题从108k步减少到27k步，并略微改善了其他魔方。

最终方案：使用DWalton求解器解决棱块（奇数N的最中心方块），然后对commutators执行束搜索解决中心块。

所有魔方总分：约132k

地球仪(Globe)

初始构造性方案

1. 将N/M型地球仪拆分为2/M大小的子地球仪。然后使用步骤(2)和(3)解决每个2/M
2. 将底部的顶部块移动到顶部，反之亦然。例如可以通过f0.r0.f0将1个块从底部移到顶部，同时将1个块从顶部移到底部
3. 如果顶部和底部的逆序对奇偶性不匹配，则将顶部循环旋转1位。然后通过资源中的最后一个commutator消除逆序对，该commutator会交换顶部和底部的成对块
4. 最后通过r0和-r0合并解决方案，使所有fx移动变为f0移动（fx = x r0's + f0 + x -r0's）
   这将3/33题从32k步改进到13k步

为进一步改进大型地球仪，我们实现了Minkwitz算法的修改版本。原始Minkwitz算法论文可在这里找到，来自该论文的术语将使用"引号"标注。

主要差异如下：

1. 对于"Improve"函数，为获得更快的速度且保持相当效果，只选择单个"j"。我们通过加权分布随机选择j，其中0..n-1的权重分别为n..1
2. 在"Fill Orbits"函数中反向迭代"i"，以便找到的词可用于后续的i（这只在一定程度上有所帮助）
3. 对于起始词"t"，从1到max_start_word_length随机选择词长度，然后找到该长度的随机词。否则起始词会太短而无法发挥最大效用，且重复词是有用的

起初我们尝试贪心"base"选择，但这导致短期收益以增加后期"table"条目的"word"长度呈指数级增长为代价。最佳base是逐列迭代、每列从底到顶时的元素（我们尝试过之字形交替顶底迭代，但效果更差，可能因为缺乏顺序性）。

实现方面，我们使用C++以获得最大速度。此外，我们实现了原地置换操作（如逆操作）以避免内存分配（3倍加速）。

表填充执行到表似乎收敛为止，超参数表示法为：(轮次, 改进轮次("s"), max_start_word_length, 快速改进或论文改进)。我们后期切换到论文的Improve是因为它尝试更多现有短词组合，这在发现新的短词变得越来越困难时是必要的。

填充表格后，可通过因式分解快速确定解决方案，因此我们再次使用随机化。在因式分解前，我们对8/25和3/33应用1-16次随机初始移动，对其余应用1-8次。每道谜题使用约1e7次运行，大大减少了移动步数（例如3/4减少约70%，8/25和3/33减少约20%）。

该算法解决每个3/33约需1700步，每个8/25约需2500步。

所有地球仪总分：约26k

花环(Wreath)

我们发现Glazed公开的爬山算法Notebook非常有用。它改善了几乎所有花环，经过多次运行和一些代码修改后，将100/100花环减少到2500步。

所有花环总分：约3.6k