八數(shù)碼問題：
取一個3*3的矩陣，將1-8(或者任意從小到大的八個數(shù)字)，隨機分布在矩陣中，留下一個空格(可以用0代替)，作為初始狀態(tài)；再去一個3*3的矩陣，將1-8(或者任意從小到大的八個數(shù)字，其取值必須與初始狀態(tài)相同)，隨機分布在矩陣中，留下一個空格(可以用0代替)，作為目標狀態(tài)；對初始狀態(tài)進行操作，其允許的操作是：將空格向上，下，左，右移動(即將空格與周邊的數(shù)字進行交換)，操作初始狀態(tài)的矩陣，在若干步后達目標狀態(tài)。求解其過程為八數(shù)碼問題。如圖：
八數(shù)碼問題的有解條件：
將矩陣從上到下從左到右的順序分布成一個數(shù)列，并去掉空格，例如：
2 8 3 (0為空格) 分布成數(shù)列后：
1 0 4 ????2 8 3 1 4 7 6 5
7 6 5
如果此初始狀態(tài)的數(shù)列(矩陣)的逆序數(shù)與目標狀態(tài)的數(shù)列(矩陣)的逆序數(shù)的奇偶性一樣，則此問題有解。
逆序數(shù)的定義：
有一個數(shù)列，在這個數(shù)列中任意取一對數(shù)字(兩個數(shù)字)，其兩個數(shù)字在數(shù)列中的(從前到后)順序與數(shù)字數(shù)值的大小相反，稱其為一個逆序。這個數(shù)列中所有的逆序的和為逆序數(shù)。
證明：
空格向左右移動時，不改變逆序數(shù)的大?。豢崭裣蛏舷乱苿訒r，會改變逆序數(shù)，改變的幅度為±2或者0 (1)。所以±2或者0的改變幅度不會對逆序數(shù)造成奇偶性的改變。所以如果兩個矩陣狀態(tài)如果能互相到達，則必須有其逆序數(shù)的奇偶性一樣。
(1) 在矩陣中操作空格上下移動時，在數(shù)列中的表現(xiàn)是將被交換的數(shù)字提前到他前面兩個數(shù)字之前或者推后到他后面兩個數(shù)字之后；例如，被交換的數(shù)字的下標是 Z 的話，空格向下移動(即被交換數(shù)向上移動)后，被交換數(shù)在數(shù)列中的位置是 Z-2 ；空格向上移動(即被交換數(shù)向下移動)后，則被交換數(shù)在數(shù)列中的位置是 Z+2。這種交換不會影響到被交換數(shù)與被它跨過的兩個數(shù)以外的數(shù)字的順序。比如說：被交換數(shù)的位置 Z ，如果空格向上移動，被交換數(shù)位置變成 Z+2，但是Z-1處的數(shù)字 與 Z 的順序沒有因為 Z 變成 Z+2 而失去了Z-1 在 Z 的前面的順序，Z-1在Z前面，也在Z+2前面，同樣的，Z變成Z+2也不會改變Z與Z+3的順序。并且，如果有順序 2 3 4 ，這個順序的逆序數(shù)為0，如果我把4放到2 3前面，變成4 2 3，其逆序數(shù)就變成了+2，逆序數(shù)就增長了2；如果有順序 4 2 3，其逆序數(shù)為+2，如果我把4放到2 3后面，變成2 3 4，其逆序數(shù)就變成了0，逆序數(shù)減少了2；如果有6 4 5，其逆序數(shù)為+2，如果我把5放在6 4 的前面，變成5 6 4，其逆序數(shù)為2，逆序數(shù)改變?yōu)?。所以改變的幅度為±2，或者0。
八數(shù)碼問題的解法以及算法(寬度優(yōu)先)：
解法：
空格可以上下左右移動，則父狀態(tài)可以衍生出若干個子狀態(tài)(考慮其空格不能越3*3的界以及其不返回到父狀態(tài)或者父父狀態(tài)等等之類的情況的話，最大的子狀態(tài)數(shù)量為4 最小為0)，這種思路的話實際上這個問題就是一個樹的搜索問題，所以用搜索的算法可以解決。
算法(寬度優(yōu)先)：
(1)判斷初始狀態(tài)與目標狀態(tài)的逆序數(shù)的奇偶性來判斷是否有解
(2)建立一個OPEN表(隊列)，用于存放待展開子節(jié)點(狀態(tài))的父節(jié)點
(3)建立一個CLOSED表(隊列)，用于存放已經展開了子節(jié)點的父節(jié)點
(4)將初始狀態(tài)放到OPEN表中，作為第一個
(5)將OPEN表中第一個節(jié)點取出(并在OPEN表中刪除這個節(jié)點)，放到CLOSED表中，排在CLOSED表中最后一個，整理好OPEN表
(6)把CLOSED表最后一個節(jié)點按照條件(不越界，不返回到父節(jié)點)展開其子節(jié)點，并且將可能的子節(jié)點按照順序存入OPEN表中
(7)判斷此父節(jié)點是否為目標狀態(tài)：
?①是，退出，打印答案
?②不是，回到步驟(4)
問題：
(1)如果不用數(shù)字，而是用毫無關系的符號來填充矩陣，怎么判斷是否有解呢？
想法：將初始狀態(tài)作為參考，將其不同的符號的順序作為其符號的值的大小，計算出初始狀態(tài)的逆序數(shù)為0，按照初始狀態(tài)的值大小來判斷目標狀態(tài)的逆序數(shù)，然后判斷奇偶性進而判斷是否有解。
#include
class open //open表
{
public:
int o_father[3][3],o_son[3][3];
};
class closed //closed表
{
public:
int c_father[3][3],c_son[3][3];
};
void printmatrix(int matrix[][3])
{
int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++) printf("%d ",matrix[i][j]);
printf("\n");
}
printf("\n");
}
int MatrixCompare(int Matrix1[][3],int Matrix2[][3]);
int Judgement(int matrix1[][3],int matrix2[][3]);
void printanwser(closed c_table[]);
void MoveOpenTable(open o_table[]);
void CopyMatrix(int matrix1[][3],int matrix2[][3]);
void GiveupMove(int matrix[][3],int,int,int);
void MoveMatrix(int matrix[][3],int,int,int);
void OpenPoint(open o_table[],closed c_table[]);
int o_table_hand=0,c_table_hand=-1;
int main()
{
int NowMatrix[3][3]={{2,8,3},{1,0,4},{7,6,5}},GoalMatrix[3][3]={{1,2,3},{8,0,4},{7,6,5}};
int i,j,z;
open o_table[5000];
closed c_table[5000];
if(Judgement(NowMatrix,GoalMatrix))
{
printf("無解\n");
return 0;
}
CopyMatrix(o_table[o_table_hand].o_son,NowMatrix); //將初始矩陣放入open表中
o_table_hand++;
do
{
c_table_hand++;
CopyMatrix(c_table[c_table_hand].c_father,o_table[0].o_father); // 將open表表頭父節(jié)點放到closed表中
CopyMatrix(c_table[c_table_hand].c_son,o_table[0].o_son); // 將open表表頭子節(jié)點放到closed表中
MoveOpenTable(o_table);
OpenPoint(o_table,c_table);
}
while(MatrixCompare(GoalMatrix,c_table[c_table_hand].c_son));
printf("有解:\n");
printanwser(c_table);
return 0;
}
int Judgement(int matrix1[][3],int matrix2[][3])
{
int i,j,z1[9],z2[9],record1=0,record2=0;
z1[0]=matrix1[0][0];
z1[1]=matrix1[0][1];
z1[2]=matrix1[0][2];
z1[3]=matrix1[1][0];
z1[4]=matrix1[1][1];
z1[5]=matrix1[1][2];
z1[6]=matrix1[2][0];
z1[7]=matrix1[2][1];
z1[8]=matrix1[2][2];
z2[0]=matrix2[0][0];
z2[1]=matrix2[0][1];
z2[2]=matrix2[0][2];
z2[3]=matrix2[1][0];
z2[4]=matrix2[1][1];
z2[5]=matrix2[1][2];
z2[6]=matrix2[2][0];
z2[7]=matrix2[2][1];
z2[8]=matrix2[2][2];
for(i=0;i<9;i++)
for(j=i+1;j<9;j++)
if(z1[i]>z1[j]) record1++;
for(i=0;i<9;i++)
for(j=i+1;j<9;j++)
if(z2[i]>z2[j]) record2++;
if(record1%2==record2%2) return 0;
else return 1;
}
void CopyMatrix(int matrix1[][3],int matrix2[][3]) //復制矩陣，將矩陣2(matrix2)的矩陣復制進矩陣1(matrix1)
{
matrix1[0][0]=matrix2[0][0];
matrix1[0][1]=matrix2[0][1];
matrix1[0][2]=matrix2[0][2];
matrix1[1][0]=matrix2[1][0];
matrix1[1][1]=matrix2[1][1];
matrix1[1][2]=matrix2[1][2];
matrix1[2][0]=matrix2[2][0];
matrix1[2][1]=matrix2[2][1];
matrix1[2][2]=matrix2[2][2];
}
int MatrixCompare(int Matrix1[][3],int Matrix2[][3]) //判定兩個矩陣是否一樣
{
int i,j,record=0;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(Matrix1[i][j]!=Matrix2[i][j]) return 1; //矩陣不同返回1
return 0; //矩陣相同返回0
}
void MoveOpenTable(open o_table[]) //用于實現(xiàn)將open表的表頭提出來后整理表的功能，
{ //最后返回一個open表的最后節(jié)點的下標值。
int i;
for(i=0;i
{
CopyMatrix(o_table[i].o_father,o_table[i+1].o_father);
CopyMatrix(o_table[i].o_son,o_table[i+1].o_son);
}
o_table_hand--;
}
void MoveMatrix(int matrix[][3],int zeroseat1,int zeroseat2,int swi) //對矩陣進行操作
{
switch(swi)
{
case 1: //向上移動空格
{
matrix[zeroseat1][zeroseat2]=matrix[zeroseat1-1][zeroseat2];
matrix[zeroseat1-1][zeroseat2]=0;
break;
}
case 2: //向右移動空格
{
matrix[zeroseat1][zeroseat2]=matrix[zeroseat1][zeroseat2+1];
matrix[zeroseat1][zeroseat2+1]=0;
break;
}
case 3: //向下移動空格
{
matrix[zeroseat1][zeroseat2]=matrix[zeroseat1+1][zeroseat2];
matrix[zeroseat1+1][zeroseat2]=0;
break;
}
case 4: //向左移動空格
{
matrix[zeroseat1][zeroseat2]=matrix[zeroseat1][zeroseat2-1];
matrix[zeroseat1][zeroseat2-1]=0;
break;
}
}
}
void GiveupMove(int matrix[][3],int zeroseat1,int zeroseat2,int swi)
{
switch(swi)
{
case 1: //撤銷向上移動空格
{
matrix[zeroseat1][zeroseat2]=matrix[zeroseat1+1][zeroseat2];
matrix[zeroseat1+1][zeroseat2]=0;
break;
}
case 2: //撤銷向右移動空格
{
matrix[zeroseat1][zeroseat2]=matrix[zeroseat1][zeroseat2-1];
matrix[zeroseat1][zeroseat2-1]=0;
break;
}
case 3: //撤銷向下移動空格
{
matrix[zeroseat1][zeroseat2]=matrix[zeroseat1-1][zeroseat2];
matrix[zeroseat1-1][zeroseat2]=0;
break;
}
case 4: //撤銷向左移動空格
{
matrix[zeroseat1][zeroseat2]=matrix[zeroseat1][zeroseat2+1];
matrix[zeroseat1][zeroseat2+1]=0;
break;
}
}
}
void OpenPoint(open o_table[],closed c_table[]) //開點函數(shù)，將closed表的待開點節(jié)點在此開點
{
int zeroseat1,zeroseat2,i,j,z,record=0;
int NowMatrix[3][3];
for(i=0;i<3;i++) //找到矩陣的 0的位置
for(j=0;j<3;j++)
if(c_table[c_table_hand].c_son[i][j]==0)
{
zeroseat1=i;
zeroseat2=j;
}
CopyMatrix(NowMatrix,c_table[c_table_hand].c_son); //把矩陣復制到臨時矩陣中
if(zeroseat1-1>-1) //判斷向上走是否能走
{
MoveMatrix(NowMatrix,zeroseat1,zeroseat2,1); //將矩陣進行空格移動操作
zeroseat1--;
for(i=c_table_hand;i>=0;i--) //判斷移動后的矩陣是否在closed表中出現(xiàn)過，出現(xiàn)過就不將此擴展節(jié)點放入open表
{
z=MatrixCompare(c_table[i].c_son,NowMatrix);
if(z==1) record++;
else record=0;
}
if(record==c_table_hand+1) //record==c_table_hand表示沒有出現(xiàn)過，可以放入open表后撤回移動步驟
{
CopyMatrix(o_table[o_table_hand].o_father,c_table[c_table_hand].c_son);
CopyMatrix(o_table[o_table_hand].o_son,NowMatrix);
o_table_hand++;
GiveupMove(NowMatrix,zeroseat1,zeroseat2,1);
zeroseat1++;
record=0;
}
else //出現(xiàn)過，不放入open表中，撤回移動步驟
{
GiveupMove(NowMatrix,zeroseat1,zeroseat2,1);
zeroseat1++;
record=0;
}
}
if(zeroseat2+1<3) //判斷向右走是否能走
{
MoveMatrix(NowMatrix,zeroseat1,zeroseat2,2); //將矩陣進行空格移動操作
zeroseat2++;
for(i=c_table_hand;i>=0;i--) //判斷移動后的矩陣是否在closed表中出現(xiàn)過，出現(xiàn)過就不將此擴展節(jié)點放入open表
{
z=MatrixCompare(c_table[i].c_son,NowMatrix);
if(z==1) record++;
else record=0;
}
if(record==c_table_hand+1) //record==c_table_hand表示沒有出現(xiàn)過，可以放入open表后撤回移動步驟
{
CopyMatrix(o_table[o_table_hand].o_father,c_table[c_table_hand].c_son);
CopyMatrix(o_table[o_table_hand].o_son,NowMatrix);
o_table_hand++;
GiveupMove(NowMatrix,zeroseat1,zeroseat2,2);
zeroseat2--;
record=0;
}
else //出現(xiàn)過，不放入open表中，撤回移動步驟
{
GiveupMove(NowMatrix,zeroseat1,zeroseat2,2);
zeroseat2--;
record=0;
}
}
if(zeroseat1+1<3) //判斷向下走是否能走
{
MoveMatrix(NowMatrix,zeroseat1,zeroseat2,3); //將矩陣進行空格移動操作
zeroseat1++;
for(i=c_table_hand;i>=0;i--) //判斷移動后的矩陣是否在closed表中出現(xiàn)過，出現(xiàn)過就不將此擴展節(jié)點放入open表
{
z=MatrixCompare(c_table[i].c_son,NowMatrix);
if(z==1) record++;
else record=0;
}
if(record==c_table_hand+1) //record==c_table_hand表示沒有出現(xiàn)過，可以放入open表后撤回移動步驟
{
CopyMatrix(o_table[o_table_hand].o_father,c_table[c_table_hand].c_son);
CopyMatrix(o_table[o_table_hand].o_son,NowMatrix);
o_table_hand++;
GiveupMove(NowMatrix,zeroseat1,zeroseat2,3);
zeroseat1--;
record=0;
}
else //出現(xiàn)過，不放入open表中，撤回移動步驟
{
GiveupMove(NowMatrix,zeroseat1,zeroseat2,3);
zeroseat1--;
record=0;
}
}
if(zeroseat2-1>-1) //判斷向下走是否能走
{
MoveMatrix(NowMatrix,zeroseat1,zeroseat2,4); //將矩陣進行空格移動操作
zeroseat2--;
for(i=c_table_hand;i>=0;i--) //判斷移動后的矩陣是否在closed表中出現(xiàn)過，出現(xiàn)過就不將此擴展節(jié)點放入open表
{
z=MatrixCompare(c_table[i].c_son,NowMatrix);
if(z==1) record++;
else record=0;
}
if(record==c_table_hand+1) //record==c_table_hand表示沒有出現(xiàn)過，可以放入open表后撤回移動步驟
{
CopyMatrix(o_table[o_table_hand].o_father,c_table[c_table_hand].c_son);
CopyMatrix(o_table[o_table_hand].o_son,NowMatrix);
o_table_hand++;
GiveupMove(NowMatrix,zeroseat1,zeroseat2,4);
zeroseat2++;
record=0;
}
else //出現(xiàn)過，不放入open表中，撤回移動步驟
{
GiveupMove(NowMatrix,zeroseat1,zeroseat2,4);
zeroseat2++;
record=0;
}
}
}
void printanwser(closed c_table[])
{
int NowMatrix[3][3],i,z;
printmatrix(c_table[c_table_hand].c_son);
CopyMatrix(NowMatrix,c_table[c_table_hand].c_father);
for(i=c_table_hand;i>=0;i--)
{
z=MatrixCompare(NowMatrix,c_table[i].c_son);
if(z==0)
{
printmatrix(NowMatrix);
CopyMatrix(NowMatrix,c_table[i].c_father);
}
}
}
