Double-Choco 谜题生成：高效数据结构与算法实践

本文深入探讨了如何为Double-Choco益智游戏自动生成可解谜题。核心内容包括设计一个高效的二维网格单元数据结构，并提出一种基于递归遍历的算法来识别和提取棋盘上的独立区域（即谜题中的“块”）。文章将详细阐述如何利用这些基础结构，结合形状匹配、旋转、镜像以及违规检查等逻辑，构建一个完整的谜题生成流程，旨在提供一个清晰、专业的教程，帮助开发者实现自动化谜题生成系统。

1. Double-Choco 谜题概述与生成挑战

Double-Choco是一款由Nikoli杂志推出的棋盘益智游戏。其核心玩法是在一个由白色和灰色单元格组成的二维网格上，通过绘制实线将网格划分为若干个“块”。每个块必须包含一对形状（大小和形态）相同、颜色相反（白色和灰色）的区域，其中一个区域可以是另一个区域的旋转或镜像。某些区域可能包含一个数字，表示该颜色在该块中的单元格数量。

自动生成此类谜题面临的主要挑战在于：

• 形状匹配与变换：需要高效地识别和匹配具有相同形状但可能经过旋转或镜像变换的区域。
• 区域连通性：确保每个块内部的同色区域是连通的。
• 完整性与可解性：生成的谜题必须填满整个棋盘，且满足所有规则，确保其可解。
• 效率：在大型棋盘上，暴力穷举会非常耗时，需要高效的数据结构和算法来支撑。

2. 核心数据结构设计：单元格（Cell）

为了有效地表示棋盘状态和进行区域操作，我们定义一个cell对象作为棋盘的基本单元。每个cell对象应包含其在网格中的位置信息、颜色、边界信息以及是否已被处理等状态。

let cell = {
x: Number,        // 单元格的X坐标
y: Number,        // 单元格的Y坐标
color: "white" | "gray", // 单元格的颜色
number: null | Number,   // 如果有数字提示，则为数字，否则为null
top: true | false,    // 上边界是否有实线（true表示有，false表示没有，即与上方单元格连通）
bottom: true | false, // 下边界是否有实线
left: true | false,   // 左边界是否有实线
right: true | false,  // 右边界是否有实线
taken: false,         // 标记该单元格是否已被某个块占用（已处理）
block: []             // 用于存储该单元格所属的块中所有单元格的引用（或坐标）
};

数据结构解释：

• x, y：用于快速定位单元格。
• color, number：存储谜题规则相关的属性。
• top, bottom, left, right：这些布尔值至关重要。false表示该方向上没有边界线，意味着当前单元格与相邻单元格属于同一连通区域。这对于后续的块提取算法是关键。
• taken：在遍历和提取块时，用于防止重复处理单元格，提高效率。
• block：在块提取过程中，可以用来临时存储属于同一块的单元格集合。

棋盘本身可以表示为一个二维数组，其中每个元素都是一个cell对象：let cells = Array(Y).fill(0).map(() => Array(X).fill(0));

3. 核心算法：块提取（Block Extraction）

在谜题生成过程中，我们需要频繁地识别出由连通单元格组成的区域，即“块”。这对于验证新放置的区域是否形成有效块、检查剩余空间是否可填充等至关重要。这里介绍一个基于深度优先搜索（DFS）或广度优先搜索（BFS）思想的递归算法。

3.1 take 函数详解

take函数是块提取的核心。它以一个未被处理的单元格为起点，递归地探索所有与之连通的单元格，并将它们标记为已处理，同时收集到同一个块中。

