宽度优先搜索解决八数码问题

解八数码问题：任意输入两个九宫格作为初始状态和目标状态，用宽度优先搜索求解。#includeiostream#includevector#includedeque#includestack#includestringusingnamespacestd;classNineNode{public:intnine[3][3];//九宫格intparent;//父节点，根节点的父节点为-1inti;//空白所在行intj;//空白所在列stringstep;//从上一节点移动至此节点所需操作};boolhavesolution(NineNodestart,NineNodeend);boolmatch(NineNodenode1,NineNodenode2);boolishave(dequeNineNodeopenQueue,vectorNineNodeclosedList,NineNodenode);intmain(){inti,j;dequeNineNodeopenQueue;//open队列vectorNineNodeclosedList;//closed列表stackstringmovepath;//移动步骤栈NineNodeinitilNode,lastNode;//初始节点和目标节点cout请输入初始节点状态:;/*输入初始节点状态开始*/for(i=0;i3;i++)for(j=0;j3;j++){cininitilNode.nine[i][j];if(0==initilNode.nine[i][j]){initilNode.i=i;initilNode.j=j;}}initilNode.parent=-1;/*输入初始节点状态结束*/cout请输入目标节点状态:;/*输入目标节点状态开始*/for(i=0;i3;i++)for(j=0;j3;j++){cinlastNode.nine[i][j];if(0==lastNode.nine[i][j]){lastNode.i=i;lastNode.j=j;}}lastNode.parent=-1;/*输入目标节点状态结束*/if(havesolution(initilNode,lastNode)){intparent=-1;//parent指示父节点下标boolflag=false;//找到标志openQueue.push_back(initilNode);while((!openQueue.empty())&&(!flag)){NineNodetemp;temp=openQueue.front();openQueue.pop_front();closedList.push_back(temp);parent=closedList.size()-1;if(match(temp,lastNode)){flag=true;break;}if(temp.j0)//向左移动{NineNodeleft=temp;left.nine[temp.i][temp.j]=left.nine[temp.i][temp.j-1];left.nine[temp.i][temp.j-1]=0;left.parent=parent;left.i=temp.i;left.j=temp.j-1;left.step=向左移动;if(!ishave(openQueue,closedList,left))openQueue.push_back(left);}if(temp.i0)//向上移动{NineNodeup=temp;up.nine[temp.i][temp.j]=up.nine[temp.i-1][temp.j];up.nine[temp.i-1][temp.j]=0;up.parent=parent;up.i=temp.i-1;up.j=temp.j;up.step=向上移动;if(!ishave(openQueue,closedList,up))openQueue.push_back(up);}if(temp.j2)//向右移动{NineNoderight=temp;right.nine[temp.i][temp.j]=right.nine[temp.i][temp.j+1];right.nine[temp.i][temp.j+1]=0;right.parent=parent;right.i=temp.i;right.j=temp.j+1;right.step=向右移动;if(!ishave(openQueue,closedList,right))openQueue.push_back(right);}if(temp.i2)//向下移动{NineNodedown=temp;down.nine[temp.i][temp.j]=down.nine[temp.i+1][temp.j];down.nine[temp.i+1][temp.j]=0;down.parent=parent;down.i=temp.i+1;down.j=temp.j;down.step=向下移动;if(!ishave(openQueue,closedList,down))openQueue.push_back(down);}}NineNodelast=closedList.back();//从最后节点沿父指针向上找while(last.parent!=-1){movepath.push(last.step);last=closedList[last.parent];}cout目标可解,移动步骤如下:endl;stringstep;while(!movepath.empty()){step=movepath.top();movepath.pop();coutstependl;}cout得到解endl;}else{cout目标节点不可达!endl;}system(pause);return0;}/*判断两个节点是否相同，相同返回true，否则返回false*/boolmatch(NineNodenode1,NineNodenode2){inti,j;boolresult=true;for(i=0;i3;i++)for(j=0;j3;j++){if(node1.nine[i][j]!=node2.nine[i][j]){result=false;break;}}returnresult;}/*判断新节点是否已经存在，即判断是否存在于open队列和closed列表中*/boolishave(dequeNineNodeopenQueue,vectorNineNodeclosedList,NineNodenode){boolresult=false;dequeNineNode::iteratorqit=openQueue.begin();vectorNineNode::iteratorvit=closedList.begin();while(qit!=openQueue.end()){if(match(*qit++,node)){result=true;break;}}while(vit!=closedList.end()){if(match(*vit++,node)){result=true;break;}}returnresult;}/*判断给定的八数码问题是否有解*/boolhavesolution(NineNodestart,NineNodeend){boolresult=false;inti,j,count1=0,count2=0;inta[3*3];intb[3*3];for(i=0;i3;i++)for(j=0;j3;j++){if(start.nine[i][j]!=0)a[count1++]=start.nine[i][j];if(end.nine[i][j]!=0)b[count2++]=end.nine[i][j];}intrsum=0,tsum=0;for(i=0;i8;i++)for(j=0;ji;j++){if(a[j]a[i])rsum++;if(b[j]b[i])tsum++;}if(rsum%2==tsum%2)result=true;returnresult;}