【算法】马踏棋盘（骑士周游）问题回溯算法实现以及使用贪心算法优化

目录

1.游戏规则

2.算法分析

3.解决步骤和思路

4.马踏棋盘算法的代码实现

4.1计算马儿还能走哪些位置

4.2马踏棋盘的核心代码

4.3马踏棋盘算法完整代码

4.4使用贪心算法进行优化

4.4.1思路

4.4.2代码实现 

---

1.游戏规则

将马儿随机放在国际象棋的 8*8 棋盘的某个方格中，马儿按照“马走日”进行移动，要求每个方格只进入一次，走遍棋盘上全部 64 个方格。

2.算法分析

1. 马踏棋盘（骑士周游）问题实际上是图的深度优先搜索（DFS）的应用
2. 如果使用回溯（就是深度优先搜索）来解决，假如马儿踏了 53 个点，如图：走到了第 53 个，坐标 (1,0)，发现已经走到尽头，没办法，那就只能回退了。为了查看其他的路径，就在棋盘上不停的回溯
3. 使用贪心算法进行优化

3.解决步骤和思路

1. 创建棋盘 chessBoard，是一个二维数组
2. 将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合（ArrayList）中，最多有 8 个位置，每走一步，就让 step + 1
3. 遍历 ArrayList 中存放的所有位置，看看哪个可以走通，如果走通就继续，走不通就回溯
4. 判断马儿是否完成了任务，使用 step 和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置 0

注意：马儿不同的走法会得到不同的结果，效率也会有影响

4.马踏棋盘算法的代码实现

4.1计算马儿还能走哪些位置

public static ArrayList<Point> next(Point curPoint) {//创建一个 ArrayListArrayList<Point> ps = new ArrayList<>();//创建一个 PointPoint p1 = new Point();//左偏上if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}//上偏左if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}//上偏右if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}//右偏上if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}//右偏下if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));}//下偏右if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}//下偏左if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}//左偏下if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));}return ps;}

4.2马踏棋盘的核心代码

    /*** 完成马踏棋盘问题的算法* @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));//遍历 pswhile (!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 成立的条件有两种1.棋盘到目前为止，仍然没有走完2.棋盘处于一个回溯过程*/if (step < X * Y && !finished) {chessboard[row][column] = 0;visited[row * X + column] = false;} else {finished = true;}}

4.3马踏棋盘算法完整代码

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));//遍历 pswhile (!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 成立的条件有两种1.棋盘到目前为止，仍然没有走完2.棋盘处于一个回溯过程*/if (step < X * Y && !finished) {chessboard[row][column] = 0;visited[row * X + column] = false;} else {finished = true;}}public static ArrayList<Point> next(Point curPoint) {//创建一个 ArrayListArrayList<Point> ps = new ArrayList<>();//创建一个 PointPoint p1 = new Point();//左偏上if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}//上偏左if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}//上偏右if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}//右偏上if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}//右偏下if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));}//下偏右if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}//下偏左if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}//左偏下if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));}return ps;}
}

4.4使用贪心算法进行优化

4.4.1思路

1. 获取当前位置的可以走的下一个位置的集合
2. 对 ps 中所有的 Point 的下一步的所有集合的数目进行非递减排序

4.4.2代码实现 

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 进行排序sort(ps);//遍历 pswhile (!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 成立的条件有两种1.棋盘到目前为止，仍然没有走完2.棋盘处于一个回溯过程*/if (step < X * Y && !finished) {chessboard[row][column] = 0;visited[row * X + column] = false;} else {finished = true;}}public static ArrayList<Point> next(Point curPoint) {//创建一个 ArrayListArrayList<Point> ps = new ArrayList<>();//创建一个 PointPoint p1 = new Point();//左偏上if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}//上偏左if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}//上偏右if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {ps.add(new Point(p1));}//右偏上if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {ps.add(new Point(p1));}//右偏下if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {ps.add(new Point(p1));}//下偏右if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}//下偏左if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {ps.add(new Point(p1));}//左偏下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>() {@Overridepublic 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;}}});}
}