【Java数据结构与算法】骑士周游问题

骑士周游问题说明

马踏棋盘算法也被称为骑士周游问题
将马随机放在国际象棋的 8×8 棋盘 Board [0～7][0～7] 的某个方格中，马按走棋规则 (马走日字) 进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格。
如图所示

骑士周游问题思路图解

思路分析

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

步骤分析

回溯算法步骤分析

创建棋盘chessBoard，定义为一个二维数组。
将当前位置设置为已经访问，然后根据当前位置，计算马还能走哪些位置，并放入到
一个集合中(ArrayList),最多有8个位置，每走一步，就使用step+1。
遍历ArrayList中存放的所有位置，看看哪个可以走通，如果走通就继续，否则进行回溯。
判断马儿是否完成了任务，使用step和应该走的步数比较，如果没有达到数量，则表
示没有完成任务，将整个棋盘置0。
注意：马不同的走法(策略) ,会得到不同的结果，效率也会有影响。(需要进行优化)

马进行移动的代码举例：

// 创建一个Point
Point p1 = new Point();
// 表示：马可以走到上图5的位置
if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
    ps.add(new Point(p1));
}

骑士周游回溯算法代码实现-移动方法

代码

package com.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;

/**
 * @author Joker大雄
 * @data 2022/12/2 - 10:53
 **/
public class HorseChessBoard {

    private static int X; // 棋盘的列数
    private static int Y; // 棋盘的行数

    public static void main(String[] args) {
    }

    /**
     * function: 根据当前位置(Point对象)，计算马还能走哪些位置(Point对象)，并放入到一个集合中(ArrayList),最多有8个位置
     *
     * @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;
    }
}

骑士周游回溯算法代码实现-算法实现

代码

package com.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;

/**
 * @author Joker大雄
 * @data 2022/12/2 - 10:53
 **/
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) + "ms");
        // 输出棋盘最终结果
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }


    }

    /**
     * function:马踏棋盘问题解决的方法(回溯)
     *
     * @param chessboard 棋盘
     * @param row        马当前所在位置的行，从0开始
     * @param column     马当前所在位置的列，从0开始
     * @param step       马所走的第几步，初始位置就是第一步
     */
    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
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);// 取出下一个可以走的位置
            // 判断该点是否已经访问过
            if (!visited[p.y * X + p.x]) {// 还未被访问
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }
        // 判断任务是否完成，没完成就将棋盘置为0
        // step < X * Y 成立存在两种情况：
        // 1. 棋盘到目前位置，仍然没有走完
        // 2. 棋盘处于回溯过程中
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {// 棋盘走完
            finished = true;
        }
    }

    /**
     * function: 根据当前位置(Point对象)，计算马还能走哪些位置(Point对象)，并放入到一个集合中(ArrayList),最多有8个位置
     *
     * @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;
    }
}

运行结果

可以看到运算花费时间将近22秒，需要进行优化；

~骑士周游启动~
耗费时间：21897ms
1	8	11	16	3	18	13	64	
10	27	2	7	12	15	4	19	
53	24	9	28	17	6	63	14	
26	39	52	23	62	29	20	5	
43	54	25	38	51	22	33	30	
40	57	42	61	32	35	48	21	
55	44	59	50	37	46	31	34	
58	41	56	45	60	49	36	47	

Process finished with exit code 0

骑士周游使用贪心算法优化

贪心算法优化步骤分析

我们获取当前位置，可以走的下一个位置的集合。

1 2	// 获取当前位置可以走的下一个位置的集合 ArrayList<Point> ps = next(new Point(column,row));

我们需要对ps里的所有Point的下一步的全部集合的数目，进行非递减排序。

8,7,6,5,3,2,1 // 递减排序
1,2,3,4,5,6,9, // 递增排序
1,2,2,3,3,3,5,6 // 非递减，在递增过程中允许重复
9,7,6,6,5,5,3,3,1 // 非递增，在递减过程中允许重复

代码实现

代码

package com.algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author Joker大雄
 * @data 2022/12/2 - 10:53
 **/
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) + "ms");
        // 输出棋盘最终结果
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    /**
     * function:马踏棋盘问题解决的方法(回溯)
     *
     * @param chessboard 棋盘
     * @param row        马当前所在位置的行，从0开始
     * @param column     马当前所在位置的列，从0开始
     * @param step       马所走的第几步，初始位置就是第一步
     */
    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);
            }
        }
        // 判断任务是否完成，没完成就将棋盘置为0
        // step < X * Y 成立存在两种情况：
        // 1. 棋盘到目前位置，仍然没有走完
        // 2. 棋盘处于回溯过程中
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {// 棋盘走完
            finished = true;
        }
    }

    /**
     * function: 根据当前位置(Point对象)，计算马还能走哪些位置(Point对象)，并放入到一个集合中(ArrayList),最多有8个位置
     *
     * @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和o2的下一步的所有位置个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                // 非递减
                if(count1<count2){
                    return -1;
                }else if(count1 == count2){
                    return 0;
                }else{
                    return 1;
                }
            }
        });
    }
}

运行结果

可以看到优化后速度非常快！

注意：更换策略意味着走法会有变法，结果也会不同；

~骑士周游启动~
耗费时间：30ms
1	16	37	32	3	18	47	22	
38	31	2	17	48	21	4	19	
15	36	49	54	33	64	23	46	
30	39	60	35	50	53	20	5	
61	14	55	52	63	34	45	24	
40	29	62	59	56	51	6	9	
13	58	27	42	11	8	25	44	
28	41	12	57	26	43	10	7	

Process finished with exit code 0