九宫问题(八数码)求解过程动态演示

核心提示：由于可扩展的数据量非常的大，加上我在保存的时候使用的是ＤＷＯＲＤ类型，九宫问题(八数码)求解过程动态演示(2)，将每一步数据都记录在一个排序二叉树中，按从小到大从左到有的排列，在搜索刚刚搜索到的位置的子位置，这样直到找到目标结果为止，搜索的时候跟每次搜索将近万次的形式比较快几乎是Ｎ次方倍，把几个在循环中用到的函数声明为

由于可扩展的数据量非常的大，加上我在保存的时候使用的是ＤＷＯＲＤ类型，将每一步数据都记录在一个排序二叉树中，按从小到大从左到有的排列，搜索的时候跟每次搜索将近万次的形式比较快几乎是Ｎ次方倍，把几个在循环中用到的函数声明为内联函数，并在插入的时候同时搜索插入的数据会不会在树中有重复来加快总体速度。二叉树插入代码：

inline bool CNineGird::AddTree(DWORD place , PlaceList*& parent)
{
　　if (parent == NULL)
　　{
　　　　parent = new PlaceList();
　　　　parent->Left = parent->Right = NULL;
　　　　parent->Place = place;
　　　　return true;
　　}
　　if (parent->Place == place)
return false;
　　if (parent->Place > place)
　　{
　　　　return AddTree(place , parent->Right);
　　}
　　return AddTree(place , parent->Left);
}计算结果是奇数排列还是偶数排列的代码：

bool CNineGird::EstimateUncoil(unsigned char *array)
{
　　int sun = 0;
　　for ( int i = 0 ; i < 8 ; i ++)
　　{
　　　　for ( int j = 0 ; j < 9 ; j ++)
　　　　{
　　　　　　if (array[j] != 0)
　　　　　　{
　　　　　　　　if (array[j] == i +1 )
　　　　　　　　　　break;
　　　　　　　　if (array[j] < i + 1)
　　　　　　　　　　sun++;
　　　　　　}
　　　　}
　　}
　　if (sun % 2 == 0)
　　　　return true;
　　else
　　　　return false;
}

移动到空格位的代码比较简单，只要计算是否会移动到框外面就可以了，并在移动的时候顺便计算一下是不是已经是目标结果，这是用来给用户手工移动是给与提示用的，代码：

inline bool CNineGird::MoveChess(unsigned char *array , int way)
{
　　int zero , chang;
　　bool moveok = false;
　　for ( zero = 0 ; zero < 9 ; zero ++)
　　{
　　　　if (array[zero] == 0)
　　　　　　break;
　　}
　　POINT pnt;
　　pnt.x = zero % 3;
　　pnt.y = int(zero / 3);
　　switch(way)
　　{
　　case 0 : //up
　　　　if (pnt.y + 1 < 3)
　　　　{
　　　　　　chang = (pnt.y + 1) * 3 + pnt.x ;
　　　　　　array[zero] = array[chang];
　　　　　　array[chang] = 0;
　　　　　　moveok = true;
　　　　}
　　　　break;
　　case 1 : //down
　　　　if (pnt.y - 1 > -1)
　　　　{
　　　　　　chang = (pnt.y - 1) * 3 + pnt.x ;
　　　　　　array[zero] = array[chang];
　　　　　　array[chang] = 0;
　　　　　　moveok = true;
　　　　}
　　　　break;
　　case 2 : //left
　　　　if (pnt.x + 1 < 3)
　　　　{
　　　　　　chang = pnt.y * 3 + pnt.x + 1;
　　　　　　array[zero] = array[chang];
　　　　　　array[chang] = 0;
　　　　　　moveok = true;
　　　　}
　　　　break;
　　case 3 : //right
　　　　if (pnt.x - 1 > -1)
　　　　{
　　　　　　chang = pnt.y * 3 + pnt.x - 1;
　　　　　　array[zero] = array[chang];
　　　　　　array[chang] = 0;
　　　　　　moveok = true;
　　　　}
　　　　break;
　　}
　　if (moveok && !m_bAutoRun)
　　{
　　　　m_iStepCount ++ ;
　　　　
　　　　DWORD temp1 ,temp2;
　　　　ArrayToDword(array , temp1);
　　　　ArrayToDword(m_iTargetChess , temp2);
　　　　if (temp1 == temp2)
　　　　{
　　　　　　MessageBox(NULL , "你真聪明这么快就搞定了!" , "^_^" , 0);　　　　
　　　　}
　　}
　　return moveok;
}　　我在进行广度搜索时候，将父结点所在的数组索引记录在子结点中了，所以得到目标排列的时候，我们只要从子结点逆向搜索就可以得到最优搜索路径了。用变量m_iPathsize来记录总步数，具体函数代码：

