[非官方題解] P&KU3（中）- 世界上最大的仙人指路

在做P&KU3（中）時，「世界上最大的仙人指路」為本人留下了很深刻的印象：「世界上最～」系列可謂是Puzzle Hunt的常客，而本人從開始玩Puzzle Hunt到現在，還是沒能成功做出任何一道，直到參加了P&KU3（中）後，才第一次做出這類型的題目。本人很喜歡這道題，看似無從入手的謎面卻蘊含了富有邏輯的解題思路，所以才決定寫下這篇解析，除了分享自己的思路外，也可以把這道好題分享給更多人。

本題是一道位於「镜湖」的「湖心岛」區的Meta。這道Meta使用「抉择，抉择」和「汇流」這兩種Feeder，分別是藍色和紅色的 12×12 仙人指路（Yajilin）謎題。我們需要找出兩個謎面分別有多少個解。

仙人指路基本規則如下（轉載自金牌解謎）：

画一条横平竖直地经过一些空格中心且不和自身交叉的回路，并涂黑剩余所有空格。任意相邻的两格不能都涂黑。灰格内带箭头的数字表示从此格开始在这个方向中涂黑的格数。

另外，有問號的格子也不能塗黑。

在做這題的仙人指路時，其中一個較常用的推論方法如下：假如我們塗黑一個十/T/L字路口中間的方格，那麼回路必須經過相鄰格子。不過相鄰格子只有一個開口，回路並不能經過相鄰格子，出現矛盾。因此，路口中間的方格必定不能塗黑，回路必須經過中間的方格，而且相鄰格子中必須正好有兩個格子沒有塗黑，L字路口則必須有線段經過。兩個謎面均有大量的分叉路口，所以我們會經常用到此法則。

我們先做紅色的「汇流」。經簡單推論可以得到以下盤面。

假設R2C3為黑塊，那麼回路必須經過R1C4和R3C4，和R4C4矛盾。

因此R2C3不是黑塊，而R1C4是黑塊。

設R9C7不為黑塊。那麼R9C9的線必須往上，不過這會導致左下角出現獨立回路。因此，R9C7必為黑塊。

我們最後得到此唯一解。

因此，這道小題的答案為 1。

我們再看看藍色的「抉择，抉择」。「抉择，抉择」比「汇流」簡單，經簡單推論就可以得到此唯一解。因此，這道小題的答案亦為 1。

接著，我們看一看比較複雜的Meta。

留意題目中的注意事項。由於所有提示數只計算在其所屬 12×12 區域內的黑格數量，因此我們在數黑格數量時不用考慮其他區域的黑格數量。

我們先觀察一下大盤面。大盤面由若干個 12×12 大的藍色和紅色Feeder組成，理論上可無限延伸。盤面的第一列為紅色Feeder，其餘為藍色Feeder。圖中的 (i, j) 座標則表示了該Feeder位於盤面的第i行、第j列。

現在我們來看看下方 s(a, b) 做的是什麼。 s(a,b) 裏面有一個名為 SolutionCount （解的個數）的函數，函數的輸入值則是一組求和算式。根據上面的圖，我們可以猜測 (a,b) 代表了大盤面的行數和列數，而雙重求和則代表把這ab個區塊合併成一個大謎題。例如當 a = 3, b = 4 時，謎題會長這個樣子。SolutionCount 則計算這個大謎題的解數。

我們的目標則是找出當 a, b 為不同數值時，這個大謎題到底有多少個解。

在解題前，我們不如先觀察一下大謎題的結構。以下是 a = 4, b = 4 時的大謎題，所有的提示都被塗成了綠色。

我們發現，相鄰行的藍色方塊都被一整行的提示分開了，必須透過第一列的紅方塊連接。我們可以畫一下方塊的相鄰狀態，然後把它們分成不同類別。

• 紅T (Top, 上): 只在下方和其他紅色方塊連接
• 紅M (Middle, 中): 在上、下方和其他紅色方塊連接
• 紅B (Bottom, 下): 只在上方和其他紅色方塊連接
• 藍S (Start, 始): 在左右和方塊連接
• 藍E (End, 末): 只在左面和其他方塊連接

不同方塊的相鄰情況不同，我們要分開處理。此外，當 b = 1 時，大謎題只有紅色方塊。我們也要分開處理這個情況。

此外，我們可以發現所有方塊的R5C12必為提示格，所以回路不能從其他方塊的R5C1進入左邊的方塊。我們可以在題面增加圍牆，表示回路不能經過的地方。

由於回路是閉合的，所以對於任意一個方塊，回路每進入一次方塊，那麼就必須離開一次。因此，穿越其邊界的線段數量必定是偶數。此外，回路需經過所有題面，所以如果大盤面由至少兩個方塊組成，那麼每個方塊必須有至少一個線段穿越其邊界。結合以上兩點，所有方塊需要有至少兩條、且有偶數條線段穿越其邊界。

