1. 双巧克力谜题概述与生成挑战
“双巧克力”（double-choco）是一款由nikoli杂志推出的逻辑谜题游戏。其核心玩法是在一个由白色和灰色单元格组成的二维网格上，通过绘制实线将网格划分为若干个独立的“区块”。每个区块必须满足以下严格条件：
- 包含一对区域：每个区块内必须包含一个白色单元格区域和一个灰色单元格区域。
- 形状与大小匹配：这对白色和灰色区域必须具有相同的形状和大小。允许其中一个区域相对于另一个进行旋转或镜像变换。
- 可选数字线索：某些区域可能包含一个数字，表示该颜色在该区块内的单元格数量。
谜题生成的核心挑战在于如何自动生成一个既符合所有规则，又能保证其“可解性”的网格。这不仅仅是随机填充，更是一个约束满足问题。我们需要一种机制来：
- 有效地表示谜题板的状态。
- 识别和验证形成的区块。
- 迭代地构建谜题，确保每一步都朝着一个有效且可解的最终状态迈进。
2. 核心数据结构：增强型二维单元格网格
为了高效地表示谜题板并支持后续的算法操作，我们推荐使用一个二维数组来存储 cell（单元格）对象。每个 cell 对象应包含以下关键属性：
let cell = {
x: Number, // 单元格的X坐标
y: Number, // 单元格的Y坐标
color: "white" | "gray" | null, // 单元格的颜色（生成过程中确定，初始可为null）
number: null | Number, // 可选的数字线索
// 边界线标识：true表示该方向存在一条实线，false表示与相邻单元格连通
hasTopLine: boolean, // 上方是否有线
hasBottomLine: boolean, // 下方是否有线
hasLeftLine: boolean, // 左方是否有线
hasRightLine: boolean, // 右方是否有线
isTakenByBlock: boolean, // 该单元格是否已被分配给一个最终的、有效的区块
blockId: null | Number // 该单元格所属区块的唯一标识符
};
// 谜题板表示为一个二维数组
let board = Array(rows).fill(0).map(() => Array(cols).fill(0).map(() => ({
// 初始化属性...
hasTopLine: false, hasBottomLine: false, hasLeftLine: false, hasRightLine: false,
isTakenByBlock: false, blockId: null, color: null, number: null
})));数据结构说明：
- x, y: 便于引用和导航。
- color, number: 谜题的最终呈现信息，在生成过程中逐步确定。
- hasTopLine等边界属性：这是表示“线”的关键。true意味着在该方向上绘制了一条实线，从而分隔了单元格；false意味着没有线，单元格与相邻的同方向单元格连通。这种表示方式直接支持后续的区域识别算法。
- isTakenByBlock: 用于在谜题生成过程中跟踪哪些单元格已经被成功分配到有效的区块中。
- blockId: 标识单元格所属的区块，方便后续对整个区块进行操作和验证。
3. 区块识别算法：基于广度优先搜索 (BFS)
在谜题生成过程中，我们需要频繁地识别由当前边界线所围成的连通区域（即潜在的“区块”）。这可以通过标准的广度优先搜索（BFS）或深度优先搜索（DFS）来实现。这里我们采用BFS，因为它通常更适合于避免递归深度限制，并且易于理解。
该函数从一个起始单元格开始，根据hasLine属性（即!hasLine表示可连通），遍历所有相邻的连通单元格，并将它们收集到一个列表中。
/**
* 识别并返回从指定起始点开始的所有连通单元格组成的区域。
* 连通性由单元格的边界线属性决定（hasLine为false表示连通）。
*
* @param {number} startX - 起始单元格的X坐标。
* @param {number} startY - 起始单元格的Y坐标。
* @param {Array>} board - 谜题板的二维单元格数组。
* @param {Array>} visited - 用于本次BFS的访问状态数组，防止重复访问。
* @returns {Array 注意事项：
- visited数组在每次调用identifyConnectedRegion时都应重新初始化，以确保只识别当前调用所对应的单一连通区域。
- 此函数仅识别区域，不进行规则验证。规则验证将在更高层的生成算法中进行。
- 在实际应用中，需要处理边界条件，例如y > 0、x
4. 谜题生成算法：迭代与回溯
谜题生成过程是一个迭代的、可能需要回溯的搜索过程。其核心思想是：从一个空白板开始，逐步“绘制”线条来定义区块，同时确保每个定义的区块都符合“双巧克力”的规则，直到整个板面被填满。
以下是结合了上述数据结构和区块识别算法的生成框架：
function generateDoubleChocoPuzzle(rows, cols) {
// 1. 初始化谜题板
let board = Array(rows).fill(0).map((_, y) => Array(cols).fill(0).map((_, x) => ({
x, y,
color: null, number: null,
hasTopLine: false, hasBottomLine: false, hasLeftLine: false, hasRightLine: false,
isTakenByBlock: false, blockId: null
})));
let currentBlockId = 1;
/**
* 递归函数，尝试填充谜题板。
* @param {Array>} currentBoard - 当前谜题板状态。
* @returns {boolean} 如果成功生成谜题，返回true；否则返回false。
*/
function solve(currentBoard) {
// 查找下一个未被填充的单元格作为新区块的起点
let startCell = null;
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (!currentBoard[y][x].isTakenByBlock) {
startCell = currentBoard[y][x];
break;
}
}
if (startCell) break;
}
// 2. 终止条件：如果所有单元格都已被填充，则谜题生成成功
if (!startCell) {
// 最终验证：确保没有遗漏的孤立单元格或不合规的区域
return validateFinalBoard(currentBoard);
}
// 3. 尝试为startCell所在的区域绘制边界线，形成一个潜在区块
// 这一步是生成算法的核心和难点，需要策略性地选择边界线来形成有效的区块形状。
// 策略可以包括：
// a. 随机选择一个形状和大小（例如2到板面一半大小的偶数），并尝试将其放置在startCell附近。
// b. 使用某种搜索算法（如DFS或BFS）从startCell开始扩展，同时记录路径和形状。
// c. 预定义一些合法的双巧克力区块模板，并尝试将其适配到当前位置。
// 示例：假设我们有一些“尝试绘制边界”的策略，这里用伪代码表示
let possibleBoundaryConfigurations = generateBoundaryOptions(startCell, currentBoard);
for (let config of possibleBoundaryConfigurations) {
// 4. 应用边界配置（绘制线）
applyBoundaryConfiguration(currentBoard, config); // 这是一个会修改board的函数
// 5. 识别新形成的区域
let visitedForRegion = Array(rows).fill(0).map(() => Array(cols).fill(false));
let potentialBlockCells = identifyConnectedRegion(startCell.x, startCell.y, currentBoard, visitedForRegion);
// 6. 验证潜在区块的合法性
if (isValidDoubleChocoBlock(potentialBlockCells, currentBoard)) {
// 7. 如果合法，标记单元格为已占用，并分配blockId，设置颜色/数字
assignBlockProperties(potentialBlockCells, currentBlockId++, currentBoard);
// 8. 递归调用，尝试填充剩余部分
if (solve(currentBoard)) {
return true; // 成功
}
// 9. 回溯：如果递归失败，撤销当前区块的分配和边界线
revertBlockProperties(potentialBlockCells, currentBoard);
revertBoundaryConfiguration(currentBoard, config); // 撤销线
currentBlockId--;
} else {
// 如果当前边界配置形成的区块不合法，也需要撤销边界配置
revertBoundaryConfiguration(currentBoard, config);
}
}
return false; // 所有尝试都失败，回溯
}
// --- 辅助函数 (需要具体实现) ---
// 伪函数：生成可能的边界配置
// 这是最复杂的部分，决定了谜题的形状和难度。
// 可以尝试生成不同大小和形状的区块，并确保它们不侵犯已有的区块。
function generateBoundaryOptions(startCell, board) {
// 返回一个数组，每个元素代表一种边界线的绘制方案
// 例如：[{x1,y1,x2,y2,direction}, ...] 或更抽象的形状定义
// 这是一个启发式搜索和形状匹配的问题，超出了本教程的详细代码范畴。
// 简单来说，可以尝试从startCell向外扩展，随机选择路径，直到形成一个封闭区域。
// 每次扩展，都需要判断是否会侵犯已有的isTakenByBlock单元格。
return [/* 各种边界配置 */];
}
// 伪函数：应用边界配置到谜题板
function applyBoundaryConfiguration(board, config) {
// 根据config设置board中相关单元格的hasTopLine/hasBottomLine/hasLeftLine/hasRightLine为true
}
// 伪函数：撤销边界配置
function revertBoundaryConfiguration(board, config) {
// 将applyBoundaryConfiguration设置的线撤销（hasLine设回false）
} 
