army8735

这是我第3次做拼图游戏了。算法简单得很，而且是最少的9宫拼图，拿到设计稿后不外几个小时搞定。

记得2008年7月份，刚毕业被EOL拉进PCHome的时候，工作所做的第一个就是flash游戏拼图（9、16、25宫）。那时为了研究出如何防止拼图死局，着实花了不少功夫（小时候玩的金山文曲星中就经常出现这个bug）。为此我特地发了个帖子求助数学大人，最终问题得以解决。

那么，什么是拼图死局呢？

以最简单的9宫拼图为例，拼图的最终目的是将随机的数块移动到如下状态：

1 2 3

4 5 6

7 8

第9格是空的，用以让玩家能够任意移动某一个数块。但是，初始随机情况可能会是这样：

1 2 3

4 5 6

8 7

这种情况下，想要变换到正确的结束状态是不可能的。至于为什么，繁琐的数学证明就不贴了。记得曾经《读者》杂志上刊登过这个东西，说是国外某位数学家悬赏1000w美金让人来拼这个拼图，结果无一人能做到。最后他才公布为何不能做到：因为这种情况的开始逆序和和目标逆序和不同。

数学定义：

n*n的方格中放入1,2,3,…,n-1及一个空格，在任何一种状态A下，
定义：f(i)=k，表示i放在第k个格子中，k按照从左至右，从上到下排序；
定义：g(i,j)=1,如果(f(i)-f(j))(i-j)<0；否则为0；
定义：F(A)=SUMg(i,j)，对所有i,j求和；
当n=3时；
目标状态F(Aobj)=0，你给的状态F(Abegin)=1；
而移动空格只有2种方式：在同行中移动不改变F值，在不同行中移动F值+2，-2或不变；
利用F函数可以解决所有n为奇数的情况；
当n为偶数时，定义F1(A)=F(A)+空格所在行&1；处理方式一样。

当初始随机情况出现死局时，逆序和就会不相等，那么发现之后该怎么办呢？当然不会重新去随机一次，这太傻了。解开锁的钥匙很简单，随便交换同行的2个数块的位置即可。

那个时候写的一个产生9、16宫随机初始数块顺序的工厂（现在看来无需用工厂方法，一个类就能搞定）：

//GenMatrixFactory
package matrix {
	public class GenMatrixFactory {

		public static function getArray(i:int):Array {
			var m:Matrix;
			switch(i) {
				case 3:
					m = new Matrix3();
				break;
				case 4:
					m = new Matrix4();
				break;
				default:
					throw new Error("none of matrix");
			}
			return m.getMatrix();
		}
	}
}

//Matrix
package matrix {
	interface Matrix {
		function getMatrix():Array;
	}
}

//Matrix3
package matrix {

	class Matrix3 implements Matrix {
		private var gameArray:Array;
		private var numList:Array;

		public function Matrix3() {
			initGameArray();
			initNumList();
		}

		private function initGameArray():void {
			//创建游戏拼图数组
			gameArray = new Array(8);
			for (var i:int = 0; i < gameArray.length; i++) {
				gameArray[i] = 0;
			}
		}
		private function initNumList():void {
			//最终状态数组
			numList = new Array(8);
			for (var i:int = 1; i <= numList.length; i++) {
 				numList[i - 1] = i;
 			}
 		}
 		public function getMatrix():Array {
 			//获取最终状态逆序和
 			var reverse:int = getReverse();
 			//产生0～array长度的随机数填充array
 			var i:int = 0;
 			while (numList.length > 0) {
				var rand:int = Math.floor(Math.random() * numList.length);
				gameArray[i++] = numList.splice(rand, 1)[0];
			}
			return Validate.validata(gameArray, reverse);
		}

		private function getReverse():int {
			var sum:int = 0;
			for (var i:int = 0; i < numList.length - 1; i++) {
				for (var j:int = i + 1; j < numList.length; j++) {
					if ((i - j) * (numList[i] - numList[j]) < 0) {
						sum++;
					}
				}
			}
			return sum;
		}
	}
}

//Matrix4
package matrix {

	class Matrix4 implements Matrix {
		private var gameArray:Array;
		private var numList:Array;

		public function Matrix4() {
			initGameArray();
			initNumList();
		}

		private function initGameArray():void {
			//创建游戏拼图数组
			gameArray = new Array(15);
			for (var i:int = 0; i < gameArray.length; i++) {
				gameArray[i] = 0;
			}
		}
		private function initNumList():void {
			//最终状态数组
			numList = new Array(15);
			for (var i:int = 1; i <= numList.length; i++) {
 				numList[i - 1] = i;
 			}
 		}
 		public function getMatrix():Array {
 			//获取最终状态逆序和
 			var reverse:int = getReverse();
 			//产生0～array长度的随机数填充array
 			var i:int = 0;
 			while (numList.length > 0) {
				var rand:int = Math.floor(Math.random() * numList.length);
				gameArray[i++] = numList.splice(rand, 1)[0];
			}
			return Validate.validata(gameArray, reverse);
		}

		private function getReverse():int {
			var sum:int = 0;
			for (var i:int = 0; i < numList.length - 1; i++) {
				for (var j:int = i + 1; j < numList.length; j++) {
					if ((i - j) * (numList[i] - numList[j]) < 0) {
						sum++;
					}
				}
			}
			return sum;
		}
	}
}

//Validate
package matrix {

	class Validate {
		public static function validata(gameArray:Array, reverse:int):Array {
			var sum:int = 0;
			for (var i:int = 0; i < gameArray.length - 1; i++) {
				for (var j:int = i + 1; j < gameArray.length; j++) {
					if ((i - j) * (gameArray[i] - gameArray[j]) < 0) {
						sum++;
					}
				}
			}
			//逆序和不同时死局，调整同行相邻两个
			if (sum % 2 != reverse % 2) {
				var temp:int = 0;
				temp = gameArray[0];
				gameArray[0] = gameArray[1];
				gameArray[1] = temp;
			}
			return gameArray;
		}
	}
}