唯一候選消去法:區域早,行列晚
唯一候選消去法,是每個 Meowdoku 玩家早就在用的技巧,就算叫不出名字:一列、一欄或一個區塊只剩一個合法格子,那一格就一定是貓,不需要再多想。這個網站的開局技巧文章,測量了在免費貓咪放好之後,這三者裡哪一個最常先剩下那唯一一格,結果區域大幅領先。但那只是一個瞬間的快照。把整個解題過程走完之後,畫面比那個快照更清楚——而且它告訴你一件開局那一刻無法告訴你的事:什麼時候該檢查哪一種視角。
什麼是唯一候選消去法
一列、一欄或一個區塊,都是恰好要放一隻貓的容器。把一個容器裡所有不合法的格子都劃掉,如果只剩一格,那一格就是貓——完全不用考慮棋盤其他地方。這跟數獨裡「唯一數」的概念一模一樣,只是套用在三種容器上,而不是兩種。
三種容器的運作機制完全相同:數一數容器裡還合法的格子,如果只剩一格,就把貓放在那裡。這個技巧本身,並沒有特別偏袒行、欄或區域中的任何一種。真正有差別、也是這篇文章接下來要測量的,只是每一種容器實際上多常、多早會走到只剩一格的地步。
完整的全貌,不只是開局
開局技巧文章只問了一個問題:免費貓咪放好之後,哪一種容器最有可能已經只剩一個候選格?答案很明確是區域——在困難難度的棋盤上,那個時刻有 12% 的未解區域已經被逼出貓咪,相對之下未解的列只有 0.7%。
這回答了「先檢查什麼」,但沒有回答「第五步該檢查什麼」,或「第十步」,或「終盤該檢查什麼」。為了得到這些答案,這篇文章把唯一候選消去法一路跑到底——找出每一個被逼出的貓咪就放上去,然後重新掃描,一次又一次,直到沒有任何一列、一欄或一個區塊只剩一個合法格子為止——並且記錄下沿路是哪一種容器逼出了每一隻貓,以及那一刻棋盤上已經有多少隻貓。
從頭到尾,區域都做了大部分的工作
在每個難度各四百個棋盤上,一路跑到消去法卡住為止,以下是整個過程(不只是開局)中,各種容器逼出貓咪的比例:
| 棋盤 | 來自列 | 來自欄 | 來自區域 |
|---|---|---|---|
| 簡單 5×5 | 31% | 31% | 38% |
| 普通 7×7 | 20% | 20% | 60% |
| 困難 9×9 | 15% | 15% | 69% |
| 極難 10×10 | 5% | 6% | 89% |
在每個難度下,列和欄幾乎平分剩下的比例,這並不意外——這套規則裡沒有任何理由讓兩者不對等,它們就是同一個形狀轉了九十度而已。真正不對稱的,是它們相對於區域的比例,而且這個差距每次棋盤變大都會再拉開。
行和列是終盤才用得上的工具
光看比例還低估了時機上的懸殊程度。針對每一個被逼出的貓咪,記錄下這個推論出現當下,棋盤上已經有多少隻貓:
| 棋盤 | 列 | 欄 | 區域 | 棋盤大小 |
|---|---|---|---|---|
| 簡單 5×5 | 2.9 | 2.9 | 2.7 | 5 |
| 普通 7×7 | 4.5 | 4.5 | 3.4 | 7 |
| 困難 9×9 | 6.6 | 6.5 | 4.5 | 9 |
| 極難 10×10 | 8.0 | 7.6 | 3.3 | 10 |
在極難難度下,一個由列逼出的貓咪,平均要等到十隻貓裡已經有八隻放好——通常是倒數第二隻貓。而一個由區域逼出的貓咪,平均只在 3.3 隻的時候就出現,連三分之一都不到。以佔整場遊戲進度的比例來看,隨著棋盤變大,區域推論會愈來愈早出現——從簡單難度大約進行到一半,到極難難度只到三分之一——而列和欄推論則愈來愈晚,從剛過一半,一路推到五分之四。
為什麼區域先發,行列殿後
一個區域一開始就可以很小。沒有任何規則阻止一個區域一開始只有兩三格,所以只要附近一次放置就能把剩下的格子排除掉,逼出貓咪。但一列或一欄不可能一開始就小——它永遠是棋盤的整個寬度,而且沒有任何單一消去技巧一次能讓它縮小超過一兩格。
放在棋盤任何位置的一隻貓,幾乎會讓其他每一列和每一欄各少掉一格:也就是它自己那一欄裡,每一列各一格。要把某一列從 N 格縮到只剩一格,消去法必須先移除掉 N − 1 格——一次一格的話,這幾乎等於要放完一整個棋盤大部分的貓才辦得到。區域完全沒有這種下限。這正是行和欄是終盤訊號、而區域不是的全部原因:這是內建在「一列一開始有多大」這件事裡,跟推理本身無關。
這三種視角真正勢均力敵的地方
簡單 5×5 棋盤是唯一一個情況不再懸殊的地方。在那裡,行和欄加起來占了所有唯一候選推論的 62%,區域只有 38%——區域個別來看仍然領先,但差距完全不像普通難度以上那麼大。開局技巧文章針對單純的新棋盤也提過同樣的事:「只有在 5×5 棋盤上,這三種視角才真正勢均力敵」。這篇文章證實這個結論適用於整場遊戲,而不只是第一步。
原因跟第五節講的一樣,只是反過來看。5×5 的區域很少比一整列五格小太多,所以讓大棋盤變得懸殊的那個大小差距,在這裡幾乎不存在。在簡單難度養成的習慣——檢查一列的效果幾乎跟檢查一個區域一樣好——正好就是在困難和極難難度上會誤導你的習慣。
遊戲內的提示按鈕實際上告訴你什麼
提示功能找的正是這篇文章測量的那三種被逼出的格子,但它並不是對稱地檢查:它會先檢查完所有列,才檢查任何一欄,再檢查完所有欄,才檢查任何一個區域,然後回傳第一個找到的結果。當一個由列逼出的格子和一個由區域逼出的格子同時存在於棋盤上時,提示會顯示那個列。
這樣設計提示按鈕其實很合理——玩家要的通常只是一個合法的下一步,不是一堂講解這是用哪種技巧解出來的課。但這也代表提示並不能代表解題過程中實際發生的比例。如果你靠它來學這款遊戲的規律,它會不成比例地讓你看到比較少見、比較晚才會出現的技巧:上面那些表格,才是在不預設優先順序、逐一檢查每種容器時,消去法真正偏好的結果。
什麼時候該檢查哪個視角:一份清單
把以上四張表格化成實用版本:
- 整場遊戲都先檢查區域。 在 7×7 以上的所有棋盤上,區域都占了唯一候選推論的多數,而且整場解題過程都會持續出現,不只是開局。
- 行和欄,等棋盤快滿的時候再檢查。 在困難和極難難度上,貓還沒放到六隻以上之前,它們幾乎不會給你任何東西。太早檢查,大多只是浪費一次掃描。
- 在簡單難度,三種都要檢查。 棋盤小到行和欄幾乎追上區域,所以沒有真正可以跳過的捷徑。
- 不要把提示當成技巧排行榜。 它只會依照列→欄→區域的順序顯示第一個被逼出的格子,並不是最常見的那一種——要看真正的排名,請用上面的表格。
這是怎麼測量出來的
兩張表格都來自遊戲本身的產生器,在四個難度下各跑了四百個新棋盤。從開局出發——也就是起始貓咪,加上每一個只有一格的區域,跟前一篇文章定義的完全一樣——每個棋盤都反覆找出所有只剩一個合法格子的列、欄和區域,全部放上貓咪,再重新掃描,直到沒有任何格子被逼出為止。每一次這樣的事件都會記錄下容器類型,以及當下棋盤上已經有多少隻貓;如果同一格同時是不只一種容器裡最後一個候選(平手的情況),就會被算進它同時符合的每一種容器類型裡。
這些都是目前這個產生器所產生棋盤的特性。這篇文章附帶的測試套件,每次執行都會從新產生的棋盤重新推導這兩張表格,所以未來只要區域大小的調整一改動,就會直接讓建置失敗,而不是讓一個過時的統計數字繼續留在頁面上。
分階段自己試試看
開一個困難 9×9 棋盤。棋盤前半段只檢查區域,看看單靠這樣能走多遠。等貓放到六、七隻之後,再開始掃行和欄——平均來說,那才是它們真正開始有用的時間點。
棋盤都是在你的瀏覽器裡生成的,你玩的內容不會被傳送到任何地方。