本文討論如何判斷拼圖游戲中圖形是否可以還原。

例1：下圖是一個(gè)3X3的數(shù)字拼圖。

圖1

它要還原成圖2

圖2

      將問題一般化，在M*N的方格里有M*N-1個(gè)不同元素和一個(gè)空元素，只有空元素可以與上下左右相鄰的元素交換位置。M*N方格中M*N-1個(gè)元素和一個(gè)空元素的位置確定一個(gè)圖形。拼圖游戲的問題是：一個(gè)圖形經(jīng)過一連串的交換能否得到另一個(gè)圖形，如何得到。從交換方式的可逆性看出這種關(guān)系滿足等價(jià)三性質(zhì)，如果圖形A通過交換變成圖形B我們則稱它們是等價(jià)的。把M*N-1個(gè)元素用1至M*N-1編號(hào)，空元素編號(hào)0。然后展成一個(gè)排列。每個(gè)圖形對(duì)應(yīng)一個(gè)排列。確定了展開方式，圖形和排列是一一對(duì)應(yīng)的。這里用到的展開方式是行優(yōu)先的順序（其他方式展開也能到相應(yīng)的結(jié)果）。將例1的兩個(gè)圖形展開有：圖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)的奇偶性稱為圖形的奇偶性。

      先看定理1如何起作用，圖1：展開的排列 1 3 2 6 0 5 4 7 8，它的逆序數(shù)為8，0元素行號(hào)為2，列號(hào)為2。逆序數(shù)加行號(hào)，列號(hào)的奇偶性為偶。圖2：展開的排列 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)之和的奇偶性也改變一次。這說明拼圖的交換方式不改變圖形的奇偶性，也說明拼圖中至少有兩組等價(jià)類，奇偶性不同的圖形不等價(jià)。

      下面證明充分性，如果圖形A的奇偶性等于圖形B的奇偶性，則圖形A，B等價(jià)。

      如果證明了拼圖只有兩組等價(jià)類，從必要性的證明過程可知，奇性圖形是一組等價(jià)類，偶性是一組。從而證明了充分性。

      先考慮一般的排列1 2 3 ... N。某個(gè)元素連續(xù)與后面M相鄰的元素交換位置，稱為向后M步移動(dòng)。如排列：1 2 3 4 5 6。元素2的向后3步移動(dòng)，排列變成1 3 4 5 2 6。同樣的方式定義向前M步移動(dòng)。如果排列A能夠通過有限向前M步移動(dòng)和向后M步移動(dòng)變成排列B，稱排列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à)類。由于移動(dòng)不改變排列的奇偶性，從而奇排列是一組等價(jià)類，偶排列是一組等價(jià)類。

考慮N*M的拼圖。
當(dāng)N=M=2，窮舉法可證明只有兩組等價(jià)類。

當(dāng)N，M不同時(shí)為2時(shí)，設(shè)N不等于2（如果N等于2，M不等于2可顛倒行列討論）。

只考慮第二行最后一個(gè)元素是空元素的情形，因?yàn)榭赵卦谄渌?/span>位置總可以等價(jià)某個(gè)空元素在第二行最后一個(gè)元素的圖形。不考慮空元素以之字形方式展開圖形，即第一行最后一個(gè)數(shù)字和第二行倒數(shù)第二個(gè)數(shù)字相連。如：

圖3

展開成1，2，4，5，3。

下面證明兩行拼圖的交換方式可以實(shí)現(xiàn)排列的向前2步和向后2步移動(dòng)。

要實(shí)現(xiàn)元素a的向前2步移動(dòng)，則可順著展開的方式循環(huán)移動(dòng)拼圖，使a在第一行第二列的位置，使空元素在第二行第二列的位置，此時(shí)可把元素i可與空元素對(duì)換。然后再沿著展開的順序還原拼圖。

例如：圖3的元素4向前2步移動(dòng)?？梢匀缦虏僮?，

圖4

圖5

圖6

展開成4，1，2，5，3。實(shí)現(xiàn)了向前2步移動(dòng)。

使i在第二行第二列的位置，使空元素在第一行第二列的位置可以實(shí)現(xiàn)向后2步移動(dòng)。根據(jù)引理1及，兩行拼圖可以分成兩組等價(jià)類。

假設(shè)M=k圖形可以分成兩組等價(jià)類，下面證明M=k+1，

只需要證明任何M=k+1圖形總等價(jià)于第一行元素為1 2 ... N的某圖形即可。

如果這N個(gè)元素都在第一行，把空元素移到第二行，從上面的證明可知，交換兩個(gè)不同的非空元素，圖形的奇偶性改變，屬于不同的等價(jià)類。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à)類數(shù)目為2。

充分性得證。

      拼圖游戲的隨機(jī)離散中加入定理1的判斷可以保證游戲有意義，不會(huì)出現(xiàn)無解的情況。

附：     windows控制臺(tái)下的數(shù)字拼圖游戲，用dev c++編譯通過。