结果：95484.csv

首先，感谢组织本次竞赛。这是我第三年连续参赛，并且我最喜欢这个题目。我将主要讨论大型立方体问题，因为它耗费了我们最多的时间。

方法概述

对于所有花环和小型立方体，我们通过双向BFS或简单的束搜索获得了结果。

对于所有球体和大型立方体，我们采用了以下步骤：

1. 解决特殊部分。
   • 主要目标是解决奇偶性问题。
2. 使用保持奇偶性的移动作为候选移动进行束搜索。
   • 基础策略是将3-轮换向子作为候选移动，并进一步扩展候选移动池以改进效果。

我们使用公开的notebook（例如这里和这里）对得到的解进行了进一步优化，并在适用时采用了公开notebook中的最佳解。
我们感谢在使用这些公开notebook过程中获得的宝贵见解。

分数

术语

• 面块（facelet）：最小的状态单位。（例如，cube_33/33/33 有 6534 个面块）
• 小块（cubie）：立方体谜题中的一个独立小立方体。（例如，在 cube_33/33/33 中，有 5766 个中心小块、372 个边缘小块和 8 个角块）

大型立方体解决方案

1. 解决特殊部分。

   • 使用在 sample_submission.csv 中出现奇数次的移动来解决奇偶性问题。
     • 由于执行相同移动偶数次不会改变奇偶性，因此仅安排出现奇数次的移动总能解决奇偶性问题。
     • 得到的移动序列经过手动微调，以进一步减少移动次数（例如，移除 r1.d1，因为它不改变奇偶性）。
   • 对于奇数 N 的立方体，还需对齐中心六个小块的位置。

   示例：对于 id=283，使用 f0.f16.f2.f4.f5.f6.f11.f12.f13.f14；对于 id=257，使用 f3.r3.f1.f2。

2. 使用保持奇偶性的移动作为候选移动进行束搜索。

   • 束宽度随 N 变化，范围从 1 到 100。
   • 评估指标是移动次数的多少。与解状态在块基础上匹配的数量被视为等同于转动次数。

   使用的候选移动如下：

   • 在两步内不扰乱奇偶性的移动。
     • 对于 N=33 的示例：r1.-d31
   • 所有 3-轮换的组合。
     • 在枚举所有 3-轮换的 8 步交换子（例如 R=-d1.-r0.d0.r0.d1.-r0.-d0.r0）之后，使用广度优先搜索以 A.R.-A 的形式寻找剩余移动。
   • 改变少量面块的 4 到 8 步交换子。
     • 对于 N=33 的示例：f1.r1.-f1.-r1、-d32.-r31.d22.r31.d32.-d22
     • 根据 N 进行调整。对于 N=5，所有改变最多 24 个面块的 4、6 和 8 步移动；对于 N=33，所有改变最多 12 个面块的 4 和 6 步移动。
   • 两个角块旋转和两个中心边块旋转的交换子。
     • 对于 N=33 的角块旋转移动示例：r0.f0.-r0.-f0.r0.f0.-r0.-f0.r32.f0.r0.-f0.-r0.f0.r0.-f0.-r0.-r32
     • 对于 N=33 的边块旋转移动示例：-r16.d0.r16.-d0.-r16.d0.d0.r16.-d32.-r16.-d0.-d0.r16.d0.-r16.-d0.r16.d32
   • 由上述组合而成的交换子。
     • 组合多个交换子可以减少移动步数。
     • 示例：-r1.r2.d0.f1.-f2.-d0.r1.-r2.d0.-f1.f2.-d0 是四个 3-轮换的组合，例如 -r1.d0.f1.-d0.r1.d0.-f1.-d0 和 r2.d0.-f2.-d0.-r2.d0.f2.-d0。

球体解决方案

1. 解决特殊部分。

   • 仅使用 r{i} 移动大致对齐位置。
   • 大多数情况无需显式解决奇偶性问题即可求解；对于无法求解的情况，在重新尝试前添加几次随机移动。

2. 使用保持奇偶性的移动作为候选移动进行束搜索。

   • 束宽度随 N 变化，范围从 1 到 10。
   • 评估指标是移动次数的多少，与解状态在面块基础上匹配的数量被视为等同于转动次数。

   使用的候选移动如下：

   • 所有 3-轮换的组合。（例如 r0.f0.r1.f0.-r1.-f0.-r0.-f0）
   • 改变少量面块的 4 到 12 步交换子。（例如 r1.f3.f4.-f3.-r1.-f4）