生成可解的双巧克力谜题：数据结构与算法指南

双巧克力谜题概述

“双巧克力”（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）的遍历算法实现。该算法会从一个未被访问的单元格开始，沿着没有边界线的路径，收集所有连通的单元格，形成一个完整的块。

Noya

让线框图变成高保真设计。

下载

/**
 * 递归函数：从指定单元格开始，寻找并收集所有连通的单元格，形成一个块。
 * @param {Array>} grid - 谜题网格
 * @param {number} x - 当前单元格的X坐标
 * @param {number} y - 当前单元格的Y坐标
 * @param {number} currentBlockId - 当前块的唯一ID
 * @param {Array