我們先看看藍E方塊。R1C6不能為黑塊，否則下方會出現矛盾。

下方的 <- 3 提示指明了四格中有三個是黑塊。分情況推論後可發現R10C3和R10C7必定是黑塊，否則會有矛盾。

利用以上發現可推出R10C5亦為黑塊，經簡單推論可得以下盤面。

留意上方的<-2提示。只有R2C1不是黑塊才不會出現矛盾。

塗黑R5C6時會出現矛盾，因此回路必定經過R5C6，而R3C6為黑塊。

此時，我們可以發現這個方塊其實有兩個解（以下稱為A和B）。

解完藍E方塊，我們可以解一下藍S方塊。

留意藍S方塊的右邊只能是藍S或藍E方塊，但是藍S和藍E方塊左邊的R11C1都堵上了，所以藍S方塊的回路不能通過R11C12到達右邊方塊。

假設藍S右側方塊的R9C1有線段，該線段必須經過藍S方塊R9C12。藍E方塊的R9C1有線段，又位於所有藍S方塊右邊，我們可利用歸納法證明所有藍S方塊的R9C1和R9C12必須有線段：

• 基本情況：藍E方塊的R9C1有線段經過。
• 歸納：若某個藍S方塊的右側方塊的R9C1有線段經過，那麼這個藍S方塊的R9C12必須有線段連接，並能推理出這個方塊的R9C1也有線段經過。

因此，我們可以從右向左推斷出所有藍S方塊的R9C1和R9C12皆有線段經過。

我們亦可利用歸納法證明所有藍S方塊的R1C12必定塗黑。

• 基本情況：藍E方塊的R1C1沒有線段穿過左邊。
• 歸納：若某藍S方塊右側的R1C1沒有線段穿過左邊，那麼這個藍S方塊的R1C12必須塗黑，並能推理出這個方塊的R1C1沒有線段穿過左邊。

因此，我們可以從右向左推斷出所有藍S方塊的上層結構。

R5C6為黑塊會出現矛盾，因此R3C6才是黑塊。

藍S方塊的兩側有四個可能性。我們把線穿過R3的情況稱作A，穿過R7的情況稱作B，一共有四種情況。我們可發現兩側都是A時，藍S並沒有解。而剩下三種情況分別對應着藍S方塊的一個唯一解。

現在我們做一下紅色方塊。留意到所有藍色方塊左邊的R1和R11都堵上了，所以我們可以先堵上所有紅色方塊R1C12和R11C12。不過，考慮到 b = 1 的情況，我們先不在R9C12加線段。

我們可以再做一些簡單推理。

我們先看一下紅B方塊。留意下方的 <- 4 提示。R6C1、R6C3、R6C7必須塗黑，否則會出現矛盾。

R1C2不能塗黑，否則會出現矛盾。

此時，我們不妨考慮紅B方塊上面的方塊。R12C1必定為黑塊，所以回路必定穿過R11C1至R11C3。因此R12C3為黑塊，回路也無法從紅B方塊的R1C3進入上面的方塊。

R3C4為黑塊時會出現矛盾，所以R1C4必為黑塊。

R1C6、R5C6或R7C6為黑塊時會出現矛盾，所以R3C6必為黑塊。

R3C8為黑塊時會出現獨立閉環，所以R3C8不能是黑塊。

R6C11不能是黑塊，不然的話線會由R7C12向右延伸，但因為R9C12被堵住，藍色方塊的線不能從R9回到紅色方塊，產生矛盾。

考慮藍色的切面。由於不同行藍色方塊之間沒有聯繫，回路只能從紅色方塊的切面來往上下行。對於回路的任何切面，回路穿過切面的次數必為偶數。目前回路已經從R6C9和R6C11穿過下圖的切面。

如果回路再從R3C12通過切面就會變成奇數。因此，R3C12只能是黑塊。

考慮 b = 1 和 b >= 2 時R7C11的線的情況：當 b = 1時，右邊沒有方塊，所以線只能往下。當 b >= 2 時，線必須經過右邊的方塊，所以線只能往右穿過藍色方塊，然後再從R9C12回到紅色方塊。

R3C11的線不能往左，只能往上。

最後再推導一下就能完成這個小謎題。

我們發現，在 b = 1 和 b >= 2 兩個情況的解都是唯一的。現在我們可以以歸納的方法證明所有紅M、紅T方塊底邊都只有C7、C9與下方方塊連通。

假設紅M方塊底邊只有C7、C9與下方方塊連通，我們可以透過下圖的推理，證明該方塊頂邊亦只有C7、C9與上方方塊連通。

由於紅B的頂邊只有C7、C9與上方方塊聯通，我們可以由下而上逐個解出所有紅M方塊。紅T方塊亦可在得到「底邊只有C7、C9與下方方塊連通」的條件下唯一地解出，其解法和紅M類似。

