拼圖游戲的初始化算法及證明

1、例1：下圖是一個3X3的數(shù)字拼圖。13265478圖1它要還原成圖212345678圖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)先的順序（其他方

2、式展開也能到相應(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。逆

3、序數(shù)加行號，列號的奇偶性為偶。兩個圖形的奇偶性相同，根據(jù)定理1判斷它們等價。首先證明必要性，即如果圖形A與圖形B等價，則圖形A的奇偶性等于圖形B奇偶性。0元素和某個元素交換位置，則排列的逆序數(shù)的奇偶性就改變一次。交換后0元素的行號或者列號會加1或減1，即行號，列號之和的奇偶性也改變一次。這說明拼圖的交換方式不改變圖形的奇偶性，也說明拼圖中至少有兩組等價類，奇偶性不同的圖形不等價。下面證明充分性，如果圖形A的奇偶性等于圖形B的奇偶性，則圖形A，B等價。如果證明了拼圖只有兩組等價類，從必要性的證明過程可知，奇性圖形是一組等價類，偶性是一組。從而證明了充分性。先考慮一般的排列1 2 3 . N。某個

4、元素連續(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：如果1iM，則元素1有限次向前M步移動，使i有1=i=M，

5、可變成情況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可顛倒行列討論）。只考慮第二行最后一個元素是空元素的情形，因為空元素在其他位置總可以等價某個空元素在第二行最后一個元素的圖形。不考慮空元素以之字形方式展開圖形，即第一行最后一個數(shù)字和第二行倒數(shù)第二個數(shù)字相連。如：12435圖3展開成1，2，4，5，3。下面證明兩行拼圖的交換方式可以實現(xiàn)排列的向前2步和向后2步移動。要實現(xiàn)元素a的向前2步移動，則可順著

6、展開的方式循環(huán)移動拼圖，使a在第一行第二列的位置，使空元素在第二行第二列的位置，此時可把元素i可與空元素對換。然后再沿著展開的順序還原拼圖。例如：圖3的元素4向前2步移動。可以如下操作，24513圖425143圖541235圖6展開成4，1，2，5，3。實現(xiàn)了向前2步移動。使i在第二行第二列的位置，使空元素在第一行第二列的位置可以實現(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的圖形。可以把a(bǔ)移動到第i-1行，并保證第i