void CNineGird::GetPath(UINT depth)
{
　　int now = 0 , maxpos = 100 ;
　　UINT parentid;
　　if (m_pPathList != NULL)
　　{
　　　　delete[] m_pPathList;
　　}
　　m_pPathList = new PathList[maxpos];
　　parentid = m_pScanbuf[depth].ScanID;
　　
　　DwordToArray(m_pScanbuf[depth].Place , m_pPathList[++now].Path);
　　
　　while(parentid != -1)
　　{
　　　　if (now == maxpos)
　　　　{
　　　　　　maxpos += 10;
　　　　　　PathList * temlist = new PathList[maxpos];
　　　　　　memcpy(temlist , m_pPathList , sizeof(PathList) * (maxpos - 10));
　　　　　　delete[] m_pPathList;
　　　　　　m_pPathList = temlist;
　　　　}
　　　　DwordToArray(m_pScanbuf[parentid].Place , m_pPathList[++now].Path);
　　　　parentid = m_pScanbuf[parentid].ScanID;
　　}
　　m_iPathsize = now;
}　　动态排列的演示函数最简单了，为了让主窗体有及时刷新的机会，启动了一个线程在需要主窗体刷新的时候，用Ｓｌｅｅ（ＵＩＮＴ）函数来暂停一下线程就可以了。代码：

unsigned __stdcall MoveChessThread(LPVOID pParam)
{
　　CNineGird * pGird = (CNineGird *)pParam;
　　RECT rect;
　　pGird->m_iStepCount = 0;
　　::GetClientRect(pGird->m_hClientWin , &rect);
　　for ( int i = pGird->m_iPathsize ; i > 0 ; i --)
　　{
　　　　memcpy(pGird->m_iChess , pGird->m_pPathList[i].Path , 9);
　　　　pGird->m_iStepCount ++;
　　　　InvalidateRect( pGird->m_hClientWin , &rect , false);
　　　　Sleep(300);
　　}
　　char msg[100];
　　sprintf(msg , "^_^ ! 搞定了!
计算步骤用时%d毫秒" , pGird->m_iTime);
　　MessageBox(NULL , msg , "~_~" , 0);
　　pGird->m_bAutoRun = false;
　　return 0L;
}　　最后介绍一下搜索函数的原理，首先得到源数组，将其转换成ＤＷＯＲＤ型，与目标比较，如果相同完成，不同就交换一下数据和空格位置，加入二叉树，搜索下一个结果，直到没有步可走了，在搜索刚刚搜索到的位置的子位置，这样直到找到目标结果为止，函数：

bool CNineGird::ComputeFeel()
{
　　unsigned char *array = m_iChess;
　　UINT i;
　　const int MAXSIZE = 362880;
　　unsigned char temparray[9];
　　
　　DWORD target , fountain , parent , parentID = 0 , child = 1;
　　ArrayToDword(m_iTargetChess , target);
　　ArrayToDword(array , fountain);
　　if (fountain == target)
　　{
　　　　return false;
　　}
　　if (m_pScanbuf != NULL)
　　{
　　　　delete[] m_pScanbuf;
　　}
　　m_pScanbuf = new Scanbuf[MAXSIZE];
　　AddTree(fountain ,m_pPlaceList);
　　m_pScanbuf[ 0 ].Place = fountain;
　　m_pScanbuf[ 0 ].ScanID = -1;
　　clock_t tim = clock();
　　while(parentID < MAXSIZE && child < MAXSIZE)
　　{
　　　　parent = m_pScanbuf[parentID].Place;
　　　　for ( i = 0 ; i < 4 ; i ++)　// 0 :UP , 1:Down ,2:Left,3:Right
　　　　{
　　　　　　DwordToArray(parent , temparray);
　　　　　　if (MoveChess(temparray,i))　　　　//是否移动成功
　　　　　　{
　　　　　　　　ArrayToDword(temparray , fountain);
　　　　　　　　if (AddTree(fountain, m_pPlaceList))　　//加入搜索数
　　　　　　　　{
　　　　　　　　　　m_pScanbuf[ child ].Place = fountain;
　　　　　　　　　　m_pScanbuf[ child ].ScanID = parentID;
　　　　　　　　　　if (fountain == target) //是否找到结果
　　　　　　　　　　{
　　　　　　　　　　　　m_iTime = clock() - tim;
　　　　　　　　　　　　GetPath(child);//计算路径
　　　　　　　　　　　　FreeTree(m_pPlaceList);
　　　　　　　　　　　　delete[] m_pScanbuf;
　　　　　　　　　　　　m_pScanbuf = NULL;
　　　　　　　　　　　　return true;
　　　　　　　　　　}
　　　　　　　　　　child ++;
　　　　　　　　}
　　　　　　}
　　　　} // for i
　　　　parentID++;
　　}
　　m_iTime = clock() - tim;
　　FreeTree(m_pPlaceList);
　　delete[] m_pScanbuf;
　　m_pScanbuf = NULL;
　　return false;
}重要函数的介绍结束，下面是程序的运行结果和运算结果：