Double-Choco游戏可解谜题生成：最优数据结构与算法咨询

问题背景 #

你正在实现Nikoli的Double-Choco拼图游戏，需要自动生成可解谜题，核心要求是将棋盘分割为若干区块，每个区块包含一对**形状完全相同（可旋转/镜像）**的白色、灰色区域，区域大小为偶数（一对总大小为2k）。现有随机生成思路存在效率和可靠性问题，以下是针对性的优化方案。

现有思路的核心问题 #

1. 随机选区域易陷入死循环：后期棋盘剩余空间碎片化时，很难找到匹配的形状，反复回溯会大幅降低生成效率。
2. 形状匹配效率低：每次临时判断旋转/镜像后的形状是否能放入，没有复用形状的等价类信息。
3. 违规检查滞后：放置后才检查是否有被包围的奇数区块，回溯成本高。

推荐数据结构 #

1. 棋盘状态与连通性管理：并查集（Union-Find） #

• 用二维数组grid记录每个单元格状态：0（未占用）、1（白色已占用）、2（灰色已占用）。
• 搭配并查集结构，跟踪每个空白单元格所属的连通区域，实时获取每个连通区域的大小。这样可以提前预判放置区块后剩余连通区域的大小是否为偶数（必须满足，因为每个区块占用2k空间，剩余空间总大小和每个连通块大小都得是偶数，否则无法配对）。
• JS实现并查集时，用数组存储父节点，加上路径压缩和按秩合并，保证操作接近O(1)复杂度。

2. 形状等价类库：预生成+哈希映射 #

• 预先生成所有符合尺寸要求的连通形状（尺寸从2到棋盘半尺寸的偶数），每个形状用相对坐标表示（比如以左上角单元格为原点，记录其他单元格的相对偏移）。
• 对每个形状生成所有旋转（0°、90°、180°、270°）和镜像（水平、垂直）的变体，然后将这些变体归为同一个等价类，用标准化的字符串编码作为哈希键（比如把相对坐标按固定顺序排序后转成JSON字符串）。
• 用Map<string, Shape[]>存储等价类，键是标准化编码，值是该类下的所有形状变体。这样选定白色区域形状后，直接通过哈希键快速获取所有可匹配的灰色区域形状。

3. 区块信息存储：Map/对象集合 #

• 用Map<string, Block>存储已生成的区块，其中Block包含：
  • whiteCells: 白色区域的坐标集合（Set，比如"x,y"格式）
  • grayCells: 灰色区域的坐标集合
  • size: 区域大小k
  • hintNumber: 可选的标注数字（如果需要生成带提示的谜题）

优化后的生成算法 #

1. 从大到小填充区块 #

• 优先生成大尺寸的区块（比如从maxSize开始递减，maxSize是棋盘总大小的1/2向下取偶），再处理小尺寸。大区块对空间的占用更规整，剩余空间更易匹配，减少后期碎片化导致的回溯。

2. 形状匹配与放置流程 #

1. 从当前最大可用尺寸k开始，在空白连通区域中随机选取一个k大小的连通形状作为白色区域。
2. 通过形状等价类库，获取该形状的所有旋转/镜像变体。
3. 在剩余空白区域中，检测是否能放下任意一个变体作为灰色区域：
   • 遍历空白连通区域的每个单元格作为变体的原点，检查所有相对坐标对应的单元格是否都是未占用状态。
4. 若找到可放置的灰色区域，预判放置后的连通区域状态：
   • 用并查集模拟放置操作，计算剩余每个连通区域的大小是否都是偶数。
   • 若所有剩余连通区域大小均为偶数，则正式标记白色、灰色区域为已占用，更新并查集和区块集合。
   • 若存在奇数大小的连通区域，放弃当前形状，重新选取白色区域。
5. 若当前尺寸k没有可匹配的形状，递减k继续尝试，直到所有区块生成完毕。

3. 可解性增强 #

• 若生成带提示的谜题，确保同一尺寸的区块数量不超过合理范围，且提示数字与区域大小对应。
• 避免生成完全对称的谜题（除非刻意设计），增加推理难度的同时保证可解性。

JS实现小技巧 #

• 用Set<string>存储已占用坐标，比如new Set(['0,0', '0,1'])，快速判断某个坐标是否被占用。
• 形状编码时，将相对坐标按x从小到大、y从小到大排序后转成字符串，确保旋转/镜像后的相同形状能得到相同的编码。
• 并查集的find方法用路径压缩，union方法用按秩合并，提升连通性判断的效率。

内容的提问来源于stack exchange，提问作者Muhammad Z