这是我第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;
}
}
}
本博客所有文章均采用