生成可解的Double-Choco谜题：数据结构与算法深度解析-js教程-PHP中文网

生成可解的Double-Choco谜题：数据结构与算法深度解析

霞舞

发布： 2025-08-04 21:04:01

原创

1054人浏览过

生成可解的Double-Choco谜题：数据结构与算法深度解析

本文深入探讨了如何自动生成Nikoli杂志的Double-Choco谜题。文章首先介绍了游戏规则及其生成挑战，随后详细阐述了基于二维单元格网格的核心数据结构，并给出了利用递归遍历识别谜题区域的算法。在此基础上，文章进一步提出了一个迭代构建与回溯相结合的谜题生成策略，涵盖了形状表示、边界设置、验证机制等关键环节，旨在提供一套完整且专业的谜题生成解决方案。

1. Double-Choco 谜题生成挑战

double-choco（双巧克力）是一款由nikoli杂志推出的独特逻辑谜题。游戏目标是将一个由白色和灰色单元格组成的二维网格划分为若干个独立的区域（块）。每个块必须包含一对形状和大小完全相同的白色和灰色区域。这两个区域可以是彼此的旋转或镜像。某些区域可能带有数字，表示该颜色在该块中的单元格数量。

自动生成此类谜题的核心挑战在于：

如何有效地表示网格、单元格及其边界状态。
如何识别和比较复杂的不规则形状。
如何在填充网格的同时，确保每个生成的块都符合“同形同大”的规则。
最重要的是，如何保证最终生成的谜题是可解的，即不存在无法匹配或导致死锁的孤立区域。

2. 核心数据结构：二维单元格网格

为了有效地管理谜题板的状态，建议使用一个二维数组来表示网格，其中每个元素都是一个cell（单元格）对象。这个cell对象需要包含足够的信息来描述其自身状态以及与相邻单元格的连接关系。

let cell = {
    x: Number,         // 单元格的X坐标
    y: Number,         // 单元格的Y坐标
    color: "white" | "gray" | null, // 单元格的颜色，生成前可为null
    number: null | Number, // 可选：该颜色在该块中的单元格数量
    top: true | false, // 上方是否有边界（true表示有墙，false表示与上方单元格连通）
    bottom: true | false, // 下方是否有边界
    left: true | false,  // 左方是否有边界
    right: true | false, // 右方是否有边界
    taken: false,      // 是否已被某个块占用（在生成过程中使用）
    blockId: null      // 所属块的唯一标识符（用于区域识别）
};

登录后复制

数据结构解析：

x, y: 记录单元格的坐标，方便在算法中传递和引用。
color, number: 最终谜题的属性，在生成过程中逐步确定。
top, bottom, left, right: 这是定义块边界的关键属性。当一个方向的布尔值为true时，表示该单元格与相邻单元格之间存在一条实线边界；false则表示它们是连通的，属于同一个潜在的区域。初始时，所有这些边界都可以设置为false，表示整个网格是一个大连通区域。
taken: 在谜题生成过程中，用于标记已被分配到某个块的单元格，避免重复处理。
blockId: 在完成块识别后，用于标记单元格所属的块。

3. 算法：从边界定义到区域识别

在谜题生成过程中，我们不仅需要设置边界，还需要能够验证这些边界是否正确地划分了区域，以及识别出各个独立的块。这可以通过一个基于深度优先搜索（DFS）或广度优先搜索（BFS）的“洪水填充”（Flood-Fill）算法来实现。

以下是一个递归实现的take函数，用于在给定边界条件下识别连通的单元格区域（即一个块或一个子区域）。

function extractBlocks(cells) {
    // 初始化所有单元格的 taken 状态为 false，blockId 为 null
    for (let row of cells) {
        for (let cell of row) {
            cell.taken = false;
            cell.blockId = null;
        }
    }

    let currentBlockId = 0;
    const height = cells.length;
    const width = cells[0].length;

    // 递归函数：用于遍历并标记属于同一连通区域的单元格
    function take(cell, blockId) {
        // 边界检查：防止越界
        if (cell.x < 0 || cell.x >= width || cell.y < 0 || cell.y >= height) {
            return;
        }
        // 如果单元格已被访问或不属于当前块（即已被其他块占用），则返回
        if (cell.taken) {
            return;
        }

        cell.taken = true;     // 标记为已访问
        cell.blockId = blockId; // 分配块ID

        // 递归访问未被边界阻挡的相邻单元格
        if (!cell.top && cell.y > 0) { // 如果上方没有边界且未越界
            take(cells[cell.y - 1][cell.x], blockId);
        }
        if (!cell.bottom && cell.y < height - 1) { // 如果下方没有边界且未越界
            take(cells[cell.y + 1][cell.x], blockId);
        }
        if (!cell.left && cell.x > 0) { // 如果左方没有边界且未越界
            take(cells[cell.y][cell.x - 1], blockId);
        }
        if (!cell.right && cell.x < width - 1) { // 如果右方没有边界且未越界
            take(cells[cell.y][cell.x + 1], blockId);
        }
    }

    // 遍历所有单元格，启动洪水填充以识别所有块
    for (let y = 0; y < height; y++) {
        for (let x = 0; x < width; x++) {
            if (!cells[y][x].taken) {
                // 发现一个未被访问的单元格，它是一个新块的起点
                take(cells[y][x], currentBlockId++);
            }
        }
    }

    // 收集并返回识别出的块
    const blocks = new Map();
    for (let y = 0; y < height; y++) {
        for (let x = 0; x < width; x++) {
            const cell = cells[y][x];
            if (cell.blockId !== null) {
                if (!blocks.has(cell.blockId)) {
                    blocks.set(cell.blockId, []);
                }
                blocks.get(cell.blockId).push(cell);
            }
        }
    }
    return Array.from(blocks.values()); // 返回所有识别出的块的数组
}

