八数码问题：
取一个3*3的矩阵，将1-8(或者任意从小到大的八个数字)，随机分布在矩阵中，留下一个空格(可以用0代替)，作为初始状态；再去一个3*3的矩阵，将1-8(或者任意从小到大的八个数字，其取值必须与初始状态相同)，随机分布在矩阵中，留下一个空格(可以用0代替)，作为目标状态；对初始状态进行操作，其允许的操作是：将空格向上，下，左，右移动(即将空格与周边的数字进行交换)，操作初始状态的矩阵，在若干步后达目标状态。求解其过程为八数码问题。如图：
八数码问题
八数码问题的有解条件：
将矩阵从上到下从左到右的顺序分布成一个数列，并去掉空格，例如：
2 8 3 (0为空格) 分布成数列后：
1 0 4 2 8 3 1 4 7 6 5
7 6 5
如果此初始状态的数列(矩阵)的逆序数与目标状态的数列(矩阵)的逆序数的奇偶性一样，则此问题有解。
逆序数的定义：
有一个数列，在这个数列中任意取一对数字(两个数字)，其两个数字在数列中的(从前到后)顺序与数字数值的大小相反，称其为一个逆序。这个数列中所有的逆序的和为逆序数。
证明：
空格向左右移动时，不改变逆序数的大小；空格向上下移动时，会改变逆序数，改变的幅度为±2或者0 (1)。所以±2或者0的改变幅度不会对逆序数造成奇偶性的改变。所以如果两个矩阵状态如果能互相到达，则必须有其逆序数的奇偶性一样。
(1) 在矩阵中操作空格上下移动时，在数列中的表现是将被交换的数字提前到他前面两个数字之前或者推后到他后面两个数字之后；例如，被交换的数字的下标是 Z 的话，空格向下移动(即被交换数向上移动)后，被交换数在数列中的位置是 Z-2 ；空格向上移动(即被交换数向下移动)后，则被交换数在数列中的位置是 Z+2。这种交换不会影响到被交换数与被它跨过的两个数以外的数字的顺序。比如说：被交换数的位置 Z ，如果空格向上移动，被交换数位置变成 Z+2，但是Z-1处的数字 与 Z 的顺序没有因为 Z 变成 Z+2 而失去了Z-1 在 Z 的前面的顺序，Z-1在Z前面，也在Z+2前面，同样的，Z变成Z+2也不会改变Z与Z+3的顺序。并且，如果有顺序 2 3 4 ，这个顺序的逆序数为0，如果我把4放到2 3前面，变成4 2 3，其逆序数就变成了+2，逆序数就增长了2；如果有顺序 4 2 3，其逆序数为+2，如果我把4放到2 3后面，变成2 3 4，其逆序数就变成了0，逆序数减少了2；如果有6 4 5，其逆序数为+2，如果我把5放在6 4 的前面，变成5 6 4，其逆序数为2，逆序数改变为0。所以改变的幅度为±2，或者0。
八数码问题的解法以及算法(宽度优先)：
解法：
空格可以上下左右移动，则父状态可以衍生出若干个子状态(考虑其空格不能越3*3的界以及其不返回到父状态或者父父状态等等之类的情况的话，最大的子状态数量为4 最小为0)，这种思路的话实际上这个问题就是一个树的搜索问题，所以用搜索的算法可以解决。
算法(宽度优先)：
(1)判断初始状态与目标状态的逆序数的奇偶性来判断是否有解
(2)建立一个OPEN表(队列)，用于存放待展开子节点(状态)的父节点
(3)建立一个CLOSED表(队列)，用于存放已经展开了子节点的父节点
(4)将初始状态放到OPEN表中，作为第一个
(5)将OPEN表中第一个节点取出(并在OPEN表中删除这个节点)，放到CLOSED表中，排在CLOSED表中最后一个，整理好OPEN表
(6)把CLOSED表最后一个节点按照条件(不越界，不返回到父节点)展开其子节点，并且将可能的子节点按照顺序存入OPEN表中
(7)判断此父节点是否为目标状态：
①是，退出，打印答案
②不是，回到步骤(4)
问题：
(1)如果不用数字，而是用毫无关系的符号来填充矩阵，怎么判断是否有解呢？
想法：将初始状态作为参考，将其不同的符号的顺序作为其符号的值的大小，计算出初始状态的逆序数为0，按照初始状态的值大小来判断目标状态的逆序数，然后判断奇偶性进而判断是否有解。
#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表表头父节点放到closed表中
CopyMatrix(c_table[c_table_hand].c_son,o_table[0].o_son); // 将open表表头子节点放到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[]) //用于实现将open表的表头提出来后整理表的功能，
{ //最后返回一个open表的最后节点的下标值。
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[]) //开点函数，将closed表的待开点节点在此开点
{
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表中出现过，出现过就不将此扩展节点放入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表示没有出现过，可以放入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 //出现过，不放入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表中出现过，出现过就不将此扩展节点放入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表示没有出现过，可以放入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 //出现过，不放入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表中出现过，出现过就不将此扩展节点放入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表示没有出现过，可以放入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 //出现过，不放入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表中出现过，出现过就不将此扩展节点放入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表示没有出现过，可以放入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 //出现过，不放入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);
}
}
}
