一、问题描述（description）
大家应该都玩过拼图游戏，常见的拼图游戏一般为4*4，3*3可能过于简单，5*5及5*5以上的虽然块数增多，但是难易程度并没有比4*4多很多，所以常见的应该是4*4的拼图。
以3*3为例，拼图应该如下图所示（以数字为例）：
1 2 3
4 5 6
7 8 9 （图一）
注：9 通常为空白块
为了表示方便（符合计算机求解的要求），内部数据使用0开始的数组表示，如下
0 1 2
3 4 5
6 7 8 （图二）
注：8 为空白块
通常拼图游戏就是打乱，还原的游戏，打乱的图如下：
3 5 6
0 8 7
1 4 2（图三）
也就是同过有限的步骤，将图三（不一定有解）还原成图二
二、问题分析（analysis）
根据问题的描述，拼图游戏可以分解成以下三个子问题：1、如何表示 2、打乱算法 3、还原算法
1、如何表示，即如何将拼图在计算机中表示出来。这个问题又可以分解成两个问题，a）内部表示，主要用于实现算法，b）外部表示，即试图，也就是用户用来交互的界面。
a)内部表示可以使用一维数组，也可以使用二位数组，通常一维数组和二位数组可以简单的转化。
使用一维数组表示(c#代码，下同）：
int[] blocks1 = new int[] { 0, 1 , 2, 3, 4, 5, 6, 7, 8 }
使用二维数组表示：
int[,] blocks2 = new int[,]
{
{0, 1, 2},
{3, 4, 5},
{6, 7, 8}
};
二者的转化 blocks[i] = blocks2[ i / 3, i %3]
b)视图部分，可以放置3*3个等大小的图片，或者把一个大的图片切割成3*3的小块，具体的参见解决方案。
2、打乱算法，如果使用纯粹的随机打乱算法，那么会出现无解的情况，即无论如何移动，都无法还原成图二的情况。这一部分在网上搜索了一下，各种说法都有，看着眼晕。无法一一求证，以下的说法比较靠谱，描述如下：
对于一个m*n据序列A，如果经过有限的移动，形成另外一个m*n的序列A’（A’即目标，如图二），必须满足A和A'的逆序数的奇偶性加上空白块行列的奇偶性相同。这里只给出相关解释，不给证明。
首先解释什么是逆序数，逆序就是一个序列（正常情况应该是从小到大）中某个元素后面的元素小于该元素，所有的逆序数的和是奇数或者是偶数，称之为逆序数的奇偶性。
例如：1 2 3 就没有逆序数，即逆序数为0，为偶数；3 1 2 就有两个逆序数（3,1），（3,2），其逆序数和为2，也是偶数。
对于图二，如果8（空白）和5交换，一定可以经过再次交换还原过来，如下图
0 1 2
3 4 8
6 7 5 （图四）
可以计算一下图四的逆序数（8,6）+（8,7）+（8,5）+（6,5）+（7,5）= 5，同时空白（8）所在行1，列2，加在一起，5+1+2=8，和图二（逆序数及8的行列和为4）的逆序数及行列和的奇偶性相同。所以，图四有解（显而易见）。
以下几个链接可以参考：
http://blog.csdn.net/tailzhou/article/details/3002442
http://tieba.baidu.com/p/2025276932?pn=1
我上面的推演不知道对否，感兴趣的可以讨论一下。
打乱的算法，好像也有人给出
http://www.cnblogs.com/idche/archive/2012/04/25/2469516.html
/** 判断一个打乱顺序的数字拼图是否可还原 order: 打乱以后的数字顺序；比如[0,1,2,3,4,5,7,6,8] order里的数字8表示空位 size: 3*3的拼图就传3就可以了 返回值：true false */ function solvability(order, size){ var a; var count = 0; var m = 0; var n = 0; var len = order.length; size = size || 3; //[0,1,2,3,4,5,7,6,8] for(var i=0; i<len; i++){ a = order[i]; //if( a == 8){ if(a == size*size-1){ m = parseInt(i/size); n = parseInt(i%size); } for(var j=i+1; j<len; j++){ if(order[j]<a){ count++; } } } count += m; count += n; return count%2 == 0; }
3、还原算法，还原算法想到了两个，一个是搜索算法，一个是人工智能（不知道这个词是否准确，即模拟人工思维方式，给出的解决方法），搜索的算法以后补充，这里只给出人工智能（暂时用这个词来表达）。
a)人工智能
这里主要给出推理过程。
（0）这里只给出n*n的推理，即行列相同，对于行列不同的，与行列相同的问题类似。
（1）如果只有一块1*1，不用做任何移动，已经完成目标。
（2）对于2*2（这应该是还可以玩一下的最简单拼图）情况如下：
0 1
2 3 （图五）（其中3为空白，这也是目标图）
对于这个图能够还原的，有一下几个，如：（不完全枚举）
2 0 1 3
3 1 0 2 ......
稍加分析可知，对于2 * 2 的拼图，有解的，通过顺时针或逆时针n步之后（事实上，2*2的拼图只能做顺时针或逆时针旋转），都可以达到目标图。反例如下：
0 2
1 3
即只有2 1 对调，这个图，无论如何也不可能还原成图五，可以用逆序数及空白块行列和的奇偶性证明。
结论，2 * 2 的拼图，顺时针或逆时针n次，必然还原。
（3）对于3 * 3 的拼图（如图二），是在 2 * 2 的拼图的基础上，加上了一行一列，即：
一行（0 1 2）加一列（竖向3 6）又加上个 2 * 2 （下图），得到的图二
4 5
7 8
可以给出结论，对于3 * 3 拼图，如果能拼出一行（0 1 2）和一列（3 6），剩下的问题同步骤（2）
（4）4 * 4 的拼图等于在3 * 3的基础上又加了一行和一列。
（5）后续的都是递归。
结论：对于n*n的拼图游戏，算法步骤：
（1）对于2 * 2 的拼图，顺（逆）时针n步，每步都进行判断，是否达到目标，如果达到，结束程序。
（2）对于n*n的拼图，先拼一行，然后拼一列，然后递归（n-1）*（n-1）的拼图。
三、解决方案（solution）
挺晚的了，暂时不提供，随后补上。
相关文章
