自动解决智能拼图，A*算法+生成可解拼图（C++）

#include<iostream> #include<set> #include<stack> #include<math.h> #include<time.h> using namespace std; const int col = 3; const int vol = 3; //int pingtu[vol][col] = {0,1,2,3,5,8,6,4,7}; int pingtu[vol][col] = {0,2,1,3,5,4,8,6,7}; int correct[vol][col] = {0,1,2,3,4,5,6,7,8}; set<int> visited; int state_count = 0; stack<int> ptstack; class ptstate{ public: int currentCost;//当前实际代价 int guessCost;//当前实际代价+估计代价 int state; ptstate(int _currentCost=0,int _guessCost=0,int _state=0):currentCost(_currentCost),guessCost(_guessCost),state(_state){}; ptstate(ptstate &_ptstate){ currentCost = _ptstate.currentCost; guessCost = _ptstate.guessCost; state = _ptstate.state; } void setState(int _currentCost,int _guessCost,int _state){ currentCost = _currentCost; guessCost = _guessCost; state = _state; } }; typedef struct openListEle{ ptstate pts; openListEle *next; openListEle *pre;//指向上一个状态，而非上一个节点 void addNext(openListEle *ole){ if(ole == NULL) return; ole->next = this->next; this->next = ole; ole->pre = this; } }openListEle; //anounce void printPingTu(int[vol][col]); void printPingTu(int); void getKeJiePingTu(int[vol][col]); long long makeInt(int[vol][col]); bool checkright(int[vol][col],int[vol][col]); void pingtuAstar(int[vol][col],int[vol][col]); bool pingtuSearch(int[vol][col]); int getGuessCostBetweenTwoState(int[vol][col],int[vol][col]); void deleteOpenListEle(openListEle*,openListEle*); //acomplish void pingtuAstar(int pt[vol][col],int correct[vol][col]){ visited.clear(); //判断是否是正确状态 int correctStateInt = makeInt(correct); if(correctStateInt == makeInt(pt)){ cout<<"已是正确状态"<<endl; return; } //初始化头节点 openListEle *openList = new openListEle; openList->next = NULL; openList->pre = NULL; //将初始状态加入openlist openListEle *startEle = new openListEle; startEle->pts.setState(0,0,makeInt(pt)); openList->addNext(startEle); openListEle *finalEle = new openListEle; finalEle = NULL; while(true){ if(finalEle != NULL) break; //找到openlist中代价最小的 openListEle *minEleP = openList->next; openListEle *minEle = NULL; int minCost = -1; int minElePCount = 0; while(minEleP!=NULL){ if(minCost == -1 || minEleP->pts.guessCost<minCost){ minCost = minEleP->pts.guessCost; minEle = minEleP; } minElePCount++; minEleP = minEleP->next; } if(minEle == NULL || minEle->pre == NULL) break; //计算以当前状态的可变状态的guessCost int tmpPt[vol][col]; int data = minEle->pts.state; for(int i=vol-1;i>=0;--i){ for(int j=col-1;j>=0;--j){ tmpPt[i][j] = data%10; data = data/10; } } int zi = 0,zj = 0; for(int i=0;i<vol;++i){ for(int j=0;j<col;++j) if(tmpPt[i][j] == vol*col-1){ zi = i; zj = j; break; } } int offseti[4] = {-1,0,1,0}; int offsetj[4] = {0,1,0,-1}; for(int i=0;i<4;++i){ int ti = zi+offseti[i]; int tj = zj+offsetj[i]; if(ti<0 || ti>vol-1 || tj<0 || tj>col-1) continue; int t = tmpPt[ti][tj]; tmpPt[ti][tj] = tmpPt[zi][zj]; tmpPt[zi][zj] = t; int hashcode = makeInt(tmpPt); if(visited.find(hashcode) == visited.end()){ visited.insert(hashcode); openListEle *newEle = new openListEle; int tmpguessCost = getGuessCostBetweenTwoState(tmpPt,correct); newEle->pts = ptstate(minEle->pts.currentCost+1,minEle->pts.currentCost+1+tmpguessCost,hashcode); minEle->addNext(newEle); if(hashcode == correctStateInt) finalEle = newEle; } t = tmpPt[ti][tj]; tmpPt[ti][tj] = tmpPt[zi][zj]; tmpPt[zi][zj] = t; } //从openList中删除 deleteOpenListEle(openList,minEle); } //保存路径 stack<openListEle*> rightpath; openListEle *pathEle = finalEle; while(pathEle != NULL){ rightpath.push(pathEle); pathEle = pathEle->pre; } int steps = 0; //输出路径 int firstOrNot = true; while(!rightpath.empty()){ pathEle = rightpath.top(); if(firstOrNot != true) printPingTu(pathEle->pts.state);getchar(); firstOrNot = false; steps++; rightpath.pop(); } cout<<"共需:"<<steps<<"步"<<endl; } void deleteOpenListEle(openListEle *head,openListEle *toDelete){ openListEle *p = head; while(p->next != NULL && p->next != toDelete) p = p->next; if(p->next != NULL) p->next = p->next->next; } int getGuessCostBetweenTwoState(int a[vol][col],int b[vol][col]){ int guessCost = 0; for(int ai=0;ai<vol;++ai) for(int aj=0;aj<col;++aj){ bool found = false; for(int bi=0;bi<vol && found == false;++bi) for(int bj=0;bj<col && found == false;++bj) if(a[ai][aj] == b[bi][bj]){ guessCost += sqrt(1.0*(ai-bi)*(ai-bi)+(aj-bj)*(aj-bj)); found = true; } } return guessCost; } void printPingTu(int a[vol][col]){ for(int i=0;i<vol;++i){ for(int j=0;j<col;++j){ if(a[i][j] != col*vol-1) cout<<a[i][j]<<" "; else cout<<" "; } cout<<endl; } } void printPingTu(int data){ int tmpPt[vol][col]; for(int i=vol-1;i>=0;--i){ for(int j=col-1;j>=0;--j){ tmpPt[i][j] = data%10; data = data/10; } } printPingTu(tmpPt); } void getKeJiePingTu(int a[vol][col]){ int data[vol*col] = {0}; int maxnumber = vol*col-1; for(int i=0;i<maxnumber;++i){ data[i] = i; int replacei = rand()%(i+1); int t = data[i]; data[i] = data[replacei]; data[replacei] = t; } data[maxnumber] = maxnumber; //计算逆序对数 int coverPairCount = 0; for(int i=0;i<maxnumber;++i){ for(int j=i+1;j<maxnumber;++j){ if(data[i]>data[j]) coverPairCount++; } } if( (coverPairCount&1) == 1){ int t = data[maxnumber-1]; data[maxnumber-1] = data[maxnumber-2]; data[maxnumber-2] = t; } int index = 0; for(int i=0;i<vol;++i){ for(int j=0;j<col;++j){ a[i][j] = data[index++]; } } } long long makeInt(int a[vol][col]){ long long sum = 0; for(int i=0;i<vol;++i) for(int j=0;j<col;++j){ sum = 10*sum+a[i][j]; } return sum; } bool checkright(int a[vol][col],int b[vol][col]){ //cout<<makeInt(a)<<" "<<makeInt(b)<<endl; return makeInt(a)==makeInt(b); } bool pingtuSearch(int pt[vol][col]){ visited.clear(); while(!ptstack.empty()) ptstack.pop(); state_count = 0; int data = makeInt(pt); visited.insert(data); ptstack.push(data); while(!ptstack.empty()){ state_count++; data = ptstack.top(); ptstack.pop(); for(int i=vol-1;i>=0;--i){ for(int j=col-1;j>=0;--j){ pt[i][j] = data%10; data = data/10; } } if(checkright(pt,correct)) return true; int zi = 0,zj = 0; for(int i=0;i<vol;++i){ for(int j=0;j<col;++j) if(pt[i][j] == vol*col-1){ zi = i; zj = j; break; } } int offseti[4] = {-1,0,1,0}; int offsetj[4] = {0,1,0,-1}; for(int i=0;i<4;++i){ int ti = zi+offseti[i]; int tj = zj+offsetj[i]; if(ti<0 || ti>vol-1 || tj<0 || tj>col-1) continue; int t = pt[ti][tj]; pt[ti][tj] = pt[zi][zj]; pt[zi][zj] = t; int hashcode = makeInt(pt); if(visited.find(hashcode) == visited.end()){ visited.insert(hashcode); ptstack.push(hashcode); } t = pt[ti][tj]; pt[ti][tj] = pt[zi][zj]; pt[zi][zj] = t; } } return false; } int main(){ srand(time(NULL)); //while(true){ // getKeJiePingTu(pingtu); // cout<<"start state"<<endl; // printPingTu(pingtu); // cout<<pingtuSearch(pingtu)<<endl; // cout<<"state_count: "<<state_count<<endl; // cout<<"correct state"<<endl; // printPingTu(correct); // getchar(); //} getKeJiePingTu(pingtu); cout<<"start state"<<endl; printPingTu(pingtu); pingtuAstar(pingtu,correct); cout<<pingtuSearch(pingtu)<<endl; cout<<"暴力搜索需要:"<<state_count<<"步"<<endl; system("pause"); }