《不可还原的拼图》是一款拼图类游戏。
在3*3或来自4*4数字中360百科，有的拼图拼到最后出现有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数字拼图标准的结360百科果，则对于图b的状态是不可能变换成a手请植换吧件的。证明起来需要所志一重用到高等代数里逆序数的概念，具体的说是用到了一个简单的定理。
定义:在一个1,2,.单写味结击船审巴布末..,n的排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后雷喜其准程赵有排生飞面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序带使身程突易修九沿数。逆序数为偶数的排列称为偶排列;逆序数为奇数低养室又减的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。--传酸兵使际活需物们步这是北大《高等代数》上的定义。
定理:交球时里必影英农缩质测抓换一个排列中的两个数，则排列的奇偶性发生改变。(证明见任何一本《高等代数粉滑经》)
我们将空格看成数字9(数字9对应空位)应南源笑振就叶把，按正常顺序看a图，9个数字排列是123456789，其逆序数是0，肉血几与妒足架场燃是偶排列;b图是1234通危权某胞56879，逆序数是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类。这里只介绍证明思路:
- 根据上面的定理，可以得出所有的拼图至少分两类;
- 2*2(2行2列)的拼图只有有两类;
- 拼图在增大之后，分类数不增。
根据这3条就可得出结论:拼图有且只有两类。并且我们可以得出一些其他有趣的结果，两类拼图图形上的差异是他们之间相差奇数次的对换(相当于把任意两块扣下来，对调)，也就是说任意交换一个拼图非空板块奇数次，则它就变到另外一类里了。
对于分为两类的理解，正如上的旋转方向面上有顺时针和逆时针之分。至此，我们就知道，如果拼图的版块是随机打乱的，那么只有一半的可能是可以被还原的。
板块证明
来自 在进行拼图计算机化游戏设计时，需要一个简单的算法来打应贵也乱板块。这里提供一个简单的打乱算法及其证明。
对于m*民则顶有场死n的拼图，从拼图板块中任取三块做轮换，通过[(m*n)/3]^2次轮换，即可实现相当"乱"的打乱效果。如对于4*4的拼图，进行25次三轮换。
三轮换的可还原性证明方法相当简单和有趣:
- 可以证明2*2的拼图中，板块三轮换是可还原的;
- 对于任意m*n的拼图X，可以通过变换F(X)使得三轮360百科换的板块加上空格移动到一个2*2的范围内;
- 在该2*2的范围内还原该三个点板块的顺序;
- 通过F(X)的逆变换F'(X厚丝鲜若)复原拼图X。
算法代码
下面这段JavaScript脚本可直接替换Windows 7中Picture Puzzle桌面小工具中的相关函数。
shuffle = function()
斤亲上七增兴侵 {
var hold = 0;
var i;
var ri = new Ar来ray(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;
});
f识密题or (i=0; i < 15; i+=3)
{
hold = this投方积究加延么医五破.tileArr双含奏育压架ay[ri[i]];
tileArray[ri[i]] = this.til圆点查eArray[ri[i+1]];
tileArray[ri[i+1]] = this.tileArray[ri[i+2]];
tileArray[ri[i+2]] = hold委剂选脚半英换;
}
}
}
还原方法
简单的考虑之后，我们就可以知道，还原一个拼图是可以的(排好之后可以汽车角失永不在被动!)， 最后只剩最右下角的2*3或3*2的几块是乱序，再调好其中的2块，剩下的3块简单轮换下位置就应该完成了，如果不对，那该图就属于那种不油引略欢可以被还原的一类。
13888888888
点击咨询 