/**
* 递归地遍历并标记连通的单元格，将其归属于同一个块。
* @param {object} currentCell - 当前正在处理的单元格。
* @param {object} blockOriginCell - 启动本次块提取的起始单元格，用于标识这个块的归属。
* @param {Array<Array<object>>} cells - 整个棋盘的二维单元格数组。
* @param {number} boardWidth - 棋盘宽度。
* @param {number} boardHeight - 棋盘高度。
*/
function take(currentCell, blockOriginCell, cells, boardWidth, boardHeight) {
// 边界检查：确保当前单元格在棋盘范围内
if (!currentCell || currentCell.taken) {
return;
}
currentCell.taken = true; // 标记当前单元格为已处理
blockOriginCell.block.push(currentCell); // 将当前单元格添加到起始单元格的块列表中
const { x, y } = currentCell;
// 向上探索
if (!currentCell.top && y > 0) {
take(cells[y - 1][x], blockOriginCell, cells, boardWidth, boardHeight);
}
// 向下探索
if (!currentCell.bottom && y < boardHeight - 1) {
take(cells[y + 1][x], blockOriginCell, cells, boardWidth, boardHeight);
}
// 向左探索
if (!currentCell.left && x > 0) {
take(cells[y][x - 1], blockOriginCell, cells, boardWidth, boardHeight);
}
// 向右探索
if (!currentCell.right && x < boardWidth - 1) {
take(cells[y][x + 1], blockOriginCell, cells, boardWidth, boardHeight);
}
}

take函数工作原理：

1. 起点：当take函数被调用时，它接收一个currentCell和blockOriginCell。blockOriginCell是本次块提取的“代表”单元格，所有属于这个块的单元格都将被添加到它的block数组中。
2. 标记：首先将currentCell.taken设为true，表示该单元格已被访问并归类。
3. 收集：将currentCell添加到blockOriginCell.block数组中。
4. 递归探索：根据currentCell的top, bottom, left, right属性（表示该方向上是否有边界线），递归地调用take函数探索其相邻的单元格。
   • 如果currentCell.top为false，表示上方没有边界线，则向上探索cells[y-1][x]。
   • 同理处理下方、左方和右方。
5. 边界条件：递归的终止条件是遇到已经taken的单元格，或者到达棋盘边界。

3.2 完整棋盘块提取流程

要从整个棋盘中提取所有独立的块，我们需要遍历所有单元格，并对未被处理的单元格调用take函数。

/**
* 从整个棋盘中提取所有独立的块。
* @param {Array<Array<object>>} cells - 整个棋盘的二维单元格数组。
* @param {number} boardWidth - 棋盘宽度。
* @param {number} boardHeight - 棋盘高度。
* @returns {Array<Array<object>>} 包含所有提取出的块的数组，每个块是一个单元格数组。
*/
function extractAllBlocks(cells, boardWidth, boardHeight) {
// 重置所有单元格的 taken 状态和 block 数组，以确保每次提取都是新的。
// 在实际生成过程中，可能只需要在特定阶段（如验证）进行提取，无需每次都重置。
cells.flat().forEach(cell => {
cell.taken = false;
cell.block = []; // 清空之前的块信息
});
const allBlocks = [];
for (let y = 0; y < boardHeight; y++) {
for (let x = 0; x < boardWidth; x++) {
const currentCell = cells[y][x];
if (!currentCell.taken) {
// 如果当前单元格未被处理，则它是一个新块的起点
take(currentCell, currentCell, cells, boardWidth, boardHeight);
// 此时 currentCell.block 已经包含了这个新块的所有单元格
if (currentCell.block.length > 0) {
allBlocks.push(currentCell.block);
}
}
}
}
return allBlocks;
}

流程解释：

1. 初始化：在开始提取前，确保所有单元格的taken状态为false，并且它们的block数组被清空（或者直接使用一个外部数组来收集）。
2. 遍历：遍历棋盘上的每一个单元格。
3. 发现新块：如果遇到一个taken状态为false的单元格，说明它是一个新块的起点。以它为blockOriginCell，调用take函数进行递归探索。
4. 收集：take函数执行完毕后，blockOriginCell.block数组将包含该新块的所有单元格。将其添加到allBlocks列表中。
5. 重复：继续遍历，直到所有单元格都被访问。

通过这种方式，extractAllBlocks函数能够识别并返回棋盘上所有独立的连通区域（块）。

4. 谜题生成流程整合

上述的cell数据结构和extractAllBlocks函数是构建Double-Choco谜题生成器的基础工具。以下是将其整合到完整生成流程中的思路：

