Fw: [問題] 數牆Nurikabe題目產生器的唯一性檢查
※ [本文轉錄自 puzzle 看板 #1gbdxeLg ]
作者: buffalobill (水牛比爾) 看板: puzzle
標題: [問題] 數牆Nurikabe題目產生器的唯一性檢查
時間: Tue Sep 1 15:29:40 2026
[問題] 數牆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://www.ptt.cc/bbs/puzzle/M.1788247784.A.56A.html
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: buffalobill (60.251.148.94 臺灣), 09/01/2026 15:29:58