背景

• 业务背景： https://www.kaggle.com/competitions/santa-2023/overview
• 数据背景： https://www.kaggle.com/competitions/santa-2023/data

方法概述

我们使用双向广度优先搜索（BBFS）来对小型谜题进行最优求解。对于大型谜题，主要采用交换子和共轭的方法求解，但加入了若干特殊功能（详见下文），这些功能带来了显著提升。

提交详情

小型谜题的最优求解

• 我们使用简单的广度优先搜索（BFS）对cube_2/2/2、wreath_6/6和wreath_7/7谜题进行了最优求解。
• 为了扩展到wreath_12/12，我们实现了双向BFS（BBFS）。这不仅使我们能够求解之前因内存不足而无法求解的wreath_12/12的最优解，而且比传统BFS快得多，成为我们求解其他谜题类型的标准工具。
• 为了扩展到wreath_21/21，我们对状态表示进行了压缩优化，并在配备大量内存的机器上运行。

中型地球仪

即使是最小的地球仪谜题也无法用BBFS求解。我们的方法是先用BBFS求解前N个格子，然后逐步扩展。具体做法是：将其他格子掩码处理——将其设置为与其他格子相同的符号（.），这样许多独特的状态会坍缩为单个伪状态，从而大幅缩小谜题规模。解决前N个格子后，我们扩展到N+M个格子。我们称之为迭代BBFS（IBBFS）。它虽然无法给出最优解，但能得到相当不错的结果。我们进一步优化使其自适应——如果BBFS用很少步数就找到解，我们会回退并一次性求解更大的块；如果求解下M个格子耗时过长，则中止并减少M。我们称之为自适应IBBFS（AIBBFS）。AIBBFS是我们求解1/8、2/6、3/4、6/4和6/8型地球仪的最佳方法。

大型地球仪

大型地球仪的求解分为两个阶段。第一阶段尝试"随机"移动来尽可能多地求解格子。第二阶段使用交换子和共轭（魔方术语）来求解剩余部分而不破坏已解决的部分。

第一阶段

第一阶段使用固定深度的BFS，寻找能求解最多格子的移动集合。然后我们只执行该集合中的第一步，并重复此过程。在进行下一次BFS迭代前只走一步（而非执行完整移动集合）提高了该阶段的效率，并显著增加了可求解的格子总数。鉴于该阶段效率约为1步/格，而第二阶段约为6步/格，在该阶段多求解格子是非常有利的。

第二阶段

我们使用BBFS寻找大量短小的两对交换子——即用少量移动交换格子对{A,B}和{C,D}，同时保持其他格子不变。这些交换子很短（8或10步），但能交换的格子对有限。我们通过共轭扩展它们——执行任意移动序列作为前序操作，将目标格子带到交换子覆盖的位置A、B、C、D，执行交换子，然后执行前序操作的逆操作。

我们构建了大型数据库（数千万条目），记录可以如此交换的格子对。每一步中，我们搜索数据库中能带来最佳性价比改进的条目（即额外求解格子数/求解步数），并应用它。

（值得一提的是，还有一个几乎同样有效但运行更快的方案：某些交换子交换南北对，另一些交换北北对和南南对。在竞赛的大部分时间里，我们先将所有块放入正确的半球，再进行半球内交换。）

在其他题解中，似乎提到了地球仪谜题也存在3格交换子。我曾考虑添加这些，但时间不足/专注于帮助队友求解最大立方体。

立方体

立方体主要由队友完成，因此我了解较少。但大致思路与大型地球仪类似……

1. 寻找能求解尽可能多格子的前缀
2. 使用轨道求解器，利用交换子独立求解每个24格轨道
3. 对于含通配符的谜题，求解背包问题
4. 使用旅行商问题求解器组装各轨道的解

最后两个阶段与之前讨论的方法有所不同。

第3阶段 - 背包问题求解

由于第2阶段独立求解每个轨道，且某些解包含通配符，因此可以跳过某些轨道。但应该跳过哪些？这就是经典的背包问题。跳过轨道的价值是求解该轨道所需的步数，成本（或"重量"）是不求解该轨道时将处于错误状态的格子数。

这主要应用于谜题#277，它有176个通配符（占状态的8%）。由于其对其他谜题适用性有限且时间紧张，我们采用简单的贪心策略：基于价值/重量比贪心地跳过轨道（要求"重量"不超过可用通配符数量）。虽然存在更好的背包问题解法，但这是一个合理的起点。

第4阶段 - 旅行商问题

第2阶段独立求解轨道，因此一个轨道解的末尾与下一个轨道解的开头可能存在可抵消的移动。如果重新排序轨道，可以最大化可抵消的移动总数。我们注意到这可以建模为（非对称）旅行商问题。首先计算每对有序轨道[A, B]在求解B紧接在A后可抵消的移动数（'C'）。A到B的有向距离为-C。使用旅行商问题求解器（我曾用于Santa 2022）来最小化距离，从而最大化抵消量。

我们也应该将此方法用于大型地球仪，但同样时间不足。

源代码

待补充

附录A：软性内容

• 致谢 感谢Kaggle，特别感谢Ryan举办本次竞赛，并以优雅高效的方式处理各种小问题。
• 为什么是永远Day Zero？今年我邀请了几位同事加入我的团队。我们工作的公司推崇"永远第一天"的文化（如果不熟悉，可在此阅读）。我曾参加内部网络安全攻防赛，其中"day zero"显然指未修补的漏洞。因此，我开玩笑地以"Always Day Zero"为队名参加那些比赛，并一直沿用至今。
• 我很高兴我的进度更新对许多人有所帮助，能帮助大家将注意力集中在最薄弱的谜题上。感谢聊天中的鼓励与有趣讨论，这确实丰富了竞赛体验。

附录B：各谜题类型最终得分

† 我们确认这是最优解。

附录C：得分进展

以下是我们在竞赛中的得分进展图。

附录D：最终提交

请查看附件中的最终提交文件。