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