不可還原的拼圖

在3*3或4*4數字中，有的拼圖拼到最後出現有1對板塊是對調的，怎么都還原不到完整的順序，這樣的拼圖其實是不可還原的拼圖。

基本介紹

• 中文名：不可還原的拼圖
• 類型：拼圖遊戲
• 方法：逐行或逐列還原
• 還原機率：二分之一的機率

不可還原的拼圖介紹

現在很多手機和電子詞典上都有這款遊戲，不知到大家在玩的時候有沒有發現有的拼圖怎么都還原不到完整的圖片（或數字順序），最終出現有1對板塊（兩個）是對調的，這個時候你可以停下來了，這不是你水平的問題，是遊戲設計者的過錯！很多遊戲設計者都是將板塊隨機打亂，實際上並不是所有隨機打亂之後都是可以還原的！確切的說，隨機打亂後，有是可以被還原的。詳細證明如下：

以3*3的九格為例，如下圖：

1	2	3
4	5	6
7	8

a圖

1	2	3
4	5	6
8	7

b圖

假設圖中的a是3*3數字拼圖示準的結果，則對於圖b的狀態是不可能變換成a的。證明起來需要用到高等代數裡逆序數的概念，具體的說是用到了一個簡單的定理。

定義：在一個1,2,...,n的排列中，如果一對數的前後位置與大小順序相反，即前面的數大於後面的數，那么它們就稱為一個逆序。一個排列中逆序的總數就稱為這個排列的逆序數。逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列。如2431中，21，43，41，31是逆序，逆序數是4，為偶排列。——這是北大《高等代數》上的定義。

定理：交換一個排列中的兩個數，則排列的奇偶性發生改變。（證明見任何一本《高等代數》）

我們將空格看成數字9（數字9對應空位），按正常順序看a圖，9個數字排列是123456789，其逆序數是0，是偶排列；b圖是123456879，逆序數是1，是奇排列。我們知道，我們能夠移動空塊相鄰的塊，這裡的移動相當於一種特殊的對換（相鄰對換），例如：對於b圖，移動6就相當於9和6互換（9向上移動了），移動7就相當於9和7互換（9向左移動了）。現在假設從b圖經過一系列的平移變到了a圖，則空格塊9必然移動（對換）了偶數次（向左一次必然要再向右一次回來，向上一次必然要向下再回來，最終才能夠回到右下角的位置），根據上面的定理最終變成的排列必然是仍然是奇排列（和b相同），然而a圖是偶排列，因而產生矛盾，因此b圖不可能通過平移變成最終的a圖。

拼圖的狀態分類

進一步考慮，a圖可以平移變成一些其他的狀態，我們把所有可以由a圖變換的到的狀態歸為一類，實際上這是一個等價關係（平移變換）決定的等價類（a圖一個代表元），b圖也代表一類，現在要問“拼圖總共有幾類？”，答案是大於等於2*2（2行2列）的拼圖都有且只有這2類。這裡只介紹證明思路：

1. 根據上面的定理，可以得出所有的拼圖至少分兩類；
2. 2*2（2行2列）的拼圖只有有兩類；
3. 拼圖在增大之後，分類數不增。

根據這3條就可得出結論：拼圖有且只有兩類。並且我們可以得出一些其他有趣的結果，兩類拼圖圖形上的差異是他們之間相差奇數次的對換（相當於把任意兩塊扣下來，對調），也就是說任意交換一個拼圖非空板塊奇數次，則它就變到另外一類里了。

對於分為兩類的理解，正如上的旋轉方向面上有順時針和逆時針之分。至此，我們就知道，如果拼圖的版塊是隨機打亂的，那么只有一半的可能是可以被還原的。

板塊三輪換的可還原性證明

在進行拼圖計算機化遊戲設計時，需要一個簡單的算法來打亂板塊。這裡提供一個簡單的打亂算法及其證明。

對於m*n的拼圖，從拼圖板塊中任取三塊做輪換，通過[(m*n)/3]^2次輪換，即可實現相當“亂”的打亂效果。如對於4*4的拼圖，進行25次三輪換。

三輪換的可還原性證明方法相當簡單和有趣：

1. 可以證明2*2的拼圖中，板塊三輪換是可還原的；
2. 對於任意m*n的拼圖X，可以通過變換F(X)使得三輪換的板塊加上空格移動到一個2*2的範圍內；
3. 在該2*2的範圍內還原該三個板塊的順序；
4. 通過F(X)的逆變換F'(X)復原拼圖X。

實現三輪換法打亂算法的JavaScript代碼

下面這段JavaScript腳本可直接替換Windows 7中Picture Puzzle桌面小工具中的相關函式。

shuffle = function()

{

var hold = 0;

var i;

var ri = new Array(15);

for (i=0; i < 15; i++)

ri[i] = i;

for(var j=0; j<5; j++)

{

ri.sort(function()

{

return Math.random()-0.5;

});

for (i=0; i < 15; i+=3)

{

hold = this.tileArray[ri[i]];

tileArray[ri[i]] = this.tileArray[ri[i+1]];

tileArray[ri[i+1]] = this.tileArray[ri[i+2]];

tileArray[ri[i+2]] = hold;

}

}

}

還原方法

簡單的考慮之後，我們就可以知道，還原一個拼圖是可以的（排好之後可以不在被動！）， 最後只剩最右下角的2*3或3*2的幾塊是亂序，再調好其中的2塊，剩下的3塊簡單輪換下位置就應該完成了，如果不對，那改圖就屬於那種不可以被還原的一類。