java实现马踏棋盘的算法
本文实例为大家分享了java实现马踏棋盘的具体代码,供大家参考,具体内容如下
马踏棋盘算法介绍
8X8棋盘,马走日字,要求每个方格只进入一次,走遍棋盘上全部64个方格。
代码:
public class HorseChessBoard { private static int X;//棋盘的列数 private static int Y;//棋盘的行数 //创建一个数组,标记棋盘的各个位置是否被访问过 private static boolean visited[]; //使用一个属性,标记是否棋盘的所有位置都被访问 private static boolean finished;//如果为true,表示成功 public static void main(String[] args) { System.out.println("骑士周游算法"); //测试骑士周游算法是否正确 X = 8; Y = 8; int row = 1;//初始位置的行,从1开始编号 int column = 1;//初始位置的列,从1开始编号 //创建棋盘 int[][] chessboard = new int[X][Y]; visited = new boolean[X*Y];//初始值都是false //测试一下耗时 long start = System.currentTimeMillis(); traversalChessboard(chessboard, row-1, column-1,1); long end = System.currentTimeMillis(); System.out.println("共耗时:" +( end-start)+"毫秒"); //输出棋盘的最后情况 for (int[] rows : chessboard){ for (int step : rows){ System.out.print(step + "\t"); } System.out.println(); } } /** * 完成骑士周游问题的算法 * @param chessboard 棋盘 * @param row 马儿当前的位置的行 从0开始 * @param column 马儿当前的位置的列 从0开始 * @param step 第几步,初始位置是第1步 */ public static void traversalChessboard(int[][] chessboard, int row, int column, int step){ chessboard[row][column] = step; visited[row * X + column] = true;//标记该位置已访问 //获取当前位置可以走的下一个位置的集合 ArrayList<Point> ps = next(new Point(column, row)); //对ps进行排序,排序的规则就是对所有的Point对象的下一步的位置的数目进行非递减排序; sort(ps); //遍历ps while (!ps.isEmpty()){ Point p = ps.remove(0);//取出下一个可以走的位置 //判断该点是否已经访问过 if (!visited[p.y * X + p.x]){//说明还没有访问过 traversalChessboard(chessboard, p.y, p.x, step + 1); } } //判断是否完成任务,使用step和应该走的步数比较 //如果没有达到数量,则表示没有完成任务,将整个棋盘置0 //说明:step < X * Y成立:①棋盘到目前为止仍然没有走完;②棋盘处于一个回溯过程 if (step < X * Y && !finished){ chessboard[row][column] = 0; visited[row * X + column] = false; }else { finished = true; } } /** * 功能:根据当前位置(Point对象),计算马儿还能走哪些位置(Point),并放入到一个集合中ArrayList,最多有八个位置 * * @param curPoint * @return */ public static ArrayList<Point> next(Point curPoint) { //创建一个ArrayList ArrayList<Point> ps = new ArrayList<Point>(); //创建一个Point Point p1 = new Point(); //表示可以走5 if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) { ps.add(new Point(p1)); } //判断是否能走6位置 if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) { ps.add(new Point(p1)); } //判断是否能走7位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) { ps.add(new Point(p1)); } //判断是否能走0位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) { ps.add(new Point(p1)); } //判断是否能走1位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } //判断是否能走2位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } //判断是否能走3位置 if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } //判断是否能走4位置 if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } return ps; } //根据当前这一步的所有的下一步的选择位置,进行非递减排序,减少回溯次数 public static void sort(ArrayList<Point> ps){ ps.sort(new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { //先获取o1的下一步的所有位置的个数 int count1 = next(o1).size(); //获取o2的下一步的所有位置的个数 int count2 = next(o2).size(); if (count1 < count2){ return -1; }else if(count1 == count2){ return 0; }else { return 1; } } }); } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
赞 (0)