到現在，我們已經解完所有的方塊了。我們發現紅色方塊在任何情況下均只有唯一解，而藍色方塊則有多解。

我們先看一下回路的形狀。回路從 (1,1) 出發，透過C11往下經過 B ，穿過 (1, 2) 至 (1, b)，然後經下面R9-11的小路回到 (1, 1)的左下角入口。回路接着繼續往下前往 (2, 1)，經過 B 穿過藍色方塊(2, 2) 至 (2, b)，再沿下方通路回到(2,1)。然後，回路往下重複，直到穿過(a, 2) 至 (a, b)後回到 (a, 1)， 最後往上回到 (1, 1)的起點。

由上述結果可知：

• 藍色方塊的答案必須和左右兩邊的方塊連得起來。假如藍E方塊左邊的藍S方塊的答案是 B->A ，那麼藍E方塊的答案只能是 A。最左邊的藍S方塊和紅色方塊相連。由於紅色方塊只能從 B 連接藍S方塊，因此最左邊的藍S方塊的答案必然是 B -> A 或 B -> B。
• 不同行的藍色方塊之間的答案沒有關聯。紅色方塊僅有唯一解，而且對藍色方塊局部解的選擇只會改變該行的內部走向，不會影響回路穿過方塊的順序，亦不會形成額外的閉環。因此，不同行藍色方塊的答案不會互相影響，各行的解數也可以相乘。

我們可以利用以上幾點計算解的個數。

• 當 b = 1 ，由於沒有藍色方塊，因此整題只有一個解。
• 當 b >= 2 ，不同行的藍色方塊之間的答案沒有關聯，所以解的個數為 (單行解數)^行數。

我們先考慮只有一行時有多少個解。回路從 B 出發，穿過若干個藍S方塊，抵達藍E方塊。假如回路從 B 進入藍S方塊，我們可以選擇 B -> B 或 B -> A 這兩個路徑。不過如果回路從 A 進入藍S方塊，那麼我們只能選擇 A -> B 路徑。由於我們可以透過 A 或 B 進入藍E方塊，因此我們在選擇路徑時只需從左到右選擇，確保方塊與左邊的路徑吻合，解答便不會有矛盾。

我們可以用遞迴的方式計算解的個數。設從 A 進入，穿過n個S後抵達E的解數為 A_n；從 B 進入，穿過n個S後抵達E的解數為 B_n。

當 n = 0 時，藍E方塊在從A或B進入時各有唯一解，因此A_0 = B_0 = 1。

當 n >= 1 時：

• 假如我們從 A 出發。我們只能從 A -> B 穿過第一個方塊，然後有 B_{n-1}個方法穿過剩餘的n-1個方塊。因此，A_n = B_{n-1}。
• 假如我們從 B 出發。我們可以選擇以 B -> B 穿過第一個方塊，然後有 B_{n-1}個方法穿過剩餘的n-1個方塊；我們也可以選擇以 B -> A 穿過第一個方塊，然後有 A_{n-1}個方法穿過剩餘的n-1個方塊。因此，B_n = A_{n-1} + B_{n-1}。

另外，當 n >= 2時，我們可以得出 B_n = A_{n-1} + B_{n-1} = B_{n-2} + B_{n-1}。其中，B_{0} = 1，B_{1} = A_0 + B_0 = 2。因此，B_n = F_{n+2}，其中 F_1 = F_2 = 1。

當大謎題由a行、b列的方塊組成時，每行需要從 B 出發，穿過b-2個藍S方塊。一行一共有 B_{b-2} = F_b個解，因此整個謎題一共有 F_b^a 個解。另外，b = 1時大盤面只有紅色方塊。紅色方塊僅有唯一解，因此 s(a, 1) = 1 = F_1^a，這條公式同樣適用。

因此，s(a,b) = F_b^a。

現在我們終於可以計算下方的算式。

前面六組算式比較簡單~~，甚至可以說是完全沒用~~。算完後用A1Z26可得到 ANSWER。

後面的算式涉及到了極限的概念，需要知道當 n 趨向無限大時， F_{n+1}/F_{n} 趨向黃金比率 φ。此外，也會用到黃金比率 φ的定義，以及卡西尼恆等式（Cassini’s Identity）等和費波那契數相關的公式。

算完後，把所得數字由右至左每兩位一組，然後以A1Z26轉換，可得到 APOCALYPSE，即本題答案。

後記：本人看到謎面的第一反應是「丟給隊友做」，然後就去做其他題了，過了整整一天半後沒人動過這道題，就只能親自把它解了。在做題的時候為了確保公式正確，我開了 (1, 4) 和 (3, 1)的提示。後來我在完賽後看了一下速通榜，才發現最快的隊伍只用了十分鐘就做出來了……