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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

沒錯，這就是一句廢話。我們還是來看一個例子吧。

在 2 7 8 1 3 這個排列中，如果 標(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個，因此這個排列的逆序數(shù)就為 5 。

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

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

Q2：什么是元素對換？

Q3：定理1證明？

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

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

首先，我們把這個棋盤按行拉長成一個隊(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é)的知識，s1的逆序數(shù)為： (15, 13) , (15, 14) , (15, 12) , (13, 12) , (14, 12) ，共5個。而s0的逆序數(shù)為0個。

是時候甩出我們的華容道定理了。

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

下面我們來證明一下這個定理是錯誤的。 【接受反駁】

證明：

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

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

一句話證明：

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

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

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

得證。