在壹個3×3的九宮中，有八個數字1-8和壹個空格隨機放置在網格中，如圖1-1。現在要求認識到這個問題:調整成圖1-1右圖所示的形式。調整規則是壹次只能將壹個與空格相鄰的數字(上、下、左或右)轉換到空格中。嘗試編程解決這個問題。
(圖1-1)
二、題目分析:
這是人工智能中的經典問題之壹。問題是在壹個3×3的棋盤裏，放了8個方格，剩下的都是空的，每壹步棋只能和相鄰的空格交換。程序自動生成問題的初始狀態，並通過壹系列交換動作將其轉化為目標排列(如下圖1-2至圖1-3)。
(圖1-2)(圖1-3)
在這個問題中，程序生成的隨機排列轉化為目標* * *，有兩種可能，且兩者不能同時成立，即奇排列和偶排列。隨機排列的數組可以用從左到右、從上到下的壹維數組來表示。如上圖所示，1-2可以表示為{8，7，1，5，2，6，3，4，0}其中0表示壹個空格。
在這個數組中，我們首先計算它可以重新排列的結果，公式是:
∑ (F(X)) = y，其中F(X)
是壹個數前面小於這個數的數，當y是奇數和偶數時有解。(8)確定是否存在數字問題的解決方案)
上面的數組可以解決它的結果。
f(8)= 0；
f(7)= 0；
f(1)= 0；
f(5)= 1；
f(2)= 1；
f(6)= 3；
f(3)= 2；
f(4)= 3；
y = 0+0+0+1+1+3+2+3 = 10
Y = 10是偶數，所以它的重排是如圖1-3所示的結果。如果求和結果是奇數重排，結果是最右邊的排列，如圖1-1。
三、算法分析
解決方法是交換空格(0)的位置，直到到達目標位置。圖形表示為:
(圖3-1)
想要得到最好的，需要使用廣度優先搜索，所以九宮有9個！排列方式有362880種，數據量非常大。使用廣度搜索，需要記住每個節點的排列形式。如果用數組來記錄，會占用大量內存，可以適當壓縮數據。以DWORD格式保存。壓縮後的形式是每個數用3位表示，也就是3× 9 = 27字節。因為8的二進制表示是1000，所以不能用3位表示。壹個竅門是把8表示成000，然後用多出來的五個字來表示8的位置，所以可以用DWORD來表示。用移位和或運算壹個壹個移動數據，比乘法快。定義了幾個結果來存儲遍歷的結果和搜索完成後的最優路徑。
該類的結構如下:
分類網格
{
公共:
結構位置列表
{
德沃德廣場；
PlaceList * Left
PlaceList * Right
};
struct Scanbuf
{
德沃德廣場；
int ScanID
};
結構路徑列表
{
無符號字符路徑[9]；
};
私人:
PlaceList * m _ pPlaceList
Scanbuf * m _ pScanbuf
RECT m _ rResetButton；
RECT m _勞托巴頓；
公共:
int m _ iPathsize
clock _ t m _ iTime
UINT m _ iStepCount
無符號字符m _ iTargetChess[9]；
無符號字符m _ I chess[9]；
HWND m _ hClientWin
PathList * m _ pPathList
波爾m _博托倫；
私人:
內嵌bool AddTree(DWORD place，PlaceList * & amp家長)；
void free tree(place list * & amp；家長)；
內聯void ArrayToDword(無符號字符數組，DWORD & amp數據)；
inline void DwordToArray(DWORD數據，無符號char * array)；
inline bool MoveChess(無符號char *array，int way)；
bool EstimateUncoil(無符號char * array)；
void GetPath(單位深度)；
公共:
void move chess(int way)；
bool ComputeFeel()；
void active shaw(HWND h view)；
void draw grid(HDC HDC，RECT client rect)；
void DrawChess(HDC hDC，RECT client rect)；
void Reset()；
void按鈕(點pnt，HWND h view)；
公共:
cninegrid()；
~ cninegrid()；
};
用向量模板計算隨機的隨機數組，用random_shuffle(，)函數對數組數據進行置亂，計算出目標結果。代碼:
void cn inegrid::Reset()
{
if(m_bAutoRun)返回；
向量vs；
int I；
for(I = 1；我& lt9 ;i ++)
vs.push_back(壹)；
vs . push _ back(0)；
random_shuffle(vs.begin()、vs . end())；
random_shuffle(vs.begin()、vs . end())；
for(I = 0；我& lt9 ;i ++)
{
m _ iChess[I]= vs[I]；
}
如果(！估計解卷(m_iChess))
{
無符號字符數組[9] = {1，2，3，8，0，4，7，6，5 }；
memcpy(m_iTargetChess，array，9)；
}
其他
{
無符號字符數組[9] = {1，2，3，4，5，6，7，8，0 }；
memcpy(m_iTargetChess，array，9)；
}
m _ iStepCount = 0；
}
數據壓縮功能的實現:
inline void cninegrid::ArrayToDword(unsigned char * array，DWORD & amp數據)
{
無符號字符夜= 0；
for(int I = 0；我& lt9 ;i ++)
{
if (array[i] == 8)
{
night =(無符號char)I；
打破；
}
}
array[night]= 0；
數據= 0；
data =(DWORD)((DWORD)array[0]& lt；& lt29 |(DWORD)array[1]& lt；& lt26 |
(DWORD)數組[2]& lt；& lt23 |(DWORD)array[3]& lt；& lt20 |
(DWORD)數組[4]& lt；& lt17 |(DWORD)array[5]& lt；& lt14 |
(DWORD)數組[6]& lt；& lt11 |(DWORD)array[7]& lt；& lt8 |
(DWORD)數組[8]& lt；& lt5 |夜)；
array[night]= 8；
}
解壓和壓縮正好相反。解壓縮代碼:
內聯void cninegrid::DwordToArray(DWORD數據，無符號字符*數組)
{
無符號字符chtem
for(int I = 0；我& lt9 ;i ++)
{
chtem =(無符號字符)(data & gt& gt(32-(I+1)* 3)；0x 000000007)；
array[I]= chtem；
}
chtem =(無符號字符)(data & amp0x 0000001F)；
array[chtem]= 8；
}
由於可擴展數據量非常大，保存時使用DWORD類型，每壹步數據都記錄在壹棵排序的二叉樹中，從左到右從小到大排列，搜索時間比每次近萬次快了差不多n倍。循環中使用的幾個函數被聲明為內聯函數，同時搜索插入的數據在樹中是否會重復，以加快整體速度。二叉樹插入碼:
AddTree(DWORD place，PlaceList * & amp父母)
{
if (parent == NULL)
{
parent = new place list()；
父->；left = parent->；右=空；
父->；Place =地點；
返回true
}
if(父-& gt；Place == place
返回false
if(父-& gt；Place & gt地點)
{
返回AddTree(place，parent-& gt；對)；
}
返回AddTree(place，parent-& gt；左)；
}
計算結果是奇數碼還是偶數碼:
bool CNI negrid::estimate dependicle(無符號字符*數組)
{
int sun = 0；
for(int I = 0；我& lt8 ;i ++)
{
for(int j = 0；j & lt9 ;j ++)
{
if (array[j]！= 0)
{
if (array[j] == i +1)
打破；
if(array[j]& lt；i + 1)
sun++；
}
}
}
if (sun % 2 == 0)
返回true
其他
返回false
}
移動到空格位的代碼比較簡單，只需要計算是否會移動到框外，移動時計算是否已經是目標結果，用來給用戶手動移動和提示。代碼:
內聯bool cninegrid::move chess(無符號char *array，int way)
{
int零，chang
bool moveok = false
for(零= 0；zero & lt9 ;零++)
{
if(數組[零] == 0)
打破；
}
點pnt
pnt.x =零% 3；
pnt.y = int(零/3)；
開關(路)
{
案例0://上
if(pnt . y+1 & lt；3)
{
Chang =(pnt . y+1)* 3+pnt . x；
array[zero]= array[Chang]；
array[Chang]= 0；
moveok = true
}
打破；
案例1 : //down
if(pnt . y-1 & gt；-1)
{
Chang =(pnt . y-1)* 3+pnt . x；
array[zero]= array[Chang]；
array[Chang]= 0；
moveok = true
}
打破；
案例2://左
if(pnt . x+1 & lt；3)
{
Chang = pnt . y * 3+pnt . x+1；
array[zero]= array[Chang]；
array[Chang]= 0；
moveok = true
}
打破；
案例3://對
if(pnt . x-1 & gt；-1)
{
Chang = pnt . y * 3+pnt . x-1；
array[zero]= array[Chang]；
array[Chang]= 0；
moveok = true
}
打破；
}
if(moveok & amp；& amp！m _包托倫)
{
m _ istepcount++；
DWORD temp1，temp2
ArrayToDword(數組，temp 1)；
ArrayToDword(m_iTargetChess，temp 2)；
if (temp1 == temp2)
{
MessageBox(NULL，“妳真聰明，這麽快就完成了！”, "^_^" , 0);
}
}
返回moveok
}
在廣度搜索中，父節點所在的數組索引被記錄在子節點中，因此在得到目標排列時，可以從子節點開始反向搜索，得到最優的搜索路徑。使用變量m_iPathsize記錄總步數。具體的功能代碼是:
void cn inegrid::get path(單位深度)
{
int now = 0，maxpos = 100；
UINT parentid
if (m_pPathList！=空)
{
刪除[]m _ ppath list；
}
m_pPathList =新路徑列表[max pos]；
parentid = m _ pScanbuf[深度]。ScanID
DwordToArray(m _ pScanbuf[深度])。Place，m_pPathList[++now]。路徑)；
while(parentid！= -1)
{
if (now == maxpos)
{
maxpos+= 10；
path list * tem list = new path list[max pos]；
memcpy(temlist，m_pPathList，sizeof(path list)*(max pos-10))；
刪除[]m _ ppath list；
m _ pPathList = temlist
}
DwordToArray(m _ pScanbuf[parentid])。Place，m_pPathList[++now]。路徑)；
parentid = m_pScanbuf[parentid]。ScanID
}
m _ iPathsize = now
}
動態排列的演示功能最簡單。為了給主窗體壹個及時刷新的機會，啟動了壹個線程。當主窗體需要刷新時，只需使用Slee(UINT)函數暫停線程即可。代碼:
無符號_ _ stdcall MoveChessThread(LPVOID PPAR am)
{
cninegrid * p grid =(cninegrid *)PP aram；
RECT矩形；
p gird-& gt；m _ iStepCount = 0；
* GetClientRect(pg ird-& gt；m _ hClientWin & amp；rect)；
for(int I = p gird-& gt；m _ iPathsize我& gt0 ;我-)
{
memcpy(pg ird-& gt；m_iChess，pg ird-& gt；m _運動員[i]。路徑，9)；
p gird-& gt；m _ istepcount++；
invalidator(pg ird-& gt；m _ hClientWin & amp；rect，false)；
睡眠(300)；
}
char msg[100]；
sprintf(msg，“^_^！搞定了！\ r \計算步驟需要%d毫秒"，p grid-& gt；m _ iTime)；
MessageBox(NULL，msg，" ~_~ "，0)；
p gird-& gt；m _ bAutoRun = false
返回0L；
}
最後介紹了搜索函數的原理。首先，獲取源數組，並將其轉換為DWORD類型。與目標比較，如果同樣的完成不壹樣，交換數據和空間位置，加入二叉樹，搜索下壹個結果，直到沒有下壹步可走。這樣，在找到目標結果之前，函數:
bool cninegrid::ComputeFeel()
{
無符號char * array = m _ iChess
UINT I；
const int MAXSIZE = 362880
無符號字符temparray[9]；
DWORD target，fountain，parentID = 0，child = 1；
ArrayToDword(m_iTargetChess，target)；
ArrayToDword(數組，噴泉)；
if(噴泉==目標)
{
返回false
}
if (m_pScanbuf！=空)
{
delete[]m _ pScanbuf；
}
m _ pScanbuf = new Scanbuf[MAXSIZE]；
AddTree(fountain，m _ pplace list)；
m_pScanbuf[ 0 ]。場所=噴泉；
m_pScanbuf[ 0 ]。ScanID =-1；
clock _ t Tim = clock()；
while(parentID & lt；MAXSIZE & amp& ampchild & ltMAXSIZE)
{
parent = m_pScanbuf[parentID]。地方；
for(I = 0；我& lt4 ;i ++) // 0:上，1:下，2:左，3:右
{
DwordToArray(parent，temparray)；
If (MoveChess(temparray，i)) //移動成功了嗎？
{
ArrayToDword(temparray，fountain)；
If (add tree (fountain，m _ pplace list))//添加搜索次數。
{
m_pScanbuf[ child ]。場所=噴泉；
m_pScanbuf[ child ]。ScanID = parentID
If (fountain == target) //找到結果了嗎？
{
m _ iTime = clock()-Tim；
get path(child)；//計算路徑
FreeTree(m _ pplace list)；
delete[]m _ pScanbuf；
m _ pScanbuf = NULL
返回true
}
child++；
}
}
} //對於I
parentid++；
}
m _ iTime = clock()-Tim；
FreeTree(m _ pplace list)；
delete[]m _ pScanbuf；
m _ pScanbuf = NULL
返回false
}
重要功能介紹完畢；以下是程序的運行結果和操作結果: