奥鹏大连理工大学远程与继续教育学院《人工智能》课程设计

大连理工大学远程与继续教育学院《人工智能》课程设计

return 0; else {

num[i]=num[i-1]; num[i-1]=0; return 1; } }

//空格向右移

int move_right(int num[9]) {

for (int i=0;i<9;i++) if (num[i]==0) break;

if (i==2||i==5||i==8) return 0; else {

num[i]=num[i+1]; num[i+1]=0; return 1; } }

//判断可否解出

int icansolve(int num[9],int target[9]) {

int i,j;

int count_num,count_target; for (i=0;i<9;i++) for (j=0;j

if(num[j]

if(target[j]

if((count_num+count_target)%2 == 0) return 1; else

return 0; }

//判断有无重复

int existed(int num[9],eight_num *where) {

大连理工大学远程与继续教育学院《人工智能》课程设计

eight_num *p;

for(p=where;p!=NULL;p=p->parent) if(*p==num) return 1; return 0; }

//寻找估价函数最小的叶子节点

eight_num* find_OK_leaf(eight_num* start) {

eight_num *p,*OK; p=OK=start;

int min=start->get_evafun();

for(p=start;p!=NULL;p=p->leaf_next) if(min>p->get_evafun()) {

OK=p;

min=p->get_evafun(); }

return OK; }

//主函数开始 int main(void) {

double time;

clock_t Start,Finish; int memery_used=0,step=0; int num[9];

int flag=0;//是否输入错误标志，1表示输入错误 int bingo=0;//是否查找成功标志，1表示成功 int i,j;

cout<<\ for (i=0;i<9;i++) {

flag=0;

cin>>num[i]; for(j=0;j

if(num[i]==num[j]) flag=1;

if (num[i]<0||num[i]>8||flag==1) {

i--;

cout<<\ } }

大连理工大学远程与继续教育学院《人工智能》课程设计

eight_num S(num),Target(target);

S.parent=S.leaf_next=S.leaf_pre=NULL; S.cul_para(); memery_used++;

cout<<\S.show();

cout<<\Target.show();

if(!icansolve(num,target)) {

cout<<\ cin>>i; return 1; }

Start=clock( );

eight_num *OK_leaf=&S,*leaf_start=&S,*new_8num,*p; while(OK_leaf!=NULL&&bingo!=1) {

OK_leaf=find_OK_leaf(leaf_start); if(*OK_leaf==Target) {

bingo=1; break; }

p=OK_leaf->leaf_pre;

OK_leaf->get_numbers_to(num);

if(move_up(num)&&!existed(num,OK_leaf)) {

new_8num=new eight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL)

leaf_start=new_8num; else

p->leaf_next=new_8num; p=new_8num; memery_used++; }

OK_leaf->get_numbers_to(num);

if(move_down(num)&&!existed(num,OK_leaf)) {

new_8num=new eight_num;

大连理工大学远程与继续教育学院《人工智能》课程设计

new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL)

leaf_start=new_8num; else

p->leaf_next=new_8num; p=new_8num; memery_used++; }

OK_leaf->get_numbers_to(num);

if(move_left(num)&&!existed(num,OK_leaf)) {

new_8num=new eight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL)

leaf_start=new_8num; else

p->leaf_next=new_8num; p=new_8num; memery_used++; }

OK_leaf->get_numbers_to(num);

if(move_right(num)&&!existed(num,OK_leaf)) {

new_8num=new eight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL)

leaf_start=new_8num; else

p->leaf_next=new_8num; p=new_8num; memery_used++; }

p->leaf_next=OK_leaf->leaf_next; if(OK_leaf->leaf_next!=NULL)

OK_leaf->leaf_next->leaf_pre=p;

大连理工大学远程与继续教育学院《人工智能》课程设计

OK_leaf->leaf_next=OK_leaf->leaf_pre=NULL; }

Finish=clock( ); if(bingo==1) {

time = (double)(Finish-Start)*1000/CLOCKS_PER_SEC; eight_num *p;

for (p=OK_leaf->parent;p!=NULL;p=p->parent) {

cout<<\ p->show(); step++; }

cout<<\ cout<

cout<<\ cout<

cout<<\

return 0; }