八數碼問題Java語言實現

importjava.util.ArrayList;importjava.util.List;/***@authordudizi@version1.0@date2013/3/15*/publicclassBaShuMa(//方向數組int[][]dir={{0,-1},{-1,0},{0,1},{1,0}};//搜索表staticNode[]all=newNode[1000000];//搜索成功后的搜索節(jié)點到初始節(jié)點的路徑上的節(jié)點列表staticList<Node>result=newArrayList<Node>();//判斷此節(jié)點的八數碼狀態(tài)是否在搜索表中已經存在publicstaticbooleanhasSame(Nodenode){for(inti=0;i<all.length;i++){if(all[i]!=null&&node.equals(all[i]))returntrue;}returnfalse;}//搜索八數碼解的方法publicvoidSearch(Nodenode){inti=0;intcur=0;//把初始狀態(tài)放到狀態(tài)表中all[i++]=node;while(cur<1000000){if(node!=null){intx=0;inty=0;NodeexNode=null;int[][]st=null;if(!node.isEndState()){//從四個方向去擴展八數碼的狀態(tài)for(intj=0;j<4;j++){〃計算移動后新的x，y坐標x=node.getX()+dir[j][0];y=node.getY()+dir[j][1];〃產生一個新的狀態(tài)節(jié)點exNode=newNode(x,y);〃設置新的狀態(tài)節(jié)點的八數碼狀態(tài)數組exNode.setState(node.getNewSameState());st=exNode.getState();if(x>-1&&x<3&&y>-1&&y<3){〃交換新的節(jié)點的八數碼狀態(tài)數組中的兩個值(原位置和移動后的位置)inttemp=st[node.getX()][node.getY()];st[node.getX()][node.getY()]=st[x][y];st[x][y]=temp;//新擴展出來的狀態(tài)在狀態(tài)表中已經出現時，從下個方向擴展if(hasSame(exNode)){continue;}else{//將新擴展出來的狀態(tài)加入到狀態(tài)表中exNode.setDir(j);exNode.setFather(node);all[i++]=exNode;〃查看此節(jié)點是不是目標節(jié)點if(exNode.isEndState()){〃把此目標節(jié)點到初始狀態(tài)節(jié)點的路徑上的節(jié)點依次存起來while(exNode!=null){result.add(exNode);exNode=exNode.getFather();}return;}}}}}〃從搜索表中取出一個未擴展的節(jié)點node=all[++cur];//判斷此節(jié)點是不是空，為空的話說明搜索表中的節(jié)點已經搜索完，則方法結束if(node!=null){//查看此節(jié)點是不是目標節(jié)點if(node.isEndState()){//把此目標節(jié)點到初始狀態(tài)節(jié)點的路徑上的節(jié)點依次存起來while(node!=null){result.add(exNode);node=node.getFather();}return;}}else(System.out.println("沒有搜索到正確解”);return;}}}}publicstaticvoidmain(String[]args)(Noden=newNode(0,2);n.getState()[0][0]=1;n.getState()[0][1]=2;n.getState()[0][2]=9;n.getState()[1][0]=5;n.getState()[1][1]=6;n.getState()[1][2]=3;n.getState()[2][0]=4;n.getState()[2][1]=7;n.getState()[2][2]=8;//開始搜索newBaShuMa().Search(n);System.out.println("八數碼的初始狀態(tài)如下:”)；printState(n);intfinDex=result.size()-2;System.out.println("八數碼的移動步驟如下:，NodecurNode=null;while(finDex>-1)(curNode=result.get(finDex);intdir=curNode.getDir();switch(dir)(case0:curNode=result.get(finDex--);System.out.println("x向左");printState(curNode);break;case1:curNode=result.get(finDex--);System.out.println("x向上");printState(curNode);break;case2:curNode=result.get(finDex--);System.out.println("x向右");printState(curNode);break;case3:curNode=result.get(finDex--);System.out.println("x向下");printState(curNode);break;}}}//打印狀態(tài)節(jié)點的對應的八數碼狀態(tài)publicstaticvoidprintState(Nodenode)(for(inti=0;i<3;i++)(for(intj=0;j<3;j++){if(node.getState()[i][j]==9){System.out.print('x'+"");}else{System.out.print(node.getState()[i][j]+"");}}System.out.println();}}}/***@authordudizi@version1.0@date2013/3/15*/publicclassNode{//此節(jié)點的八數碼狀態(tài)數組中'x'的行列值privateintx;privateinty;//此節(jié)點的八數碼狀態(tài)數組privateint[][]state=newint[3][3];//此節(jié)點的父節(jié)點privateNodefather;//父節(jié)點移動生成此節(jié)點的方向privateintdir;//判斷此狀態(tài)節(jié)點是否是最終的解狀態(tài)publicbooleanisEndState()(intx=1;for(inti=0;i<state.length&&x<9;i++){for(intj=0;j<state.length&&x<9;j++){if(state[i][j]!=x)returnfalse;x++;}}returntrue;}//返回一個新的與此狀態(tài)節(jié)點有相同八數碼狀態(tài)的節(jié)點publicint[][]getNewSameState(){int[][]st=newint[3][3];for(inti=0;i<3;i++){for(intj=0;j<3;j++){st[i][j]=state[i][j];}}returnst;}//判斷兩個節(jié)點的八數碼狀態(tài)是否相同publicbooleanequals(Nodenode){for(inti=0;i<state.length;i++){for(intj=0;j<state.length;j++){if(state[i][j]!=node.getState()[i][j])returnfalse;}}returntrue;}publicint[][]getState(){returnstate;}publicvoidsetState(int[][]state){this.state=state;}publicNode(intx,inty){super();this.x=x;this.y=y;}publicintgetX()(returnx;}publicvoidsetX(intx)(this.x=x;}publicintgetY()(returny;}publicvoidsetY(inty)(this.y=y;}publicNodegetFather()(returnfather;}public