1. 初始化棋盘：

   • 创建一个指定大小的X x Y二维cells数组。
   • 所有单元格初始状态为color: null（或统一颜色），number: null，taken: false。
   • 所有边界（top, bottom, left, right）初始为false，表示整个棋盘是一个大的连通区域，后续在确定块边界时再设置为true。

2. 迭代填充棋盘：

   • 选择未占用区域：随机选择一个尚未被taken的单元格作为起点。
   • 生成白色区域：从该起点开始，随机生成一个连通的白色区域（例如，通过随机游走或BFS/DFS扩展），其大小在预设范围内（例如，2到棋盘总面积的一半，并向下取整到偶数）。
     • 在生成过程中，需要确保新选择的单元格是未被占用的。
     • 一旦生成一个潜在的白色区域，将其单元格的color设置为”white”。
   • 寻找匹配的灰色区域：
     • 在剩余的未占用空间中，尝试寻找一个与已生成白色区域形状相同、大小相等，且颜色相反（”gray”）的区域。
     • 这涉及到复杂的三维匹配（平移、旋转、镜像）。可以先将白色区域的形状抽象为相对坐标点集，然后对该点集进行旋转和镜像变换，再尝试在棋盘上找到一个空闲区域能完全容纳这个变换后的点集。
     • 如果找到，将其单元格的color设置为”gray”。
   • 确定块边界：
     • 一旦成功匹配一对白色和灰色区域，它们共同构成一个完整的块。
     • 遍历这个块中的所有单元格。对于每个单元格，检查其相邻单元格是否属于同一个块。如果相邻单元格不属于同一个块，则在该方向上设置边界（例如，currentCell.top = true）。
     • 将这个块中的所有单元格的taken属性设置为true。
   • 违规检查：
     • 在放置一个新块后，使用extractAllBlocks函数检查棋盘上是否存在任何“孤立”的、无法形成有效Double-Choco块的区域。例如，检查是否有大小为奇数的未被占用的连通区域，因为Double-Choco的每个块总面积必须是偶数（一对同形异色区域）。
     • 如果存在违规，回溯到上一步（撤销当前块的放置），并尝试重新生成白色区域或寻找匹配的灰色区域。
   • 重复：重复上述步骤，直到整个棋盘都被填充完毕。

3. 添加数字提示：

   • 在棋盘填充完毕后，根据规则在某些白色或灰色区域内放置数字提示。这通常涉及到统计特定区域的单元格数量，并选择合适的单元格来放置数字。

5. 注意事项与优化建议

• 边界检查：在take函数中，务必进行y > 0, y 0, x
• 形状匹配的复杂性：实现高效的形状匹配（包括旋转和镜像）是谜题生成中最具挑战性的部分。可以考虑将形状抽象为规范化的点集或位掩码，以便进行比较。预计算常见的形状及其所有旋转/镜像变体可以提高效率。
• 回溯机制：由于谜题生成是一个约束满足问题，当某个选择导致死胡同（无法填满棋盘或产生违规）时，需要强大的回溯（backtracking）机制来撤销之前的选择并尝试新的路径。
• 随机性与难度控制：通过调整随机选择区域的大小、形状复杂度和放置策略，可以控制生成谜题的难度。
• 性能优化：对于大型棋盘，extractAllBlocks可能会被频繁调用。如果性能成为瓶颈，可以考虑优化taken状态的重置策略，或使用更高级的连通分量算法（如并查集Union-Find）来动态维护区域信息。
• 颜色与数字属性的使用：在块提取之后，可以遍历block中的单元格，根据其color和number属性进行验证。例如，确认白色和灰色区域的数量是否符合数字提示。

总结

本文提供了一个构建Double-Choco谜题生成器的基础框架，重点介绍了cell数据结构和基于递归的块提取算法。通过将这些基础工具与高级的形状匹配、回溯和违规检查逻辑相结合，开发者可以构建出能够自动生成可解Double-Choco谜题的系统。理解并有效利用这些数据结构和算法，是实现复杂棋盘游戏自动生成功能的关键。