八数码问题java语言实现

《八数码问题java语言实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、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];//搜索成功后的搜索节点到初始节点的路径上的节点列表staticListresult=newArrayList

2、e>();//判断此节点的八数码状态是否在搜索表中已经存在publicstaticbooleanhasSame(Nodenode){for(inti=0;i

3、ode!=null){intx=0;inty=0;NodeexNode=null;int[][]st=null;if(!node.isEndState()){//从四个方向去扩展八数码的状态for(intj=0;j<4;j++){//计算移动后新的x，y坐标x=node.getX()+dir[j][0];y=node.getY()+dir[j][1];//产生一个新的状态节点exNode=newNode(x,y);//设置新的状态节点的八数码状态数组exNode.setState(node.getNewSameSta

4、te());st=exNode.getState();if(x>-1&&x<3&&y>-1&&y<3){//交换新的节点的八数码状态数组中的两个值(原位置和移动后的位置)inttemp=st[node.getX()][node.getY()];st[node.getX()][node.getY()]=st[x][y];st[x][y]=temp;//新扩展出来的状态在状态表中已经出现时，从下个方向扩展if(hasSame(exNode)){continue;}else{//将新扩展出来的状态加入到状态表中exNode

5、.setDir(j);exNode.setFather(node);all[i++]=exNode;//查看此节点是不是目标节点if(exNode.isEndState()){//把此目标节点到初始状态节点的路径上的节点依次存起来while(exNode!=null){result.add(exNode);exNode=exNode.getFather();}return;}}}}}//从搜索表中取出一个未扩展的节点node=all[++cur];//判断此节点是不是空，为空的话说明搜索表中的节点已经搜索完，则方法结

6、束if(node!=null){//查看此节点是不是目标节点if(node.isEndState()){//把此目标节点到初始状态节点的路径上的节点依次存起来while(node!=null){result.add(exNode);node=node.getFather();}return;}}else{System.out.println("没有搜索到正确解");return;}}}}publicstaticvoidmain(String[]args){Noden=newNode(0,2);n.getState()

7、[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("八数码的初始状态如下:");printState(n);intfinD

8、ex=result.size()-2;System.out.println("八数码的移动步骤如下:");NodecurNode=null;while(finDex>-1){curNode=result.get(finDex);intdir=curNode.getDir();switch(dir){case0:curNode=result.ge