本文送給欠我100元的某小三。
1. Intro
最近華容道很火灶搜，可惜曹操去世得早祟蚀，不然也能蹭個(gè)何猷君的熱搜。最近同樣很火的游戲割卖，還有一個(gè)頭腦王者前酿，可惜前幾天由于未可知的原因被封了。
離開(kāi)了頭腦王者的我鹏溯，就像高考前遇到車(chē)禍的考生罢维。
為了檢驗(yàn)自我的智商是否一下跌落到倔強(qiáng)青銅，我堅(jiān)定地戳開(kāi)了華容道小程序丙挽，準(zhǔn)備接受知識(shí)的洗禮肺孵。
可誰(shuí)能想到，我第一道題颜阐，就遇到了滑鐵盧平窘。
棋盤(pán)到達(dá)圖1這個(gè)狀態(tài)之后，我又瞎戳了個(gè)三五分鐘凳怨，仍是無(wú)解瑰艘。
出于程序員的自我修養(yǎng)，我開(kāi)始考慮肤舞，這會(huì)不會(huì)是小程序的bug紫新？
也就是說(shuō)，編寫(xiě)小程序的人并不是從棋盤(pán)原始狀態(tài)（圖2）出發(fā)李剖，按上下左右移動(dòng)的規(guī)則打亂棋盤(pán)芒率，而是 瞎幾把 隨機(jī)初始化棋盤(pán)？
為了證明我的猜想篙顺，我去洗了個(gè)頭偶芍，接著開(kāi)啟了頭腦風(fēng)暴充择。
2. 隨意證明一發(fā)
要如何證明圖1狀態(tài)的華容道是無(wú)解的？
我的不知道嚴(yán)不嚴(yán)謹(jǐn)?shù)淖C明是：逆向思維腋寨。即證明從圖2的原始狀態(tài)是無(wú)法通過(guò)上下左右平移到達(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)過(guò)多次平移凤类，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é)的觀(guān)念履肃，我提出了牛寶寶猜想：即，當(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í)力，我打開(kāi)了萬(wàn)能的谷歌埋合，準(zhǔn)備抄抄別人的答案备徐。奇妙的是，關(guān)于這個(gè)問(wèn)題竟然只有一些只言片語(yǔ)的解讀甚颂。最終蜜猾，經(jīng)過(guò)我的不懈努力秀菱，終于讓我catch到了一個(gè)關(guān)鍵字：逆序數(shù)。
3. 從逆序數(shù)的角度證明無(wú)解性
3.1 逆序數(shù)
逆序數(shù)是什么蹭睡？我相信大家和我一樣衍菱，是懵逼的。
不過(guò)我相信肩豁，通過(guò)我下面的淺顯易懂的解讀之后脊串，你會(huì)在半分鐘之內(nèi)決定關(guān)掉這個(gè)網(wǎng)頁(yè)。
逆序數(shù)是什么清钥，我相信任何一個(gè)修過(guò)線(xiàn)性代數(shù)琼锋，學(xué)過(guò)行列式的人，都不會(huì)記得的祟昭。像我就不記得逆序數(shù)就是一個(gè)排列中所有逆序的總數(shù)缕坎。
沒(méi)錯(cuò)，這就是一句廢話(huà)篡悟。我們還是來(lái)看一個(gè)例子吧谜叹。
逆序數(shù)計(jì)算
在2 7 8 1 3這個(gè)排列中，如果標(biāo)準(zhǔn)次序是從小到大的話(huà)搬葬，那么逆序?qū)τ校?del>(2, 7), (2, 8)(2, 1), (2, 3)(7, 8)(7, 1), (7, 3), (8, 1), (8, 3), (1, 3)5踩萎。
如果你堅(jiān)持過(guò)了半分鐘停局，到了這，恭喜你香府，你已經(jīng)知道了逆序數(shù)是啥了董栽。不如再堅(jiān)持半分鐘，來(lái)看一下神奇的逆序數(shù)定理企孩。
逆序數(shù)定理
逆序數(shù)定理1：一個(gè)排列中的任意兩個(gè)元素對(duì)換锭碳，排列的奇偶性會(huì)改變。
Q1：什么是排列的奇偶性勿璃？
- 逆序數(shù)為奇數(shù)的排列稱(chēng)為奇排列擒抛；
- 逆序數(shù)為偶數(shù)的排列稱(chēng)為偶排列；
Q2：什么是元素對(duì)換补疑？
- 在排列中歧沪，將任意兩個(gè)元素對(duì)調(diào)，其余元素不變的操作莲组，叫做元素對(duì)換诊胞；
- 將相鄰兩個(gè)元素對(duì)換，叫做相鄰對(duì)換锹杈；
Q3：定理1證明撵孤？
我估計(jì)你們也不想看迈着，有興趣的自己戳鏈接：證明
3.2 逆序數(shù)證明無(wú)解性
再貼一下圖，我們要證明的是下面這個(gè)狀態(tài)的華容道是無(wú)解的邪码。怎么利用逆序數(shù)定理來(lái)證明呢裕菠？
首先，我們把這個(gè)棋盤(pán)按行拉長(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。
把它們兩都看成排列的話(huà)喻圃，利用我們剛剛學(xué)的知識(shí)萤彩，s1的逆序數(shù)為：(15, 13), (15, 14), (15, 12), (13, 12), (14, 12)粪滤，共5個(gè)斧拍。而s0的逆序數(shù)為0個(gè)。
是時(shí)候甩出我們的華容道定理了杖小。
華容道定理第一彈
華容道定理1：按照游戲規(guī)則移動(dòng)方塊不會(huì)改變排列的逆序數(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ā)生改變鳖擒。
華容道定理第二彈
華容道定理2：若某狀態(tài)的排列的逆序數(shù)加上空格元素行號(hào)和列號(hào)的奇偶性 ≠ 原始狀態(tài)的排列的逆序數(shù)加上空格元素行號(hào)和列號(hào)的奇偶性溉浙，則該狀態(tài)是無(wú)解的。
一句話(huà)證明：
空格元素和某個(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ú)解的啦坛猪。
得證。
