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

本文深入探讨了如何自动生成Double-Choco谜题，重点介绍了基于2D单元格矩阵的数据结构设计，以及利用递归式连通组件识别（如洪水填充算法）来提取和验证谜题块的算法。我们将详细阐述从棋盘初始化、形状生成与匹配到边界定义和最终验证的完整生成流程，并提供关键代码示例和实现注意事项，旨在为开发者提供一套可行的谜题生成方案。

一、核心数据结构：单元格表示

在double-choco谜题中，棋盘由一个个单元格组成，这些单元格可以是白色或灰色。为了有效地表示棋盘状态和块的边界，我们采用一个2d数组来存储自定义的cell对象。每个cell对象不仅包含其在棋盘上的坐标，还承载了颜色、数字（如果适用）、边界信息以及是否已被分配到某个块的状态。

一个cell对象的核心属性定义如下：

let cell = {
x: Number,        // 单元格的X坐标
y: Number,        // 单元格的Y坐标
color: "white" | "gray", // 单元格的颜色
number: null | Number,   // 如果有数字提示，表示该颜色区域的单元格数量
top: true | false,    // 顶部是否有边界线 (true: 有边界, false: 无边界)
bottom: true | false, // 底部是否有边界线
left: true | false,   // 左侧是否有边界线
right: true | false,  // 右侧是否有边界线
taken: false,     // 是否已被分配到某个完成的谜题块中
blockId: null     // 所属谜题块的唯一ID，或存储整个块的引用
};

关键属性解析：

• x, y: 单元格的二维坐标，方便定位。
• color, number: 用于表示谜题的特定规则，即白/灰区域及其大小提示。
• top, bottom, left, right: 这四个布尔值是定义谜题块边界的关键。当值为true时，表示该方向存在一条实线，将当前单元格与相邻单元格分隔开；当值为false时，表示该方向没有实线，当前单元格与相邻单元格相连，属于同一个连通区域。
• taken: 在生成过程中，用于标记已被成功分配到某个合法谜题块的单元格，避免重复处理。
• blockId: 用于在提取块后，将所有属于同一块的单元格关联起来。

二、块提取算法：基于边界的连通组件识别

在谜题生成过程中，我们需要能够根据已定义的边界线（即cell对象的top/bottom/left/right属性）来识别和提取独立的谜题块。这可以通过一个递归的洪水填充（Flood-Fill）算法来实现。

该算法从一个未被标记的单元格开始，递归地访问所有与其相连（即之间没有边界线）的相邻单元格，直到遇到边界线或已访问过的单元格。所有被访问到的单元格共同构成一个完整的谜题块。

/**
* 递归地提取一个连通的谜题块。
* @param {Array<Array<cell>>} cells - 整个棋盘的2D单元格数组。
* @param {cell} currentCell - 当前正在处理的单元格。
* @param {Array<cell>} currentBlock - 用于存储当前块中所有单元格的数组。
* @param {number} blockId - 当前块的唯一标识符。
*/
function extractBlock(cells, currentCell, currentBlock, blockId) {
// 边界检查：确保单元格在棋盘范围内
if (!currentCell || currentCell.taken) {
return;
}
currentCell.taken = true;      // 标记为已访问/已分配
currentCell.blockId = blockId; // 分配块ID
currentBlock.push(currentCell); // 将单元格添加到当前块中
const { x, y } = currentCell;
const rows = cells.length;
const cols = cells[0].length;
// 向上移动：如果顶部没有边界线且上方单元格存在
if (!currentCell.top && y > 0) {
extractBlock(cells, cells[y - 1][x], currentBlock, blockId);
}
// 向下移动：如果底部没有边界线且下方单元格存在
if (!currentCell.bottom && y < rows - 1) {
extractBlock(cells, cells[y + 1][x], currentBlock, blockId);
}
// 向左移动：如果左侧没有边界线且左侧单元格存在
if (!currentCell.left && x > 0) {
extractBlock(cells, cells[y][x - 1], currentBlock, blockId);
}
// 向右移动：如果右侧没有边界线且右侧单元格存在
if (!currentCell.right && x < cols - 1) {
extractBlock(cells, cells[y][x + 1], currentBlock, blockId);
}
}
/**
* 遍历整个棋盘，提取所有独立的谜题块。
* @param {Array<Array<cell>>} cells - 整个棋盘的2D单元格数组。
* @returns {Array<Array<cell>>} 所有提取出的谜题块的数组。
*/
function findAllBlocks(cells) {
const allExtractedBlocks = [];
let nextBlockId = 1;
for (let y = 0; y < cells.length; y++) {
for (let x = 0; x < cells[0].length; x++) {
const currentCell = cells[y][x];
if (!currentCell.taken) {
const newBlock = [];
extractBlock(cells, currentCell, newBlock, nextBlockId++);
if (newBlock.length > 0) {
allExtractedBlocks.push(newBlock);
}
}
}
}
return allExtractedBlocks;
}

工作原理：

1. extractBlock函数是核心的递归函数。它接收当前单元格、一个用于累积当前块单元格的数组以及块ID。
2. 在