本文深入探讨了如何为“双巧克力”（double-Choco）谜题游戏自动生成可解谜题。我们将介绍一种高效的数据结构——基于2D网格的单元格对象，该对象包含边界信息、颜色和状态。在此基础上，我们将详细阐述一种递归的块识别算法（类似于深度优先搜索），以及如何将其整合到迭代式谜题生成流程中，以确保生成的谜题满足游戏规则，并具备可解性。文章将提供示例代码，并讨论生成过程中的关键考量与优化策略。
双巧克力谜题概述
“双巧克力”（double-choco）是一款由nikoli杂志推出的独特逻辑谜题。游戏在一个由白色和灰色单元格组成的2d网格上进行。玩家的目标是通过绘制线条将网格划分为若干个“块”。每个块必须包含一对形状和大小完全相同的白色区域和灰色区域。这两个区域可以是彼此的旋转或镜像。某些区域可能带有数字，表示该颜色在该块中的单元格数量。
自动生成此类谜题的关键挑战在于，不仅要创建满足基本规则的块，还要确保整个谜题是可解的，并且没有遗留下无法形成合法块的孤立区域。
核心数据结构设计
为了高效地表示谜题板并支持生成算法，我们推荐使用一个二维数组来存储自定义的“单元格”（Cell）对象。每个Cell对象应包含以下属性，以全面描述其状态和边界信息：
let Cell = { x: number, // 单元格的X坐标 y: Number, // 单元格的Y坐标 color: "white" | "gray", // 单元格的颜色，初始化时可为空或未定义 number: null | Number, // 如果有数字提示，则为数字，否则为null // 边界标志：true表示该方向有边界线（墙），false表示与相邻单元格连通 top: Boolean, // 上方是否有边界 bottom: Boolean, // 下方是否有边界 left: Boolean, // 左方是否有边界 right: Boolean, // 右方是否有边界 blockId: null, // 用于标记该单元格所属的块ID，null表示未分配 isOccupied: Boolean // 在生成过程中标记单元格是否已被某个块占据 };
数据结构解释：
- x, y：坐标信息便于引用和调试。
- color：存储单元格的颜色，这在生成阶段会被赋值。
- number：用于存储谜题提示数字。
- top, bottom, left, right：这些布尔值是定义块形状的关键。true表示在该方向上有一条实线，将当前单元格与相邻单元格分隔开。false表示它们是连通的，属于同一个块。在初始状态下，所有这些都可以设置为false，表示一个完全开放的网格。
- blockId：在块识别算法中使用，确保每个单元格只属于一个块，并能快速查询其所属块。
- isOccupied：在生成过程中，标记单元格是否已被分配到某个最终的谜题块中，避免重复处理。
谜题板本身可以表示为一个Cell对象的二维数组：let board = Array(rows).fill(0).map(() => Array(cols).fill(0).map(() => ({…Cell})));
块识别算法：从网格中提取块
生成谜题的核心在于能够准确地识别出当前网格状态下形成的“块”。这可以通过一种类似于深度优先搜索（DFS）或广度优先搜索（BFS）的遍历算法实现。该算法会从一个未被访问的单元格开始，沿着没有边界线的路径，收集所有连通的单元格，形成一个完整的块。
/** * 递归函数：从指定单元格开始，寻找并收集所有连通的单元格，形成一个块。 * @param {Array<Array<Object>>} grid - 谜题网格 * @param {number} x - 当前单元格的X坐标 * @param {number} y - 当前单元格的Y坐标 * @param {number} currentBlockId - 当前块的唯一ID * @param {Array<Object>} blockCellsList - 用于收集当前块所有单元格的列表 */ function findBlockCells(grid, x, y, currentBlockId, blockCellsList) { // 边界检查：确保坐标在网格范围内 if (x < 0 || x >= grid[0].length || y < 0 || y >= grid.length) { return; } const cell = grid[y][x]; // 检查：如果单元格已经被分配到某个块，或者已在当前遍历中访问过，则停止 if (cell.blockId !== null) { return; } cell.blockId = currentBlockId; // 将当前单元格分配给当前块 blockCellsList.push(cell); // 将单元格添加到当前块的列表中 // 递归探索相邻单元格，前提是它们之间没有边界线 if (!cell.top) findBlockCells(grid, x, y - 1, currentBlockId, blockCellsList); if (!cell.bottom) findBlockCells(grid, x, y + 1, currentBlockId, blockCellsList); if (!cell.left) findBlockCells(grid, x - 1, y, currentBlockId, blockCellsList); if (!cell.right) findBlockCells(grid, x + 1, y, currentBlockId, blockCellsList); } /** * 从整个网格中提取所有独立的块。 * @param {Array<Array<Object>>} grid - 谜题网格 * @returns {Array<Array<Object>>} 包含所有识别出的块的列表，每个块是一个单元格列表 */ function extractAllBlocks(grid) { let allBlocks = []; let blockCounter = 0; // 在每次提取前，重置所有单元格的blockId，确保重新识别 grid.forEach(row => row.forEach(cell => cell.blockId = null)); for (let y = 0; y < grid.length; y++) { for (let x = 0; x < grid[0].length; x++) { // 如果当前单元格尚未被分配到任何块 if (grid[y][x].blockId === null) { blockCounter++; // 为新块生成一个ID let currentBlockCells = []; findBlockCells(grid, x, y, blockCounter, currentBlockCells); // 只有当成功找到单元格形成块时才添加 if (currentBlockCells.length > 0) { allBlocks.push(currentBlockCells); } } } } return allBlocks; }
注意事项：
- findBlockCells函数是递归的，用于探索单个连通组件。
- extractAllBlocks函数遍历整个网格，确保所有未分配的单元格都被用作新块的起点，从而找到所有独立的块。
- 在每次调用extractAllBlocks之前，重置blockId是至关重要的，以确保每次分析都是基于当前边界状态的全新识别。
谜题生成算法流程
谜题生成是一个迭代和回溯的过程，其核心思想是逐步填充网格，每次放置一对符合规则的白色和灰色区域，并同时定义其边界。
-
初始化网格：
- 创建一个MxN的Cell对象二维数组，所有单元格的isOccupied设为false，color未定义，top/bottom/left/right边界全部设为false（表示初始时无边界）。
