[问题] 数墙Nurikabe题目产生器的唯一性检查 我还满喜欢玩 Nurikabe 的 https://www.puzzle-nurikabe.com/ 简介一下Nurikabe规则 题目原始盘面上有若干数字代表岛屿 你要在盘面上画上海洋 将所有岛屿区隔开来 使岛屿的大小为该数字 海洋则要保持连通性 且不得出现2x2区块： 范例： ┌────────┐┌────────┐ │　　　　　　　　││　　█　　　█　│ │　４　６　　　　││　４█６　　█　│ │　　　　　　　　││███████　│ │４　　　　　　４││４　　　█　█４│ │　　　　　　　　││█████　██│ │　３　　　３　１││█３　　█３█１│ │６　　　　　　　││６███████│ │　　　　　　２　││　　　　　█２　│ └────────┘└────────┘ 想要自己刻一个题目产生器 但卡在唯一性的检查上 我先讲讲我目前的做法： 步骤一：初始化 产生NxN的空白盘面，假设N=8，想要更难的可以N=12, N=16 将所有偶数行与偶数列填上海 (0-indexed)： ┌────────┐ │████████│ │█　█　█　█　│ │████████│ │█　█　█　█　│ │████████│ │█　█　█　█　│ │████████│ │█　█　█　█　│ └────────┘ 这样就已经是一个合格的盘面了，共有16座岛屿 当然这个盘面超无聊 再来我们做点变化，以免玩家知道(奇,奇)一定是岛 步骤二：翻转 有0.5机率选行，有0.5机率选列 若选行，则对每个奇数行，有0.5机率翻转整个行(岛海互换) 若选列，则对每个奇数列，有0.5机率翻转整个列(岛海互换) ┌────────┐ │████████│ │█　█　█　█　│ │████████│ │　█　█　█　█│ ←翻转 │████████│ │　█　█　█　█│ ←翻转 │████████│ │█　█　█　█　│ └────────┘ 注意翻转後的盘面也是合法状态 步骤三：填岛 再来是决定岛屿数量Cnt 我控制在 [N^2/8, N^2/6] 之间 以N=8而言，岛屿数量为[8, 10]之间 进行填岛 假设我想要10个岛 while(岛屿数量 > 10){ 随机选取一格海面 if(将该海面填成岛後，海面仍维持连通性) 则 填岛 } 反复进行这样的步骤後得到 ┌────────┐ │████████│ │　　█　　　　　│ │　　██████│ │　█　█　█　█│ │██　███　　│ │　█　█　█　　│ │████████│ │█　█　█　　　│ └────────┘ 很难看出是上面那个盘面填成的吧 为了避免「一个超大岛，其它都1」 我if还加了条件「填岛後形成的岛面积要小於等於N」才会填岛 步骤四：削海 对每格海面 检查，如果将此格海面填成岛 是否会破坏连通性or改变岛屿的数量 若都不会，则填岛 检查是由外向内，先填边边再往中间检查 检查完长这样： ┌────────┐ │　　█　　　　　│ │　　█　　　　　│ │　　██████│ │　█　█　█　　│ │██　██　　　│ │　█　█　█　　│ │████████│ │　　█　█　　　│ └────────┘ 可以看到上面那根海消失了 削海後岛的面积是可以大於N的 这时通常也不会有超大岛出现了 步骤五：放数字 放数字的规则如下 ．面积为1的岛屿只有一种放法 ．若一个岛与其它岛有对角关系(左上-右下) or (右上-左下) 且该对角已有数字放置，将本岛的数字置於该对映角落 ．若两个岛都还没放数字，且具有对角关系 将两个岛的数字放上去呈对角 ．若该岛有靠边，且只有一格靠边，那就在该格放数字 ．最後还是没有数字的岛，随机挑一个邻接海域数最多的格子放数字 个人猜测是尽可以让数字凑对角 比较容易出现具唯一解的盘面 ┌────────┐ │　　█　　　　　│ │　　█10　　　　│ │　７██████│ │　█３█１█　　│ │██　██７　　│ │１█　█１█　　│ │████████│ │　２█１█３　　│ └────────┘ 步骤六：刚性检查 这个步骤比较复杂 刚性就是检查一个岛屿的「形状能不能改变」 形状改变的定义是 列举 一格该岛邻近的海格子 x 一格该岛海边岛格子 若两格交换後，不改变岛屿数量and不破坏海域连通性 则视作形状可以改变，我举个例子 ┌──────┐ │███１█１│ │█ ███│ │█３██１█│ │███１██│ └──────┘ ３岛屿，形状可以改变， 不改变岛屿数量不破坏海域连通性： ┌──────┐ │███１█１│ │█ ████│ │█３ █１█│ │███１██│ └──────┘ 发生这种情形，盘面就没有唯一解 此时可以尝试解救： ．每个岛屿以一次为限，将数字移动至交换後的岛上 再检察该岛屿是否具备刚性 若所有岛皆具刚性，则此盘面为合法盘面，可以输出 若岛解救一次後仍不具刚性，则此盘面为不合法盘面，重新生成 如上例将３移动至交换後的岛上，该岛便获得刚性： ┌──────┐ │███１█１│ │█ ████│ │█ ３█１█│ │███１██│ └──────┘ 但这种作法有极限 如以下盘面无法透过交换移动数字解救： ┌─────────┐ │████████１│ │１█１█ █１██│ │███７　　█１█│ │█１██　　███│ │██１█ █１█１│ │１████████│ └─────────┘ 不管７放在哪边，该岛至少都会有三种变形的可能 通过刚性检查後 整个盘面就可以拿掉海洋只留数字输出成题目谜面： ┌────────┐ │　　　　　　　　│ │　　　10　　　　│ │　７　　　　　　│ │　　３　１　　　│ │　　　　　７　　│ │１　　　１　　　│ │　　　　　　　　│ │　２　１　３　　│ └────────┘ 唯一解 透过上述步骤产生出来的谜面 已经是实际上可以进行游玩的Nurikabe谜面了 但问题是，即使通过了刚性检查 还是常常产出具备多重解的盘面： ┌────────┐ │████４　　　│ │█　　３████│ │█████１█　│ │４　　　██６　│ │█████　　　│ │　６█１████│ │　　███　█２│ │　　█１█２█　│ └────────┘ ┌────────┐ │████４　　　│ │█　█３████│ │█　█　█１█　│ │４　█　██６　│ │█████　　　│ │　６█１████│ │　　███　█２│ │　　█１█２█　│ └────────┘ 目前卡在这点 有两种做法 1. 写出一个快速求解器，可以根据谜面快速找出所有解 目前用暴力DFS求解只能用在8x8盘面上，用於更大的盘面就会超时 主要是大数字的形状变化太多... 2. 根据产生出来的盘面，找出可以限制重复解出现的「关节」处进行修改，使解唯一 这就卡在悟性不够，写不出来Orz 我的程度就是想出刚性而已 目前的成果已经可以在这里游戏(只支援键盘操作) https://buffalobill-taiwan.github.io/htmlterm/ 输入指令nurikabe就可以玩了 还有很多游戏tetris jpmj等... --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 60.251.148.94 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1788247784.A.56A.html ※ buffalobill:转录至看板 Math 09/01 15:29