你给的这个例子貌似无解，下面是用a*算法写的八数码程序代码，当然也可以用广搜来做
a*算法求解八数码问题
估价函数选择不在位数与当前结点深度之和
123456780->271853406(step=17)约52s
include
include
using namespace std;typedef struct node
{
char data[9];int depth,not_in_pos;node*father,*pre,*next;}tstat;int step=0;统计总共走了多少步
tstat*get_eva_function(tstat*start)/返回估价函数最小的结点
{
tstat*i,*p;int min,eva;i=p=start;min=eva=i->not_in_pos+i->depth;for;i;i=i->next)
{
eva=i->not_in_pos+i->depth;if(min>eva)
{
min=eva;p=i;}
}
return(p);}
tstat*create_data()/创建数据
{
tstat*st=new tstat;string s;int i,j,slen=0;bool b;cin>>s;while(s[slen])slen+;if(slen!9)
{
cout输入错误!return(**);}
for(i=0;i;i+)
{
st->data[i]=s[i];b=true;for(j=0;j;j+)
if(st->data[i]=st->data[j])
{
b=false;break;}
if!(st->data[i]>='0'&st->data[i])|!b))
{
cout输入错误!return(**);}
}
st->depth=0;st->father=st->pre=st->next=**;return(st);}
bool cansolve(tstat*st,tstat*ta)/判断是否有解,根据逆序数奇偶性相同否判断
{
int i,j,num_st=0,num_ta=0;for(i=0;i;i+)
for(j=0;j;j+)
{
if(st->data[j]<st->data[i]&st->data[j]!'0')
num_st+;if(ta->data[j]<ta->data[i]&ta->data[j]!'0')
num_ta+;}
num_st=num_st-(num_st/2)*2;num_ta=num_ta-(num_ta/2)*2;if((num_st=0&num_ta=0)|(num_st=1&num_ta=1))
return(true);else
{
cout无解!return(false);}
}
void print_stat(tstat*st)/格式化输出状态结点中数据
{
int i,j;for(i=0;i;i+)
{
for(j=0;j;j+)
cout<<st->data[i*3+j];cout;}
}
void print_data(tstat*st)/输出函数
{
if(st)
{
print_data(st->father);cout;cout;print_stat(st);cout;}
}
bool **same(tstat*st1,tstat*st2)/判断st1和st2是否相同
{
int i;bool b=true;for(i=0;i;i+)
if(st1->data[i]!st2->data[i])
{
b=false;break;}
return(b);}
bool **ok(tstat*st,tstat*pos)/判断st是否出现过
{
tstat*p;bool b=true;for(p=pos;p;p=p->father)
if(st->data=p->data)
{
b=false;break;}
return(b);}
int find0(tstat*st)/返回0所在位置
{
int i,pos;for(i=0;i;i+)
if(st->data[i]='0')
{
pos=i;break;}
return(pos);}
int get_nip(tstat*st,tstat*ta)/计算not_in_pos值
{
int i,nip=0;for(i=0;i;i+)
if(st->data[i]!ta->data[i])
nip+;return(nip);}
tstat*calc_path(tstat*start,tstat*target)/寻找路径,返回找到后的目标结点
{
tstat*p,*q,*r,*st=start;int zpos,i;char tch;p=st;while((p)&!**same(p,target)))
{
r=p->pre;zpos=find0(p);if(zpos!0&zpos!3&zpos!6)/左移
{
if!(q=new tstat))
{
cout内存分配失败!\n;return(**);}
for(i=0;i;i+)q->data[i]=p->data[i];tch=q->data[zpos];q->data[zpos]=q->data[zpos-1];q->data[zpos-1]=tch;q->depth=p->depth+1;q->father=p;q->pre=r;q->next=**;q->not_in_pos=get_nip(q,target);if(**ok(q,p))
{
if(r)
r->next=q;else
st=q;r=q;}
else
delete q;}
if(zpos!2&zpos!5&zpos!8)/右移
{
if!(q=new tstat))
{
cout内存分配失败!\n;return(**);}
for(i=0;i;i+)q->data[i]=p->data[i];tch=q->data[zpos];q->data[zpos]=q->data[zpos+1];q->data[zpos+1]=tch;q->depth=p->depth+1;q->father=p;q->pre=r;q->next=**;q->not_in_pos=get_nip(q,target);if(**ok(q,p))
{
if(r)
r->next=q;else
st=q;r=q;}
else
delete q;}
if(zpos!0&zpos!1&zpos!2)/上移
{
if!(q=new tstat))
{
cout内存分配失败!\n;return(**);}
for(i=0;i;i+)q->data[i]=p->data[i];tch=q->data[zpos];q->data[zpos]=q->data[zpos-3];q->data[zpos-3]=tch;q->depth=p->depth+1;q->father=p;q->pre=r;q->next=**;q->not_in_pos=get_nip(q,target);if(**ok(q,p))
{
if(r)
r->next=q;else
st=q;r=q;}
else
delete q;}
if(zpos!6&zpos!7&zpos!8)/下移
{
if!(q=new tstat))
{
cout内存分配失败!\n;return(**);}
for(i=0;i;i+)q->data[i]=p->data[i];tch=q->data[zpos];q->data[zpos]=q->data[zpos+3];q->data[zpos+3]=tch;q->depth=p->depth+1;q->father=p;q->pre=r;q->next=**;q->not_in_pos=get_nip(q,target);if(**ok(q,p))
{
if(r)
r->next=q;else
st=q;r=q;}
else
delete q;}
r->next=p->next;if(p->next)
p->next->pre=r;p->pre=p->next=**;p=get_eva_function(st);}
return(p);}
int main()/主函数
{
tstat*start,*target,*p;cout请输入初始状态(0~8,0为空):";if(start=create_data())
{
cout请输入目标状态(0~8,0为空):";if(target=create_data())
{
if(cansolve(start,target))
{
if(p=calc_path(start,target))
print_data(p);}
}
}
return(0);} 展开