如何使用java实现马踏棋盘
如何使用java实现马踏棋盘
这篇文章将为大家详细讲解有关如何使用java实现马踏棋盘，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
具体内容如下
马踏棋盘算法也被称为骑士周游问题
将马随机放在过期象棋的8x8棋盘的某个方格中，马按走棋规则进行移动，要求每个方格只进入一次，走遍棋盘上全部64个方格
骑士周游问题结局步骤和思路
1.创建棋盘chessBoard，是一个二维数组
2.将当前位置设置为已个访问，然后根据当前位置，计算马儿还能走那些位置，并放到一个集合中(ArrayList)，最多8个位置
3.变量ArrayList存放的所有位置，看看哪个可以走通
4.判断马儿是否完成了骑士周游问题
注意：马儿不同的走法，会得到不同的结果，效率也会有影响
代码实现
publicclassHorseChessBoard{privatestaticintX;//棋盘的列数privatestaticintY;//棋盘的行数//创建数组标记棋盘各个位置是否被访问过privatestaticboolean[]visited;//使用一个属性标记是否棋盘的所有位置都被访问过，即是否成功privatestaticbooleanfinish;//如果为true表示成功publicstaticvoidmain(String[]args){X=8;Y=8;introw=1;intcol=1;int[][]chessboard=newint[X][Y];visited=newboolean[X*Y];longstart=System.currentTimeMillis();traversalChessboard(chessboard,row-1,col-1,1);longend=System.currentTimeMillis();System.out.println(end-start);for(int[]rows:chessboard){for(intstep:rows){System.out.print(step+"");}System.out.println();}}//其实周游问题publicstaticvoidtraversalChessboard(int[][]chessboard,introw,intcol,intstep){if(finish)return;chessboard[row][col]=step;visited[row*X+col]=true;//标记该位置已经访问//获取当前位置可以走的下一个位置的集合List<Point>ps=next(newPoint(col,row));sort(ps);//遍历pswhile(!ps.isEmpty()){Pointp=ps.remove(0);//取出下一个可以走的位置//判断该点是否已经访问过if(!visited[p.y*X+p.x]){traversalChessboard(chessboard,p.y,p.x,step+1);}}//1.棋盘到目前位置任然未走完//2.棋盘处于一个回溯过程if(step<X*Y&&!finish){chessboard[row][col]=0;visited[row*X+col]=false;}else{finish=true;}}//根据当前这一步的所有的下一步的选择位置进行非递减排序publicstaticvoidsort(List<Point>ps){ps.sort(newComparator<Point>(){@Overridepublicintcompare(Pointo1,Pointo2){//获取o1,o2下一步所有个数intcount1=next(o1).size();intcount2=next(o2).size();if(count1<count2){return-1;}elseif(count1==count2){return0;}else{return1;}}});}//Point:根据当前位置(point对象)//根据当前位置，计算马儿还能走那些位置，并放到一个集合中(ArrayList)，最多8个位置publicstaticList<Point>next(PointcurPoint){//创建list集合List<Point>ps=newArrayList<>();//创建一个pointPointp1=newPoint();if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y-1)>=0){ps.add(newPoint(p1));}if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y-2)>=0){ps.add(newPoint(p1));}if((p1.x=curPoint.x+1)<X&&(p1.y=curPoint.y-2)>=0){ps.add(newPoint(p1));}if((p1.x=curPoint.x+2)<X&&(p1.y=curPoint.y-1)>=0){ps.add(newPoint(p1));}if((p1.x=curPoint.x+2)<X&&(p1.y=curPoint.y+1)<Y){ps.add(newPoint(p1));}if((p1.x=curPoint.x+1)<X&&(p1.y=curPoint.y+2)<Y){ps.add(newPoint(p1));}if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y+2)<Y){ps.add(newPoint(p1));}if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y+1)<Y){ps.add(newPoint(p1));}returnps;}}
关于“如何使用java实现马踏棋盘”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
