九宫格程序c++人工智能

#include"NineGrid.h" NineGrid::NineGrid(Graph startGrid,Graph endGrid) { m_start=startGrid; m_start.layer=1; m_start.flag=1; m_end=endGrid; Open=new DllNode; Open->data=m_start; Open->data.father=NULL; Open->next=NULL; Open->before=NULL; Closed=NULL; pop=NULL; } NineGrid::~NineGrid() { DllNode *Scan=Open; DllNode *Scan_delete; for(int i=0;i<2;i++) { while(Scan!=NULL) { Scan_delete=Scan; Scan=Scan->next; delete Scan_delete; } Scan=Closed; } } bool NineGrid::IsSuccess() { for(int i=1;i<=9;i++) if(pop->data.grids[i]!=m_end.grids[i]) return false; return true; } void NineGrid::CreateChildren(Graph child[4]) { Graph mid_child; int mid_num; mid_num=pop->data.grids[0]; for(int i=0;i<4;i++) { mid_child=pop->data; switch(i) { case 0: if(mid_num%3==1) mid_child.flag=DisableGraph; else { mid_child.grids[0]=mid_num-1; mid_child.grids[mid_num]=mid_child.grids[mid_num-1]; mid_child.grids[mid_num-1]=0; } break; case 1: if(mid_num%3==0) mid_child.flag=DisableGraph; else { mid_child.grids[0]=mid_num+1; mid_child.grids[mid_num]=mid_child.grids[mid_num+1]; mid_child.grids[mid_num+1]=0; } break; case 2: if(mid_num==1||mid_num==2||mid_num==3) mid_child.flag=DisableGraph; else { mid_child.grids[0]=mid_num-3; mid_child.grids[mid_num]=mid_child.grids[mid_num-3]; mid_child.grids[mid_num-3]=0; } break; case 3: if(mid_num==7||mid_num==8||mid_num==9) mid_child.flag=DisableGraph; else { mid_child.grids[0]=mid_num+3; mid_child.grids[mid_num]=mid_child.grids[mid_num+3]; mid_child.grids[mid_num+3]=0; } break; } child[i]=mid_child; if(child[i].flag!=DisableGraph) { child[i].father=&(pop->data); child[i].layer=child[i].layer+1; child[i].flag=f_function(child[i]); } } } /* void NineGrid::CreateChildren(Graph child[4]) { Graph mid_child; int blank=pop->data.grids[0]; int way=0; for(int i=0;i<=3;i++)//??????,???????????4???????4???, //?????,???????????(????) { mid_child=pop->data; switch(way) { case 0 : //up if (blank<=6) { mid_child.grids[blank]=mid_child.grids[blank+3]; mid_child.grids[blank+3]=0; mid_child.grids[0]=blank+3; } else mid_child.flag=DisableGraph; break; case 1 : //down if (blank>3) { mid_child.grids[blank]=mid_child.grids[blank-3]; mid_child.grids[blank-3]=0; mid_child.grids[0]=blank-3; } else mid_child.flag=DisableGraph; break; case 2 : //left if (blank%3==1||blank%3==2)//?????2? { mid_child.grids[blank]=mid_child.grids[blank+1]; mid_child.grids[blank+1]=0; mid_child.grids[0]=blank+1; } else mid_child.flag=DisableGraph; break; case 3 : //right if (blank%3==2||blank%3==0)//?????2? { mid_child.grids[blank]=mid_child.grids[blank-1]; mid_child.grids[blank-1]=0; mid_child.grids[0]=blank-1; } else mid_child.flag=DisableGraph; break; default: break; } if (mid_child.flag!=DisableGraph)//?????? { if(mid_child.grids[0]==pop->data.father->grids[0]) mid_child.flag=DisableGraph;//???????????????? else { mid_child.layer=pop->data.layer+1; mid_child.flag=f_function(mid_child); mid_child.father=&pop->data; } } child[i]=mid_child; way++; } } */ void NineGrid::Extend_Open(Graph child[4]) { for(int i=0;i<4;i++) { if(child[i].flag==DisableGraph) continue; DllNode * thesame; bool judge=true; bool test=Compare(child[i],thesame); if(test) { if((thesame->data.flag)>child[i].flag) { thesame->data.father=child[i].father; thesame->data.flag=child[i].flag; thesame->data.layer=child[i].layer; if(thesame==Open) { Open=Open->next; Open->before=NULL; thesame->next=NULL; } else { (thesame->before)->next=thesame->next; (thesame->next)->before=thesame->before; } } else judge=false; } else { thesame=new DllNode; thesame->data=child[i]; } // DllNode * scan=Open; if(judge) { if(Open!=NULL) { if(Open->data.flag>=thesame->data.flag) { Open->before=thesame; thesame->next=Open; Open=thesame; } else { bool insert=false; DllNode * scan=Open; DllNode * Last; while(scan!=NULL) { if(scan->data.flag>=thesame->data.flag) { thesame->before=scan->before; thesame->next=scan; scan->before->next=thesame; scan->before=thesame; insert=true; break; } Last=scan; scan=scan->next; } if(!insert) { thesame->before=Last; Last->next=thesame; thesame->next=NULL; } } } else { Open=thesame; Open->before=NULL; Open->next=NULL; } } } } bool NineGrid::PopOpen() { if(Open==NULL) return false; if(Open->next==NULL) { if(Closed==NULL) Closed=Open; else { Closed->before=Open; Open->next=Closed; Closed=Open; } Open=NULL; } else { Open=Open->next; if(Closed==NULL) { Closed=Open->before; Closed->before=NULL; Closed->next=NULL; Open->before=NULL; } else { Closed->before=Open->before; Open->before->next=Closed; Closed=Open->before; Open->before=NULL; } } pop=Closed; return true; } void NineGrid::GetPath() { stack<Graph*> output; Graph *scan_Node=&(pop->data); while(scan_Node!=NULL) { output.push(scan_Node); scan_Node=scan_Node->father; } Graph * Graph_output; int cas_num=0; cout<<endl<<endl; while(!output.empty()) { if(cas_num!=0) cout<<"第"<<cas_num<<"步:"<<endl; Graph_output=output.top(); output.pop(); for(int i=1;i<=9;i++) { cout<<Graph_output->grids[i]<<" "; if(i%3==0) cout<<endl; } cas_num++; } } bool NineGrid::Judgement() { int num_one=0; int num_two=0; for(int i=2;i<=9;i++) for(int j=1;j<i;j++) { if((m_start.grids[j]!=0)&&(m_start.grids[j]<m_start.grids[i])) num_one++; if((m_end.grids[j]!=0)&&(m_end.grids[j]<m_end.grids[i])) num_two++; } if((num_two+num_one)%2!=0) return false; else return true; } bool NineGrid::Compare(const Graph child,DllNode* & SameNode) { DllNode *Scan=Open; for(int m=0;m<2;m++) { while(Scan!=NULL) { bool samedata=true; for(int i=1;samedata&&(i<=9);i++) if(child.grids[i]!=Scan->data.grids[i]) samedata=false; if(samedata) { SameNode=Scan; return true; } Scan=Scan->next; } Scan=Closed; } return false; } int NineGrid::h_function(Graph N) { /* int index[9]; GoalIndex(index); int h=0; for(int i=1;i<=9;i++) { switch(N.grids[i]) { case 0: h+=distance(index[0],i); break; case 1: h+=distance(index[1],i); break; case 2: h+=distance(index[2],i); break; case 3: h+=distance(index[3],i); break; case 4: h+=distance(index[4],i); break; case 5: h+=distance(index[5],i);