最近華容道很火，可惜曹操去世得早，不然也能蹭個(gè)何猷君的熱搜。最近同樣很火的游戲，還有一個(gè)頭腦王者，可惜前幾天由于未可知的原因被封了。

離開了頭腦王者的我，就像高考前遇到車禍的考生。

為了檢驗(yàn)自我的智商是否一下跌落到倔強(qiáng)青銅，我堅(jiān)定地戳開了華容道小程序，準(zhǔn)備接受知識(shí)的洗禮。

可誰(shuí)能想到，我第一道題，就遇到了滑鐵盧。

棋盤到達(dá)圖1這個(gè)狀態(tài)之后，我又瞎戳了個(gè)三五分鐘，仍是無(wú)解。

出于程序員的自我修養(yǎng)，我開始考慮，這會(huì)不會(huì)是小程序的bug？

也就是說(shuō)，編寫小程序的人并不是從棋盤原始狀態(tài)（圖2）出發(fā)，按上下左右移動(dòng)的規(guī)則打亂棋盤，而是 瞎幾把 隨機(jī)初始化棋盤？

為了證明我的猜想，我去洗了個(gè)頭，接著開啟了頭腦風(fēng)暴。

要如何證明圖1狀態(tài)的華容道是無(wú)解的？

我的不知道嚴(yán)不嚴(yán)謹(jǐn)?shù)淖C明是：逆向思維。即證明從圖2的原始狀態(tài)是無(wú)法通過上下左右平移到達(dá)圖1的狀態(tài)的。

當(dāng) 1 2 3 4 5 6 7 8 9 10 13 14 這幾個(gè)數(shù)字都各就各位之后，我們只需要關(guān)注右下角的2x2的4個(gè)方格。

如圖3所示，空格以 0 表示，在這個(gè)2x2的方塊內(nèi)，我們從原始狀態(tài)出發(fā)，經(jīng)過多次平移， 11 12 15 這三個(gè)數(shù)字只可能出現(xiàn)如下幾種排列方式。因?yàn)椴徽撛趺匆苿?dòng)，這四個(gè)格子都相當(dāng)于做了順時(shí)針或逆時(shí)針的旋轉(zhuǎn)，而不可能出現(xiàn)圖1中 12 和 15 兩兩交換的局面。

但是我這個(gè)糙證明被不愿意透露姓名的小三同學(xué)否定了，原因是 11 12 15 可以借助其他位置（如 10 14 7 8 ）改變順序。

為了反駁這位同學(xué)的觀念，我提出了牛寶寶猜想：即，當(dāng)除右下角的2x2方格以外的所有數(shù)字都?xì)w位時(shí)，該2x2方格中的數(shù)字只能有圖3中的幾種狀態(tài)；換言之，如果該2x2方格中出現(xiàn)了其他狀態(tài)，則 1 2 3 4 5 6 7 8 9 10 13 14 這幾個(gè)數(shù)字的位置必然是打亂的。

然而，由于缺乏強(qiáng)大的理論支撐，證明陷入僵局。

可是，作為圖靈的后人，怎么能被這點(diǎn)困難打倒呢？這豈不是告訴世人，我就是倔強(qiáng)青銅，倔強(qiáng)青銅就是我。

為了證明我王者的實(shí)力，我打開了萬(wàn)能的谷歌，準(zhǔn)備抄抄別人的答案。奇妙的是，關(guān)于這個(gè)問題竟然只有一些只言片語(yǔ)的解讀。最終，經(jīng)過我的不懈努力，終于讓我catch到了一個(gè)關(guān)鍵字：逆序數(shù)。

逆序數(shù)是什么？我相信大家和我一樣，是懵逼的。

不過我相信，通過我下面的淺顯易懂的解讀之后，你會(huì)在半分鐘之內(nèi)決定關(guān)掉這個(gè)網(wǎng)頁(yè)。

逆序數(shù)是什么，我相信任何一個(gè)修過線性代數(shù)，學(xué)過行列式的人，都不會(huì)記得的。像我就不記得 逆序數(shù)就是一個(gè)排列中所有逆序的總數(shù) 。

沒錯(cuò)，這就是一句廢話。我們還是來(lái)看一個(gè)例子吧。

在 2 7 8 1 3 這個(gè)排列中，如果 標(biāo)準(zhǔn)次序 是從小到大的話，那么逆序?qū)τ校? (2, 7) , (2, 8) , (2, 1) , (2, 3) , (7, 8) , (7, 1) , (7, 3) , (8, 1) , (8, 3) , (1, 3) ，共5個(gè)，因此這個(gè)排列的逆序數(shù)就為 5 。

如果你堅(jiān)持過了半分鐘，到了這，恭喜你，你已經(jīng)知道了逆序數(shù)是啥了。不如再堅(jiān)持半分鐘，來(lái)看一下神奇的逆序數(shù)定理。

Q1：什么是排列的奇偶性？

Q2：什么是元素對(duì)換？

Q3：定理1證明？

我估計(jì)你們也不想看，有興趣的自己戳鏈接： 證明

再貼一下圖，我們要證明的是下面這個(gè)狀態(tài)的華容道是無(wú)解的。怎么利用逆序數(shù)定理來(lái)證明呢？

首先，我們把這個(gè)棋盤按行拉長(zhǎng)成一個(gè)隊(duì)列：

s1 = 1 2 3 4 5 6 7 8 9 10 11 15 13 14 12 16

空格用 16 表示。

顯然 ，原始狀態(tài)的隊(duì)列為：

s0 = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 。

把它們兩都看成排列的話，利用我們剛剛學(xué)的知識(shí)，s1的逆序數(shù)為： (15, 13) , (15, 14) , (15, 12) , (13, 12) , (14, 12) ，共5個(gè)。而s0的逆序數(shù)為0個(gè)。

是時(shí)候甩出我們的華容道定理了。

這是網(wǎng)上很多人提的一個(gè)證明思路。

下面我們來(lái)證明一下這個(gè)定理是錯(cuò)誤的。 【接受反駁】

證明：

根據(jù)逆序數(shù)定理，上下平移或左右平移，相當(dāng)于交換了某個(gè)元素和空格元素的順序，排列奇偶性會(huì)發(fā)生改變。

比如將圖2原始狀態(tài)中的 12 向下移動(dòng)到 15 的右邊，則 s = 1 2 3 4 5 6 7 8 9 10 11 16 13 14 15 12 ，相當(dāng)于交換了 12 和 16 的位置，這時(shí)逆序數(shù)為7，而原始逆序數(shù)為0，奇偶性發(fā)生改變。

一句話證明：

空格元素和某個(gè)元素交換位置，則排列的逆序數(shù)的奇偶性就改變一次。交換后空格元素的行號(hào)或者列號(hào)會(huì)加1或減1，即行號(hào)，列號(hào)之和的奇偶性也改變一次。

還是以剛剛的 s = 1 2 3 4 5 6 7 8 9 10 11 16 13 14 15 12 為例，此時(shí)該排列的逆序數(shù)加上空格元素行號(hào)和列號(hào) = 7+3+4 = 14，仍為偶數(shù)。

而我們要證明無(wú)解的狀態(tài)（圖1）的排列 s' = 1 2 3 4 5 6 7 8 9 10 15 13 14 12 16 ，其逆序數(shù)加上空格元素行號(hào)和列號(hào) = 5+4+4 = 13，為奇數(shù)，很明顯，這是無(wú)解的啦。

得證。