拼图算法分析
From:http://blog.sina.com.cn/s/blog_6a4b57e30100mfch.html
一、题目说明：（九宫问题）在一个３×３的九宫中有１－８这８个数及一个空格随机的摆放在其中的格子里，如图１－１所示。现在要求实现这个问题：将该九宫格调整为如图１－１右图所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。
（图１－１）二、题目分析：九宫问题是人工智能中的经典难题之一，问题是在３×３方格棋盘中，放８格数，剩下的没有放到的为空，每次移动只能是和相邻的空格交换数。程序自动产生问题的初始状态，通过一系列交换动作将其转换成目标排列（如下图１－２到图１－３的转换）。
（图１－２） （图１－３）
九宫问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个一维数组表示，如上图１－２我们就可以表示成｛８，７，１，５，２，６，３，４，０｝其中０代表空格。在这个数组中我们首先计算它能够重排列出来的结果，公式就是：
∑（Ｆ（Ｘ））＝Ｙ，其中Ｆ（Ｘ）
就是一个数他前面比这个数小的数的个数，Ｙ为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。
Ｆ（８）＝０；Ｆ（７）＝０；Ｆ（１）＝０；Ｆ（５）＝１；Ｆ（２）＝１；Ｆ（６）＝３；Ｆ（３）＝２；Ｆ（４）＝３；Ｙ＝０＋０＋０＋１＋１＋３＋２＋３＝１０
Ｙ＝１０是偶数，所以他的重排列就是如图１－３的结果，如果加起来的结果是奇数重排的结果就是如图１－１最右边的排法。三、算法分析九宫问题的求解方法就是交换空格（０）位置，直至到达目标位置为止。图形表示就是：
（图３－１）要想得到最优的就需要使用广度优先搜索，九宫的所以排列有９！种，也就是３６２８８０种排法，数据量是非常大的，我使用的广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，我们把数据进行适当的压缩。使用ＤＷＯＲＤ形式保存，压缩形式是每个数字用３位表示，这样就是３×９＝２７个字节，由于８的二进制表示形式１０００，不能用３位表示，我使用了一个小技巧就是将８表示位０００，然后用多出来的５个字表示８所在的位置，就可以用ＤＷＯＲＤ表示了。用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。类结构如下：
//NineGrid.hclassCNineGird{public:structPlaceList{DWORDPlace;PlaceList*Left;PlaceList*Right;};structScanbuf{DWORDPlace;intScanID;};structPathList{unsignedcharPath[9];};private:PlaceList*m_pPlaceList;Scanbuf*m_pScanbuf;RECTm_rResetButton;RECTm_rAutoButton;public:intm_iPathsize;clock_tm_iTime;UINTm_iStepCount;unsignedcharm_iTargetChess[9];unsignedcharm_iChess[9];HWNDm_hClientWin;PathList*m_pPathList;boolm_bAutoRun;private:inlineboolAddTree(DWORDplace,PlaceList*&parent);voidFreeTree(PlaceList*&parent);inlinevoidArrayToDword(unsignedchar*array,DWORD&data);inlinevoidDwordToArray(DWORDdata,unsignedchar*array);inlineboolMoveChess(unsignedchar*array,intway);boolEstimateUncoil(unsignedchar*array);voidGetPath(UINTdepth);public:voidMoveChess(intway);boolComputeFeel();voidActiveShaw(HWNDhView);voidDrawGird(HDChDC,RECTclientrect);voidDrawChess(HDChDC,RECTclientrect);voidReset();voidOnButton(POINTpnt,HWNDhView);public:CNineGird();~CNineGird();};
计算随机随机数组使用了vector模板用random_shuffle（，）函数来打乱数组数据，并计算目标结果是什么。代码：
//NineGrid.cpp#include"NineGrid.h"voidCNineGird::Reset(){if(m_bAutoRun)return;vectorvs;inti;for(i=1;im_pPathList[i].Path,9);pGird->m_iStepCount++;InvalidateRect(pGird->m_hClientWin,&rect,false);Sleep(300);}charmsg[100];sprintf(msg,"^_^!搞定了! 计算步骤用时%d毫秒",pGird->m_iTime);MessageBox(NULL,msg,"~_~",0);pGird->m_bAutoRun=false;return0L;}//最后介绍一下搜索函数的原理，首先得到源数组，将其转换成ＤＷＯＲＤ型，与目标比较，如果相同完成，不同就交换一下数据和空格位置，加入二叉树，搜索下一个结果，直到没有步可走了，在搜索刚刚搜索到的位置的子位置，这样直到找到目标结果为止，函数：boolCNineGird::ComputeFeel(){unsignedchar*array=m_iChess;UINTi;constintMAXSIZE=362880;unsignedchartemparray[9];DWORDtarget,fountain,parent,parentID=0,child=1;ArrayToDword(m_iTargetChess,target);ArrayToDword(array,fountain);if(fountain==target){returnfalse;}if(m_pScanbuf!=NULL){delete[]m_pScanbuf;}m_pScanbuf=newScanbuf[MAXSIZE];AddTree(fountain,m_pPlaceList);m_pScanbuf[0].Place=fountain;m_pScanbuf[0].ScanID=-1;clock_ttim=clock();while(parentID