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

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

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

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

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

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

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

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

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

這也就是說 3-SAT 公式可滿足的充分必要條件是對應(yīng)的羊了個羊游戲?qū)嵗赏P(guān)。而羊了個羊顯然屬于 NP，因?yàn)槟茉诙囗検綍r間內(nèi)判定一個操作序列是否能消去所有方塊，從而我們就證明了下面的命題：

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

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