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

核心提示：一、题目说明：（九宫问题）在一个３×３的九宫中有１－８这８个数及一个空格随机的摆放在其中的格子里，如图１－１所示，九宫问题(八数码)求解过程动态演示，现在要求实现这个问题：将该九宫格调整为如图１－１右图所示的形式，调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中，）函数来打乱数组

一、题目说明：

（九宫问题）在一个３×３的九宫中有１－８这８个数及一个空格随机的摆放在其中的格子里，如图１－１所示。现在要求实现这个问题：将该九宫格调整为如图１－１右图所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。

（图１－１）

二、题目分析：

九宫问题是人工智能中的经典难题之一，问题是在３×３方格棋盘中，放８格数，剩下的没有放到的为空，每次移动只能是和相邻的空格交换数。程序自动产生问题的初始状态，通过一系列交换动作将其转换成目标排列（如下图１－２到图１－３的转换）。

（图１－２）	（图１－３）

九宫问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个一维数组表示，如上图１－２我们就可以表示成｛８，７，１，５，２，６，３，４，０｝其中０代表空格。

在这个数组中我们首先计算它能够重排列出来的结果，公式就是：

∑（Ｆ（Ｘ））＝Ｙ，其中Ｆ（Ｘ）

就是一个数他前面比这个数小的数的个数，Ｙ为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。

Ｆ（８）＝０；
Ｆ（７）＝０；
Ｆ（１）＝０；
Ｆ（５）＝１；
Ｆ（２）＝１；
Ｆ（６）＝３；
Ｆ（３）＝２；
Ｆ（４）＝３；
Ｙ＝０＋０＋０＋１＋１＋３＋２＋３＝１０

Ｙ＝１０是偶数，所以他的重排列就是如图１－３的结果，如果加起来的结果是奇数重排的结果就是如图１－１最右边的排法。

三、算法分析

九宫问题的求解方法就是交换空格（０）位置，直至到达目标位置为止。图形表示就是：

（图３－１）

要想得到最优的就需要使用广度优先搜索，九宫的所以排列有９！种，也就是３６２８８０种排法，数据量是非常大的，我使用的广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，我们把数据进行适当的压缩。使用ＤＷＯＲＤ形式保存，压缩形式是每个数字用３位表示，这样就是３×９＝２７个字节，由于８的二进制表示形式１０００，不能用３位表示，我使用了一个小技巧就是将８表示位０００，然后用多出来的５个字表示８所在的位置，就可以用ＤＷＯＲＤ表示了。用移位和或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。

类结构如下：

class CNineGird
{
public:
　　struct PlaceList
　　{
　　　　DWORD　　　　Place;
　　　　PlaceList*　　Left;
　　　　PlaceList*　　Right;
　　};
　　struct Scanbuf
　　{
　　　　DWORD Place;
　　　　int ScanID;
　　};
　　struct PathList
　　{
　　　　unsigned char Path[9];
　　};
private:
　　PlaceList *m_pPlaceList;
　　Scanbuf *m_pScanbuf;
　　RECT m_rResetButton;
　　RECT m_rAutoButton;
public:
　　int m_iPathsize;
　　clock_t m_iTime;
　　UINT m_iStepCount;
　　unsigned char m_iTargetChess[9];
　　unsigned char m_iChess[9];
　　HWND m_hClientWin;
　　PathList *m_pPathList;
　　bool m_bAutoRun;
private:
　　inline bool AddTree(DWORD place , PlaceList*& parent);
　　void FreeTree(PlaceList*& parent);
　　inline void ArrayToDword(unsigned char *array , DWORD & data);
　　inline void DwordToArray(DWORD data , unsigned char *array);
　　inline bool MoveChess(unsigned char *array , int way);
　　bool EstimateUncoil(unsigned char *array);
　　void GetPath(UINT depth);
　　
public:
　　void MoveChess(int way);
　　bool ComputeFeel();
　　void ActiveShaw(HWND hView);
　　void DrawGird(HDC hDC , RECT clientrect);
　　void DrawChess(HDC hDC , RECT clientrect);
　　void Reset();
　　void OnButton(POINT pnt , HWND hView);
　　
public:
　　CNineGird();
　　~CNineGird();
};　　计算随机随机数组使用了vector模板用random_shuffle（，）函数来打乱数组数据，并计算目标结果是什么。代码：

void CNineGird::Reset()
{
　　if(m_bAutoRun) return;
　　vector<int> vs;
　　int i;
　　for (i = 1 ; i < 9 ; i ++)
　　　　vs.push_back(i);
　　vs.push_back(0);
　　random_shuffle(vs.begin(), vs.end());
　　random_shuffle(vs.begin(), vs.end());
　　for ( i = 0 ; i < 9 ; i ++)
　　{
　　　　m_iChess[i] = vs[i];
　　}
　　
　　if (!EstimateUncoil(m_iChess))
　　{
　　　　unsigned char array[9] = {1,2,3,8,0,4,7,6,5};
　　　　memcpy(m_iTargetChess , array , 9);
　　}
　　else
　　{
　　　　unsigned char array[9] = {1,2,3,4,5,6,7,8,0};
　　　　memcpy(m_iTargetChess , array , 9);
　　}
　　m_iStepCount = 0;
}数据压缩函数实现：

inline void CNineGird::ArrayToDword(unsigned char *array , DWORD& data)
{
　　unsigned char night = 0;
　　for ( int i = 0 ; i < 9 ; i ++)
　　{
　　　　if (array[i] == 8)
　　　　{
　　　　　　night = (unsigned char)i;
　　　　　　break;
　　　　}
　　}
　　
　　array[night] = 0;
　　data = 0;
　　data =　　 (DWORD)((DWORD)array[0] << 29 | (DWORD)array[1] << 26 |
　　　　　　　　　　 (DWORD)array[2] << 23 | (DWORD)array[3] << 20 |
　　　　　　　　　　 (DWORD)array[4] << 17 | (DWORD)array[5] << 14 |
　　　　　　　　　　 (DWORD)array[6] << 11 | (DWORD)array[7] <<　8 |
　　　　　　　　　　 (DWORD)array[8] <<　5 | night);
　　
　　array[night] = 8;
}解压缩时跟压缩真好相反，解压代码：

inline void CNineGird::DwordToArray(DWORD data , unsigned char *array)
{
　　unsigned char chtem;
　　for ( int i = 0 ; i < 9 ; i ++)
　　{
　　　　chtem = (unsigned char)(data >> (32 - (i + 1) * 3) & 0x00000007);
　　　　array[i] = chtem;
　　}
　　chtem = (unsigned char)(data & 0x0000001F);
　　array[chtem] = 8;
}