登录后复制

take函数原理： 该函数从一个未被taken的单元格开始，递归地访问所有与之连通（即之间没有边界）的相邻单元格，并将它们标记为已访问，并赋予相同的blockId。当所有可达的单元格都被访问后，一个完整的连通区域（一个块）就被识别出来了。通过遍历整个网格，对每个未被访问的单元格启动一次take过程，即可识别出所有的独立块。

4. 算法：自动生成可解谜题的策略

生成可解的Double-Choco谜题是一个复杂的搜索问题，通常采用迭代构建与回溯相结合的方法。

4.1 迭代构建法概述

基本思路是：从一个空白网格开始，迭代地选择一个未被填充的区域，尝试生成一个符合规则的“双巧克力”块（一对形状相同的白色和灰色区域），将其放置到网格中，并设置相应的边界。如果放置成功且没有导致后续的死锁（例如，留下无法匹配的孤立区域），则继续下一个块的生成；否则，回溯到上一步，尝试其他选择。

即构数智人

即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

查看详情

4.2 形状表示与匹配

要比较白色和灰色区域的形状，我们需要一种标准化的表示方法。

相对坐标集： 一个形状可以表示为其所有单元格相对于其“左上角”或“最小X、最小Y”单元格的相对坐标集合。例如，一个L形可能表示为 {(0,0), (1,0), (0,1)}。
形状规范化： 为了方便比较，需要对形状进行规范化。例如，将其所有相对坐标平移，使最小X和最小Y都为0。
旋转与镜像变换：
- 旋转90度： (x, y) 变为 (-y, x)，然后重新规范化。
- 镜像（水平）： (x, y) 变为 (-x, y)，然后重新规范化。
- 镜像（垂直）： (x, y) 变为 (x, -y)，然后重新规范化。通过对一个形状进行所有可能的旋转和镜像变换，生成其所有等价形态的集合。在匹配时，只需检查灰色区域的规范化形状是否在白色区域的等价形态集合中。

4.3 边界的动态设置

当确定了一个白色区域W和一个灰色区域G形成一个块时，需要更新其内部单元格的top, bottom, left, right属性：

对于块内的每个单元格c：
- 如果c的某个方向的邻居n也属于当前块（即n在W或G中），则c与n之间的边界应设置为false（连通）。
- 如果c的某个方向的邻居n不属于当前块（即n在块外或不存在），则c与n之间的边界应设置为true（有墙）。

4.4 关键的验证与回溯机制

这是生成可解谜题的关键。每次放置一个块后，必须进行验证：

孤立区域检查： 使用第3节的extractBlocks函数，检查网格中所有未被taken的单元格形成的连通区域。如果存在任何一个区域的单元格数量为奇数，则说明当前块的放置导致了后续无法完成匹配的情况，必须回溯。
死锁检查： 随着网格被填充，剩余的空白区域可能会变得支离破碎。需要确保剩余的空白区域仍然能够形成至少一对匹配的形状。这可能需要更复杂的启发式或预判。

4.5 生成算法流程细化

初始化网格：
- 创建XxY的cells二维数组。
- 所有cell的color为null，taken为false。
- 所有cell的top, bottom, left, right初始为false（表示无墙）。
主循环（回溯搜索）：
- 定义一个递归函数generatePuzzle(grid)。
- 基线条件： 如果网格中所有单元格都已被taken，则谜题生成成功，返回grid。
- 选择起点： 找到网格中第一个未被taken的单元格(sx, sy)。
- 尝试生成白色区域W：
  - 从(sx, sy)开始，随机或启发式地“生长”一个白色区域W。W应是连通的，且只包含未被taken的单元格。
  - 控制W的大小（例如，2到板子大小的一半）。
  - 获取W的规范化形状及所有变换形态。
- 尝试寻找匹配的灰色区域G：
  - 遍历所有未被taken的单元格(gx, gy)（除了W中的单元格）作为潜在的灰色区域起点。
  - 从(gx, gy)开始，尝试“生长”一个灰色区域G，使其形状能够匹配W的某个变换形态。
  - 确保G中的单元格也是未被taken的。
  - 如果找到一个匹配的G： a. 临时应用块： 将W和G中的单元

以上就是生成可解的Double-Choco谜题：数据结构与算法深度解析的详细内容，更多请关注php中文网其它相关文章！