八数码问题.docx
《八数码问题.docx》由会员分享，可在线阅读，更多相关《八数码问题.docx（45页珍藏版）》请在冰点文库上搜索。
八数码问题
不同的人，对待资料有不同的态度，说实话，我要的是积分，你呢？
如果你是河工大的学生，那么我是你10级学哥，自己努力，没有什么不行的！
好好学习，天天向上
把数码问题就是把一串数字变成下面这个样子:
123
804
765
实现方法
1.
过程表示
源代码：
#include
staticintstyle[9]={1,2,3,6,7,4,5,8,0};//输入的数码
//2,5,4,3,0,7,1,8,63,2,1,8,0,4,7,6,51,0,4,2,7,3,8,5,61,0,3,8,2,4,7,6,5
staticintarrayStep41[6]={5,4,3,6,7,8};//第四步和第六步共用的数组，所以设为全局量
staticintarrayStep71[4]={3,6,7,4};
staticintlocal;//空格的位置
inti,j;//所用到的变量
intnumber=0;//记录移动步数
voidprint（）;
voidstep1（）;
voidstep2（）;
voidstep3（）;
voidstep4（）;
voidstep5（）;
voidstep6（）;
voidstep7（）;
voidstep8（）;
voidstep9（）;
voidexchange（intx,inty）;
voidjudge（）;
voidjudge（）//判断空格位置
{
number=0;
for（i=0;i<9;i++）
{
if（style[i]==0）
{
local=i;
return;
}
}
}
voidexchange（intx,inty）//交换两个数
{
inttemp;
print（）;
temp=style[x];
style[x]=style[y];
style[y]=temp;
local=y;
number++;
}
voidstep1（）
{
intarrayStep11[5]={3,0,1,2,5};
intarrayStep12[6]={6,7,8,5,2,1};
if（（style[2]!
=0）&&style[2]!
=1）
return;
else
{
if（local==2）
{
if（style[1]==1）
exchange（2,5）;
else
exchange（2,1）;
return;
}
else
{
if（local==4）
{
exchange（4,1）;
i=2;
while（local!
=5）
{
exchange（arrayStep11[i],arrayStep11[i+1]）;
i++;
}
return;
}
for（i=0;i<3;i++）
{
if（arrayStep11[i]==local）
{
while（local!
=5）
{
exchange（arrayStep11[i],arrayStep11[i+1]）;
i++;
}
return;
}
}
for（i=0;i<4;i++）
{
if（arrayStep12[i]==local）
{
while（local!
=1）
{
exchange（arrayStep12[i],arrayStep12[i+1]）;
i++;
}
return;
}
}
}
}
return;
}
voidstep2（）
{
intarrayStep21[8]={0,3,6,7,8,5,4,1};
for（i=0;i<8;i++）
{
if（arrayStep21[i]==local）
{
while（style[0]!
=1）
{
exchange（arrayStep21[i%8],arrayStep21[（i+1）%8]）;
i++;
}
break;
}
}
}
voidstep3（）
{
intarrayStep31[8]={2,1,4,3,6,7,8,5};
for（i=0;i<8;i++）
{
if（arrayStep31[i]==local）
{
while（style[1]!
=2）
{
exchange（arrayStep31[i%8],arrayStep31[（i+1）%8]）;
i++;
}
break;
}
}
}
voidstep4（）
{
for（i=0;i<6;i++）
{
if（arrayStep41[i]==local）
{
while（（style[4]!
=3））
{
exchange（arrayStep41[i%6],arrayStep41[（i+1）%6]）;
i=（i+1）%6;
}
while（local!
=3）
{
exchange（arrayStep41[i%6],arrayStep41[（i+5）%6]）;
i=（i+5）%6;
}
break;
}
}
}
voidstep5（）
{
intarrayStep51[9]={3,0,1,4,5,2,1,0,3};
i=0;
do
{
exchange（arrayStep51[i],arrayStep51[i+1]）;
i++;
}
while（local!
=3）;
}
voidstep6（）
{
for（i=0;i<6;i++）
{
if（arrayStep41[i]==local）
{
while（style[5]!
=4）
{
exchange（arrayStep41[i%6],arrayStep41[（i+1）%6]）;
i++;
}
if（local==8）
exchange（8,7）;
break;
}
}
return;
}
voidstep7（）
{
for（i=0;i<4;i++）
{
if（arrayStep71[i]==local）
{
while（style[4]!
=5）
{
exchange（arrayStep71[i%4],arrayStep71[（i+1）%4]）;
i=（i+1）%4;
}
while（local!
=3）
{
exchange（arrayStep71[i%4],arrayStep71[（i+3）%4]）;
i=（i+3）%4;
}
break;
}
}
}
voidstep8（）
{
intarrayStep81[13]={3,0,1,2,5,4,7,8,5,2,1,0,3};
i=0;
do
{
exchange（arrayStep81[i],arrayStep81[i+1]）;
i++;
}
while（local!
=3）;
}
voidstep9（）
{
for（i=0;i<4;i++）
{
if（arrayStep71[i]==local）
{
while（style[7]!
=6）
{
exchange（arrayStep71[i%4],arrayStep71[（i+1）%4]）;
i=（i+1）%4;
}
while（local!
=4）
{
exchange（arrayStep71[i%4],arrayStep71[（i+3）%4]）;
i=（i+3）%4;
}
break;
}
}
}
voidprint（）
{
for（j=0;j<9;j++）
{
if（style[j]==0）
printf（"\t"）;
else
printf（"%d\t",style[j]）;
if（（j+1）%3==0）
printf（"\n"）;
}
printf（"************%d***********\n",number）;
}
voidloop（）
{
printf（"请输入数码：
\n"）;
for（i=0;i<9;i++）
scanf（"%d",&style[i]）;
judge（）;
step1（）;
step2（）;
step3（）;
if（style[2]!
=3）
{
step4（）;
step5（）;
}
step6（）;
if（style[8]!
=5）
{
step7（）;
step8（）;
}
step9（）;
print（）;
if（!
（（style[3]==8）&&（style[6]==7）））
printf（"用书上所给算法来看此数码错误！
\n"）;
}
voidmain（）
{
while
（1）
loop（）;
}
2.深度优先实现
/***************说明***********************
用宽度优先搜索算法实现八数码问题
******************************************/
#include
#include
#include
#include
#include"string.h"
#include"assert.h"
#include"windows.h"
usingnamespacestd;
intwholeStyle[9]={2,8,3,1,6,4,7,0,5};
intstandard1[9]={1,2,3,8,0,4,7,6,5};
intlocal,i,j;
intstartKey=0,endKey=0,equalKey=1,tempSpace;
structnode*openHead,*open;//open表
structnode*closedHead,*closed;//closed表
structnode*tempNode;//临时节点
structnode*answer;//找到的路径
intnum=0;
structnode
{
intstyle[9];
structnode*next;
structnode*father;
};
voidupdateData（）//更新要判断数据
{
inti;
printf（"请输入八数码原始状态：
\n"）;
for（i=0;i<9;i++）
scanf（"%d",&wholeStyle[i]）;
printf（"请输入八数码最终状态：
\n"）;
for（i=0;i<9;i++）
scanf（"%d",&standard1[i]）;
}
voidjudge1（structnode*head）//判断空格位置
{
for（i=0;i<9;i++）
{
if（head->style[i]==0）
{
local=i;
return;
}
}
}
intjudge2（structnode*head）//判断是否与标准八数码相等，不相等返回值为0
{
for（i=0;i<9;i++）
{
if（head->style[i]!
=standard1[i]）
{
if（（i==3）&&（head->style[3]==standard1[6]））
;
elseif（（i==6）&&（head->style[6]==standard1[3]））
;
else
return0;
}
}
return1;
}
voidjudge3（）//判断新生成的八数码是否就是最终状态或者在open、closed表中出现
{
if（judge2（tempNode））
endKey=1;
else
{
while（openHead->next->next->style[0]!
=9）
{
for（i=0;i<9;i++）
{
if（openHead->next->next->style[i]!
=tempNode->style[i]）
{
equalKey=1;
break;
}
else
equalKey=0;
}
if（equalKey）//不相等
openHead=openHead->next;
else
break;
}
openHead=open->next;
if（equalKey）//不相等
{
while（closedHead->next->style[0]!
=9）
{
for（i=0;i<9;i++）
{
if（closedHead->next->style[i]!
=tempNode->style[i]）
{
equalKey=1;
break;
}
else
equalKey=0;
}
if（!
equalKey）//相等
break;
else
closedHead=closedHead->next;
}
closedHead=closed->next;
}
if（equalKey）//不相等
{
open->next=tempNode;
tempNode->next=openHead;
tempNode->father=openHead->next;
open=open->next;
}
}
}
voidprint（structnode*temp）//输出八数码表
{
for（j=0;j<9;j++）
{
if（temp->style[j]==0）
printf（"\t"）;
else
printf（"%d\t",temp->style[j]）;
if（（j+1）%3==0）
printf（"\n"）;
}
}
voidwrite2txt（）
{
ofstreamout（"F:
\\out_details.txt",ios:
:
app）;
if（out.fail（））
{
cerr<<"未找到文件"<}
out<<"第"<<++num<<"步\n";
out<<"opentable：
\n";
while（openHead->next->style[0]!
=9）
{
for（i=0;i<9;i++）
{
out<next->style[i]<<"\t";
if（（i+1）%3==0）
out<<"\n";
}
out<<"\n";
openHead=openHead->next;
}
openHead=openHead->next;
out<<"*********************\n";
out<<"closedtable：
\n";
while（closedHead->next->style[0]!
=9）
{
for（i=0;i<9;i++）
{
out<next->style[i]<<"\t";
if（（i+1）%3==0）
out<<"\n";
}
out<<"\n";
closedHead=closedHead->next;
}
closedHead=closedHead->next;
out<<"-----------------------------------\n";
out.close（）;
}
voidmain（）
{
//updateData（）;//输入八数码数据
for（i=0;i<9;i++）//判断初始状态是否已经为最终状态
{
if（wholeStyle[i]==standard1[i]）
;
else
{
if（（i==3）&&（wholeStyle[i]==standard1[6]））
;
elseif（（i==6）&&（wholeStyle[i]==standard1[3]））
;
else
{
startKey=1;
break;
}
}
}
if（!
startKey）
{
printf（"不用判断！
\n"）;
return;
}
printf（"要判断！
\n"）;
openHead=newnode（）;
open=newnode（）;
openHead->style[0]=9;
openHead->next=open;
for（i=0;i<9;i++）
open->style[i]=wholeStyle[i];
open->next=openHead;
open->father=openHead;
closedHead=newnode（）;
closed=newnode（）;
closedHead->style[0]=9;
closedHead->next=closedHead;
closed=closedHead;
while（open->style[0]!
=9）//当open表不为空时一直循环
{
judge1（openHead->next）;
if（local%3>0）//右移
{
equalKey=1;
tempNode=newnode（）;
for（i=0;i<9;i++）
tempNode->style[i]=openHead->next->style[i];
tempSpace=tempNode->style[local-1];
tempNode->style[local-1]=tempNode->style[local];
tempNode->style[local]=tempSpace;
judge3（）;
}
if（endKey）
break;
if（local>2）//下移
{
equalKey=1;
tempNode=newnode（）;
for（i=0;i<9;i++）
tempNode->style[i]=openHead->next->style[i];
tempSpace=tempNode->style[local-3];
tempNode->style[local-3]=tempNode->style[local];
tempNode->style[local]=tempSpace;
judge3（）;
}
if（endKey）
break;
if（local%3<2）//左移
{
equalKey=1;
tempNode=newnode（）;
for（i=0;i<9;i++）
tempNode->style[i]=openHead->next->style[i];
tempSpace=tempNode->style[local+1];
tempNode->style[local+1]=tempNode->style[local];
tempNode->style[local]=tempSpace;
judge3（）;
}
if（endKey）
break;
if（local<6）//上移
{
equalKey=1;
tempNode=newnode（）;
//tempNode=malloc（sizeof（structnode））;
for（i=0;i<9;i++）
tempNode->style[i]=openHead->next->style[i];
tempSpace=tempNode->style[local+3];
tempNode->style[local+3]=tempNode->style[local];
tempNode->style[local]=tempSpace;
judge3（）;
}
if（endKey）
break;
closed->next=openHead->next;//把open的标头添加到closed表中
openHead->next=openHead->next->next;
closed=closed->next;
clo
升级会员 