本文深入探讨了如何为“双巧克力”（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
注意事项：
findBlockCells函数是递归的，用于探索单个连通组件。extractAllBlocks函数遍历整个网格，确保所有未分配的单元格都被用作新块的起点，从而找到所有独立的块。在每次调用extractAllBlocks之前，重置blockId是至关重要的，以确保每次分析都是基于当前边界状态的全新识别。
谜题生成算法流程
谜题生成是一个迭代和回溯的过程，其核心思想是逐步填充网格，每次放置一对符合规则的白色和灰色区域，并同时定义其边界。
初始化网格：
创建一个MxN的Cell对象二维数组，所有单元格的isOccupied设为false，color未定义，top/bottom/left/right边界全部设为false（表示初始时无边界）。
以上就是生成可解的双巧克力谜题：数据结构与算法指南的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1513656.html
微信扫一扫 
支付宝扫一扫 
