生成可解的双巧克力谜题：高效的数据结构与算法实践

本文深入探讨了如何为“双巧克力”（Double-Choco）谜题游戏设计一套高效的自动生成可解谜题的系统。我们将介绍核心的数据结构——一个增强型二维单元格网格，并详细阐述基于广度优先搜索（BFS）的区域识别算法。在此基础上，文章将构建一个迭代式的谜题生成框架，该框架通过智能绘制边界线、验证形成的区块形状及其内部白灰区域的匹配性，并结合回溯机制，确保生成谜题的有效性和可解性。

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<Array