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

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

為了檢驗自我的智商是否一下跌落到倔強青銅，我堅定地戳開了華容道小程序，準備接受知識的洗禮。

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

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

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

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

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

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

我的不知道嚴不嚴謹的證明是：逆向思維。即證明從圖2的原始狀態(tài)是無法通過上下左右平移到達圖1的狀態(tài)的。

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

如圖3所示，空格以 0 表示，在這個2x2的方塊內，我們從原始狀態(tài)出發(fā)，經過多次平移， 11 12 15 這三個數字只可能出現如下幾種排列方式。因為不論怎么移動，這四個格子都相當于做了順時針或逆時針的旋轉，而不可能出現圖1中 12 和 15 兩兩交換的局面。

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

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

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

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

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

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

不過我相信，通過我下面的淺顯易懂的解讀之后，你會在半分鐘之內決定關掉這個網頁。

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

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

在 2 7 8 1 3 這個排列中，如果 標準次序 是從小到大的話，那么逆序對有： (2, 7) , (2, 8) , (2, 1) , (2, 3) , (7, 8) , (7, 1) , (7, 3) , (8, 1) , (8, 3) , (1, 3) ，共5個，因此這個排列的逆序數就為 5 。

如果你堅持過了半分鐘，到了這，恭喜你，你已經知道了逆序數是啥了。不如再堅持半分鐘，來看一下神奇的逆序數定理。

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

Q2：什么是元素對換？

Q3：定理1證明？

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

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

首先，我們把這個棋盤按行拉長成一個隊列：

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

空格用 16 表示。

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

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

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

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

這是網上很多人提的一個證明思路。

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

證明：

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

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

一句話證明：

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

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

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

得證。