近日，羊了個羊火遍了網絡，一時間關于第二關怎樣難、如何通關的文章也多了起來，但是從計算復雜性（computational complexity）的角度討論游戲難度的文章應該還沒有，所以這次我也寫一篇關于計算復雜性的文章來碰瓷。

游戲的機制是比較簡單的，簡單說來就是地圖上有一些不同類型的方塊，玩家可以選擇方塊放入自己的槽位中（槽位有上限，是個常數），如果槽位中有三個相同類型的方塊就消去，游戲目標是消去所有方塊。游戲的難點在于地圖上的方塊是堆疊起來的，被疊在下方的方塊不能被選擇，只有在上方的方塊被放入槽位后才能被選擇（也就是解鎖），有時被疊在下方的方塊的類型都由于被遮擋而不可知。

事實上，羊了個羊與有些小游戲的機制很類似，而其中很多小游戲已經被證明是 NP-complete 的，所以我們比較確信也能證明推廣了的羊了個羊是 NP-complete 的。這里我們給一個比較弱的、簡單的歸約構造，來說明推廣的羊了個羊游戲是 NP-complete。這里我們說的推廣是指方塊類型的數量不限制于常數，被遮擋的方塊類型是確定的且已知的，槽位數量固定為 3（槽位數量是其他常數也可以用類似方法，只要在游戲初期迫使玩家拿一個特殊類型的方塊，而在游戲最后才能消去，整個過程中這個方塊占用了一個槽位，相當于少了一個槽位）。當然，這里我們不考慮游戲道具的影響。

本文的歸約主要抄襲的是 Computational Complexity of Games and Puzzles 網頁上證明 Mah-Jongg 游戲（一個類似連連看的游戲，有的地方也叫麻將）是 NP-complete 的歸約。

我們仍然使用 3-SAT 這個經典的 NP-complete 問題作為歸約問題。我們對于 3-SAT 公式中的每個變量設置 3 個方塊堆，一個方塊堆用于模擬變量的賦值（TRUE or FALSE），一個方塊堆對應于賦值為 FALSE，一個堆對應于賦值為 TRUE。模擬變量的賦值方塊堆有兩層，第一層是 4 個一樣的對應于變量的方塊，第二層包含變量被賦值為 TRUE 和 FALSE 的方塊各一個以及填充方塊。對應于賦值為 FALSE 的方塊堆通常是多層的（也可能退化為一層），頂層包含兩個對應于變量被賦值為 FALSE 的方塊（用于配合之前賦值方塊堆使用），下層包含對應于子句的方塊（對應子句中變量以非的形式出現）以及填充方塊。對應于賦值為 TRUE 的方塊堆的結構是類似的。最后，還有一個用于驗證解的方塊堆，這個堆是多層結構，頂部包含了對應于子句的方塊，中部是對應于變量的方塊，底部是對應于子句的方塊。

我們用一個具體的例子來描述這個歸約，假設 3-SAT 的實例是。那么對于的羊了個羊游戲的實例如下（為了能表述每個方塊的類型和堆疊情況，我們使用側面視圖的方式展示）

其中 C1 表示，C2 表示，a 是填充方塊，a 方塊沒有壓住任何方塊，所以可以留到最后再全部消去而不影響其他方塊。注意這里我們設置的槽位數量是 3，也就是說選擇某個方塊放入槽里后就必須要消除這個類型的方塊，否則就無法繼續游戲了。

如果公式可滿足，那么可以按照滿足時各變量的賦值來消除方塊。比如假設 xyz 全賦值為 FALSE，那么我們就對應消除最左側的三個 x y 和 z，這樣一來，第二層的方塊 x=F y=F 和 z=F 就被解鎖，我們就可以消去所有 x=F y=F z=F 方塊，接著一個 C1 方塊和兩個 C2 方塊就解鎖，然后就能配合最下方的驗證方塊堆，消去驗證堆的頂部兩層，而后中間的變量 xyz 方塊也馬上能消去，最后就沒有什么限制了，所有的方塊都能夠被消去。

反過來，如果所有方塊可以消去（也就是該關卡可以通關），那么公式可滿足。注意到驗證堆中的變量 xyz 的方塊想要被消去，必須上部的 C1 C2 子句方塊都先消去，而子句方塊又受限于賦值方塊，賦值方塊受限于變量方塊，變量方塊的擺放方式決定了在變量賦值時，每個變量只能賦為 FALSE 或 TRUE 中的一個（具體來說，在游戲初期 4 個 x 方塊中任意消去 3 個后，方塊 x=F 和 x=T 中必然有一個未被解鎖）。這就意味著方塊消去的順序蘊含了一個滿足公式的賦值。

這也就是說 3-SAT 公式可滿足的充分必要條件是對應的羊了個羊游戲實例可通關。而羊了個羊顯然屬于 NP，因為能在多項式時間內判定一個操作序列是否能消去所有方塊，從而我們就證明了下面的命題：

命題：在所有被遮擋的方塊類型是確定且已知的條件下，推廣的羊了個羊游戲屬于 NP-complete。

用非人話來說就是，你沒有辦法設計一個多項式時間復雜度的算法來判斷任意推廣的羊了個羊關卡是否有解，除非 P=NP （這個只有 4 個字符的等式價值一個土地獎和 100 萬美元，所以別去閑著沒事就想著嘗試證明或證否）。用人話來說就是，即使被遮擋的方塊類型是確定的且已知的，計算機也仍然（幾乎）無法快速地判斷羊了個羊是否能通關。