本文討論如何判斷拼圖游戲中圖形是否可以還原。
例1：下圖是一個(gè)3X3的數(shù)字拼圖。
圖1
它要還原成圖2
圖2
將問(wèn)題一般化，在M*N的方格里有M*N-1個(gè)不同元素和一個(gè)空元素，只有空元素可以與上下左右相鄰的元素交換位置。M*N方格中M*N-1個(gè)元素和一個(gè)空元素的位置確定一個(gè)圖形。拼圖游戲的問(wèn)題是：一個(gè)圖形經(jīng)過(guò)一連串的交換能否得到另一個(gè)圖形，如何得到。從交換方式的可逆性看出這種關(guān)系滿足等價(jià)三性質(zhì)，如果圖形A通過(guò)交換變成圖形B我們則稱(chēng)它們是等價(jià)的。把M*N-1個(gè)元素用1至M*N-1編號(hào)，空元素編號(hào)0。然后展成一個(gè)排列。每個(gè)圖形對(duì)應(yīng)一個(gè)排列。確定了展開(kāi)方式，圖形和排列是一一對(duì)應(yīng)的。這里用到的展開(kāi)方式是行優(yōu)先的順序（其他方式展開(kāi)也能到相應(yīng)的結(jié)果）。將例1的兩個(gè)圖形展開(kāi)有：圖1對(duì)應(yīng)1 3 2 6 0 5 4 7 8，圖2對(duì)應(yīng)1 2 3 4 5 6 7 8 0。
定理1：圖形A與圖形B等價(jià)的充要條件圖形A的排列的逆序數(shù)加上0元素行號(hào)和列號(hào)的奇偶性等于圖形B的排列的逆序數(shù)加上0元素行號(hào)和列號(hào)的奇偶性。為方便表述，把圖形排列的逆序數(shù)加上0元素行號(hào)和列號(hào)的奇偶性稱(chēng)為圖形的奇偶性。
先看定理1如何起作用，圖1：展開(kāi)的排列 1 3 2 6 0 5 4 7 8，它的逆序數(shù)為8，0元素行號(hào)為2，列號(hào)為2。逆序數(shù)加行號(hào)，列號(hào)的奇偶性為偶。圖2：展開(kāi)的排列 1 2 3 4 5 6 7 8 0，它的逆序數(shù)為8，0元素行號(hào)為3，列號(hào)為3。逆序數(shù)加行號(hào)，列號(hào)的奇偶性為偶。兩個(gè)圖形的奇偶性相同，根據(jù)定理1判斷它們等價(jià)。
首先證明必要性，即如果圖形A與圖形B等價(jià)，則圖形A的奇偶性等于圖形B奇偶性。
0元素和某個(gè)元素交換位置，則排列的逆序數(shù)的奇偶性就改變一次。交換后0元素的行號(hào)或者列號(hào)會(huì)加1或減1，即行號(hào)，列號(hào)之和的奇偶性也改變一次。這說(shuō)明拼圖的交換方式不改變圖形的奇偶性，也說(shuō)明拼圖中至少有兩組等價(jià)類(lèi)，奇偶性不同的圖形不等價(jià)。
下面證明充分性，如果圖形A的奇偶性等于圖形B的奇偶性，則圖形A，B等價(jià)。
如果證明了拼圖只有兩組等價(jià)類(lèi)，從必要性的證明過(guò)程可知，奇性圖形是一組等價(jià)類(lèi)，偶性是一組。從而證明了充分性。
先考慮一般的排列1 2 3 ... N。某個(gè)元素連續(xù)與后面M相鄰的元素交換位置，稱(chēng)為向后M步移動(dòng)。如排列：1 2 3 4 5 6。元素2的向后3步移動(dòng)，排列變成1 3 4 5 2 6。同樣的方式定義向前M步移動(dòng)。如果排列A能夠通過(guò)有限向前M步移動(dòng)和向后M步移動(dòng)變成排列B，稱(chēng)排列A與排列B M步等價(jià)。容易看出這也是等價(jià)關(guān)系。
引理1：任何一個(gè)1至N的排列M步等價(jià)于1 2 ... N-M（...）。括號(hào)里是N-M+1至N的某個(gè)排列。
證明：如果N=M，這顯然成立。
假設(shè)N=k時(shí)成立，下面證明k+1的情況。
1元素的位置記為i
情況1：假設(shè)i=1，顯然，余下的元素減1，就變成N=k的境況，得證。
情況2：如果1<i<=M，則元素1前面的元素向后M步移動(dòng)，變?yōu)榍闆r1。
情況3：如果i>M，則元素1有限次向前M步移動(dòng)，使i有1<=i<=M，可變成情況1或2。
從而得證。
當(dāng)M=2時(shí)，只有兩組等價(jià)類(lèi)。由于移動(dòng)不改變排列的奇偶性，從而奇排列是一組等價(jià)類(lèi)，偶排列是一組等價(jià)類(lèi)。
考慮N*M的拼圖。
當(dāng)N=M=2，窮舉法可證明只有兩組等價(jià)類(lèi)。
當(dāng)N，M不同時(shí)為2時(shí)，設(shè)N不等于2（如果N等于2，M不等于2可顛倒行列討論）。
只考慮第二行最后一個(gè)元素是空元素的情形，因?yàn)榭赵卦谄渌?/span>位置總可以等價(jià)某個(gè)空元素在第二行最后一個(gè)元素的圖形。不考慮空元素以之字形方式展開(kāi)圖形，即第一行最后一個(gè)數(shù)字和第二行倒數(shù)第二個(gè)數(shù)字相連。如：
圖3
展開(kāi)成1，2，4，5，3。
下面證明兩行拼圖的交換方式可以實(shí)現(xiàn)排列的向前2步和向后2步移動(dòng)。
要實(shí)現(xiàn)元素a的向前2步移動(dòng)，則可順著展開(kāi)的方式循環(huán)移動(dòng)拼圖，使a在第一行第二列的位置，使空元素在第二行第二列的位置，此時(shí)可把元素i可與空元素對(duì)換。然后再沿著展開(kāi)的順序還原拼圖。
例如：圖3的元素4向前2步移動(dòng)。可以如下操作，
圖4
圖5
圖6
展開(kāi)成4，1，2，5，3。實(shí)現(xiàn)了向前2步移動(dòng)。
使i在第二行第二列的位置，使空元素在第一行第二列的位置可以實(shí)現(xiàn)向后2步移動(dòng)。根據(jù)引理1及，兩行拼圖可以分成兩組等價(jià)類(lèi)。
假設(shè)M=k圖形可以分成兩組等價(jià)類(lèi)，下面證明M=k+1，
只需要證明任何M=k+1圖形總等價(jià)于第一行元素為1 2 ... N的某圖形即可。
如果這N個(gè)元素都在第一行，把空元素移到第二行，從上面的證明可知，交換兩個(gè)不同的非空元素，圖形的奇偶性改變，屬于不同的等價(jià)類(lèi)。N大于2，第二行就有兩個(gè)非空元素可供交換。所以兩行圖形可以等價(jià)與第一行為1 2 ... N的某個(gè)圖形。
如果1至N的某個(gè)a元素不在第一行，設(shè)它在第i行。把空元素移動(dòng)到i行，這樣第i行和第i-1行可以看成M=2的圖形。可以把a移動(dòng)到第i-1行，并保證第i行和i-1行中1至N的元素的行號(hào)不增加。有限步移動(dòng)可以使1至N元素全部在第一行。
顯然M=k+1圖形的等價(jià)類(lèi)數(shù)目為2。
充分性得證。
拼圖游戲的隨機(jī)離散中加入定理1的判斷可以保證游戲有意義，不會(huì)出現(xiàn)無(wú)解的情況。
附： windows控制臺(tái)下的數(shù)字拼圖游戲，用dev c++編譯通過(guò)。