马随机放在国际象棋的 8X8 棋盘Board[0~7] [0~7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。
马踏棋盘游戏代码实现
马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
如果使用回溯(就是深度优先搜索)来解决，假如马儿踏了53个点，走到了第53个，坐标(1,0) ，发现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回退…
分析第一种方式的问题，并使用贪心算法(greedyalgorithm)进行优化。解决马踏棋盘问题。
使用前面的游戏来验证算法是否正确。
解决步骤和思路： https://blog.csdn.net/zhang0558/article/details/50497298
创建棋盘chessBoard，是一个二维数组
将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合中(ArrayList),最多有8个位置，每走-步,就使用step+1
遍历ArrayList中存放的所有位置，看看哪个可以走通,如果走通，就继续，走；不通，就回溯
判断马儿是否完成了任务，使用step 和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置0
注意:马儿不同的走法(策略)，会得到不同的结果，效率也会有影响(优化)
publicclassHorsechessBoard{ privatestaticintX;// 表示列 privatestaticintY;// 表示行 privatestaticbooleanvisited[];// 是否被访问 privatestaticbooleanfinished;// 是否全部完成 // 进行行走 publicstaticvoidtraversal(int[][]arr,introw,intcol,intstep){ arr[row][col]=step; visited[row*X+col]=true;// 初始位置标记为已访问 // 获取下一步集合 ArrayList<Point>ps=next(newPoint(col,row)); sort(ps);//然后在traversal方法当中的ps进行排序： // 遍历集合 while(!ps.isEmpty()){ Pointp=ps.remove(0); // 判断该点是否访问过 if(!visited[p.y*X+p.x]){// 没有访问过 traversal(arr,p.y,p.x,step+1); } } if(step<X*Y&&!finished){ arr[row][col]=0; visited[row*X+col]=false; }else{ finished=true; } } publicstaticvoidsort(ArrayList<Point>ps){ ps.sort(newComparator<Point>(){ @Override publicintcompare(Pointo1,Pointo2){ intcount1=next(o1).size(); intcount2=next(o2).size(); if(count1<count2){ return-1; }elseif(count1==count2){ return0; }else{ return1; } } }); } // 根据当前位置计算还有哪些位置可以走 staticintweizhi[][]={{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}}; publicstaticArrayList<Point>next(PointcutPoint){ ArrayList<Point>ps=newArrayList<Point>(); Pointp1=newPoint(); // 判断是否可以走下一个位置 if((p1.x=cutPoint.x-2)>=0&&(p1.y=cutPoint.y-1)>=0){ ps.add(newPoint(p1)); } if((p1.x=cutPoint.x-1)>=0&&(p1.y=cutPoint.y-2)>=0){ ps.add(newPoint(p1)); } if((p1.x=cutPoint.x+1)<X&&(p1.y=cutPoint.y-2)>=0){ ps.add(newPoint(p1)); } if((p1.x=cutPoint.x+2)<X&&(p1.y=cutPoint.y-1)>=0){ ps.add(newPoint(p1)); } if((p1.x=cutPoint.x+2)<X&&(p1.y=cutPoint.y+1)<Y){ ps.add(newPoint(p1)); } if((p1.x=cutPoint.x+1)<X&&(p1.y=cutPoint.y+2)<Y){ ps.add(newPoint(p1)); } if((p1.x=cutPoint.x-1)>=0&&(p1.y=cutPoint.y+2)<Y){ ps.add(newPoint(p1)); } if((p1.x=cutPoint.x-2)>=0&&(p1.y=cutPoint.y+1)<Y){ ps.add(newPoint(p1)); } returnps; } publicstaticvoidmain(String[]args){ X=9;//chg to 6 Y=9; introw=5; intcol=5; int[][]arr=newint[X][Y]; visited=newboolean[X*Y]; System.out.println("开始"); longstart=System.currentTimeMillis(); traversal(arr,row-1,col-1,1); longend=System.currentTimeMillis(); System.out.println("耗时 = "+(end-start)+" 毫秒"); for(int[]rows:arr){ for(intstep:rows){ System.out.print(step+"\t"); } System.out.println(); } System.out.println("结束"); }}
