一、線性代數基礎知識
1、逆序的定義：
逆序是一個與排列相關的概念。
由自然數1，2…，n組成的不重複的每一種有确定次序的排列，稱為一個n級排列（簡稱為排列）；或者一般的，n個互不同元素排成一列稱為“一個n級排列”。例如，1234和4312都是4級排列，而24315是一個5級排列。
在一個n級排列中，如果一對數的前後位置與大小順序相反，即前面的數大于後面的數，那麼它們就稱為一個“逆序”。
一個排列中逆序的總數就稱為這個排列的逆序數。
逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。
如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。
再來一個定理：交換一個排列中的兩個數，則排列的奇偶性發生改變。
二、拼圖的數學定義
在m*n*p(m,n>2,p>=1)的方塊區域裡，所有的方格兩兩不同，其中有一個特殊的方格，稱為空穴，任何與之有鄰面(二維時隻須有鄰邊)的方塊均可與之互換位置(一次這樣的位置互換稱為一次操作，也稱為空穴的一次移動)。剛開始時随機産生雜亂的排列順序，要求經過一系列操作後形成要求的排列順序(目标排列)。
其實，拼圖問題可以轉化為這麼一個問題：“任意給一個數字矩陣，能否證明：經過無限次的交換，一定能到達目标矩陣或者經過無限的交換也不能實作目标矩陣？”。
三、定理
定理一：
圖形a與圖形b等價的充要條件圖形a的排列的逆序數加上0元素行号和列号的奇偶性等于圖形b的排列的逆序數加上0元素行号和列号的奇偶性。為友善表述，把圖形排列的逆序數加上0元素行号和列号的奇偶性稱為圖形的奇偶性。
定理二：
對于任意 m* n 的情況，任意兩個空穴在同一個位置且奇偶性相同的排列可以通過空穴移動互相轉化。
定理三、
對源狀态a與目标狀态b進行規範化，使得兩矩陣的元素0（此處的元素0就是空穴）的位置相同；記為新的源狀态a'與目标狀态b'；
若a'與b'的逆序對的奇偶性相同（即a'與b1的逆序對的奇偶性相同），則a'必定可能轉化為b',即a可以轉化到b;
若a'與b'的逆序對的奇偶性不同（即a'與b2的逆序對的奇偶性相同），則a'必定不可能轉化為b',即a不可以轉化到b;
小結：
其實：以上三個定理或者說是結論，說的都是一個事，隻是角度不同，三個定理的證明與叙述見下面的連結。
<a target="_blank" href="http://blog.renren.com/share/252407647/528277482">定理一的叙述及證明</a>
<a target="_blank" href="http://blog.csdn.net/ville_zeng/article/details/8878020">定理二的叙述及證明</a>
<a target="_blank" href="http://blog.csdn.net/tailzhou/article/details/3002442">定理三的叙述及證明</a>