前言：最近在學(xué)習(xí)mathematics for computer science, 聽課中思考了這樣一道有趣的問題：數(shù)字/字母華容道的可解性。若要Google搜索，可以搜索"solubility of the pile puzzle"或者是"solubility of the sixteen puzzle"。其實(shí)這個問題早已被研究透徹，但我看了很多文章，解釋地十分繁瑣甚至有錯誤的地方，所以在此做一個清晰簡明的總結(jié)（所用知識都是大家能看明白的）。

一、所用知識（如果有大佬能從抽象代數(shù)的角度解釋就更好了）：

1.不變式（invariant）的思想：在研究一些問題時，我們可以從一個事物一直不變的性質(zhì)/狀態(tài)入手。例如我們要證明以下的數(shù)字華容道不可解：

看起來似乎無從下手，那么我們能不能從中找到什么不變的性質(zhì)呢？首先我們可以想這個游戲是每次將數(shù)字進(jìn)行上下左右移動，那么每次移動改變了什么呢？又有什么沒變呢？

也許你還是一頭霧水，但確實(shí)有不變的東西：我們發(fā)現(xiàn)完成好的數(shù)字/字母華容道，它的逆序是0（逆序會在下面講到），而現(xiàn)在這個華容道的逆序數(shù)是1，而我們每次左右移動并不改變逆序數(shù)，上下移動改變逆序數(shù)的數(shù)目是0或2，所以無論我們移動多少次，都無法將逆序數(shù)為1的華容道變成逆序數(shù)為偶數(shù)/0的華容道（奇數(shù)+偶數(shù)=奇數(shù)）。若你對此還是有點(diǎn)難以理解，更加詳細(xì)的講解可以觀看AV46506390的p3。

2.逆序數(shù)（線性代數(shù)里的概念）

在一個排列中，如果一對數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個逆序。 一個排列中逆序的總數(shù)就稱為這個排列的逆序數(shù)。舉個例子：

在（1，2，4，6，3，5，7，8）中，（4，3），（6，3）（6，5）都為逆序，該排列的逆序數(shù)為3。

而華容道可以以行的順序?qū)懗梢粋€排列，（空著的那一格是不算的），所以上面的華容道逆序數(shù)為1（（8，7）這一個逆序），而最終排好的華容道逆序數(shù)為0。

PS：我們將華容道復(fù)原專指所有數(shù)字/字母按順序排列，將空格放在從上往下，從左往右數(shù)的最后一格。

二、數(shù)字/字母華容道一般情況的可解性

上面以3x3為例子，說明了3x3數(shù)字/字母華容道的可解性，我們可以合理推論得到（下面會作證明）：

對于n x n（n為奇數(shù)）的數(shù)字/字母華容道：其初始情況的逆序數(shù)須為偶數(shù)，該華容道可解。

那么對于n為偶數(shù)的呢？哈哈哈，是不是有點(diǎn)復(fù)雜了？其實(shí)并不（雖然我考慮偶數(shù)的情況時也想了很久，頭發(fā)抓掉了不少），另外很多文章也是根據(jù)n=奇偶的情況去考慮，并且跳躍地給出了??（??指空的那一格）與逆序數(shù)的關(guān)系來判斷可解性（簡直坑爹，mmp）。

下面我們直接來看一般情況：其中??指的是空的那一格。

n x n的數(shù)字/字母華容道中，有（n^2-1）個數(shù)字，記該華容道初始狀態(tài)的逆序數(shù)為Q，??所在行數(shù)為R。除了??所在的這一行，其他的一行有n個數(shù)字。

如圖，若將該華容道想像成i 一個排列，若將b移動到??所在的位置，則把b向后移動了n-1位。因為原先排列是（·····a,b,c,······，d,e,······，f,g,h,·······）

現(xiàn)在排列變?yōu)椋āぁぁぁぁぁぁ,c,·····，d,b,e,·······，f,g,h,······），c，d之間有n-3個元素，b移動的位數(shù)應(yīng)表示為1+n-3+1（兩個1分別表示c，d），故b向后移動了n-1位。換言之，??在華容道中上/下移動了n-1位（這個非常重要，一定要理解?。?！

引理一：

對于一個排列，某元素向前/向后移動1位，該排列的逆序數(shù)就會增加/減少1，即該排列的逆序數(shù)的奇偶性會發(fā)生一次改變。

引理二：

在華容道中，左右移動并不改變排列的逆序數(shù)。

結(jié)論：

當(dāng)n為奇數(shù)時（如3x3，5x5這類），n-1為偶數(shù)，也就是說，??的上下移動不會改變排列逆序數(shù)的奇偶性，因此想要將一個華容道復(fù)原，其初始狀態(tài)的逆序數(shù)必須為偶數(shù)。

當(dāng)n為偶數(shù)時，n-1為奇數(shù)，每次上下移動都會改變排列逆序數(shù)的奇偶性，而如果我們要能復(fù)原偶數(shù)型nxn的華容道，那么最終??位于最后一格，而??位于第R行，移動到最后一行需要上下移動T=（n-R+2k）次，因為不可能一直下移，所以不是n-R次，但如果有上移操作，那么要回到原來的位置，對應(yīng)地需要一次下移，所以上移下移的操作一定是偶數(shù)次，故用2k來表示。

可以看出T的奇偶性由R決定，故要能復(fù)原n為偶數(shù)的華容道，其初始狀態(tài)逆序數(shù)的奇偶性要和R相同（因為奇數(shù)+奇數(shù)=偶數(shù)，偶數(shù)+偶數(shù)=偶數(shù)）

那么這時有人會問，當(dāng)n為奇數(shù)時，??也要到最后一格，那不是也滿足T的表達(dá)式嗎？如果這樣，好像和n為偶數(shù)一樣了誒。確實(shí)如此（指前面那句話），但n為奇為偶最重要的是上下移動到底會不會改變逆序數(shù)的奇偶性，n為奇數(shù)時，上下左右移動并不會改變排列逆序數(shù)的奇偶性，所以我們并沒有討論??的位置對可解性的影響。

如果還想了解更多，可以去閱讀《N數(shù)碼問題直接解及優(yōu)化研究》，《抽象代數(shù)基礎(chǔ)教程》這些材料，如果只是單單想了解可解性，我的這篇專欄應(yīng)該寫得足夠清楚明白了??