马踏棋盘算法

た入场券 2022-10-22 07:32 168阅读 0赞

# 一：马踏棋盘算法介绍 #

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

[游戏演示地址][Link 1]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

# 二：马踏棋盘游戏代码实现 #

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][]

分析第一种方式的问题，并使用贪心算法（ greedyalgorithm ）进行优化。解决马踏棋盘问题 .

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2][]

代码实现：

HorseChessboard实体类：

package com.horse;
    
    import com.sun.xml.internal.ws.message.ByteArrayAttachment;
    
    import java.awt.*;
    import java.util.ArrayList;
    import java.util.Comparator;
    
    /**
     * @author lizhangyu
     * @date 2021/4/4 21:25
     */
    public class HorseChessboard {
    
        /**
         * 棋盘的列数
         */
        private static int X;
    
        /**
         * 棋盘的行数
         */
        private static int Y;
    
        /**
         * 创建一个数组，标记棋盘的各个位置是否被访问过
         */
        private static boolean visited[];
    
        /**
         * 使用一个属性，标记是否棋盘的所有位置都被访问过
         * 如果为true，表示成功
         */
        private static boolean finished;
    
        public static void main(String[] args) {
    
            System.out.println("骑士周游算法，开始运行");
    
            X = 6;
            Y = 6;
    
            //马儿初始位置的行，从 1 开始编号
            int row = 1;
            //马儿初始位置的列，从 1 开始编号
            int column = 1;
    
            //创建棋盘
            int[][] chessboard = new int[X][Y];
    
            //初始值都是false
            visited = new boolean[X * Y];
    
            //测试一下耗时
            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 进行排序,排序的规则就是对 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 成立的情况有两种
             * 1. 棋盘到目前位置,仍然没有走完
             * 2. 棋盘处于一个回溯过程
             */
            if (step < X * Y && !finished) {
                chessboard[row][column] = 0;
                visited[row * X + column] = false;
            }else {
                finished = true;
            }
        }
    
        /**
         * 功能：根据当前位置（Point对象），计算马儿还能走那些位置，并放入到一个集合中（ArrayList），最多有8个位置
         * @param curPoint
         * @return
         */
        public static ArrayList<Point> next(Point curPoint) {
            //创建一个ArrayList
            ArrayList<Point> ps = new ArrayList<>();
    
            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) {
                    int count1 = next(o1).size();
                    int count2 = next(o2).size();
                    if (count1 < count2) {
                        return -1;
                    }else if (count1 == count2) {
                        return 0;
                    }else {
                        return 1;
                    }
                }
            });
        }
    
    }

运行结果：

1：采用贪心算法的结果

骑士周游算法，开始运行
    共耗时: 11 毫秒
    4	33	24	13	2	35	
    25	12	3	34	27	14	
    32	5	26	23	36	1	
    11	22	9	28	15	18	
    6	31	20	17	8	29	
    21	10	7	30	19	16

没有采用贪心算法的结果：

骑士周游算法，开始运行
    共耗时: 90 毫秒
    1	6	9	26	3	36	
    8	27	2	5	10	25	
    31	16	7	12	35	4	
    28	21	30	17	24	11	
    15	32	19	22	13	34	
    20	29	14	33	18	23

由此可见采用了贪心算法可以大大的减少回溯的次数，从而提高程序的效率。

[Link 1]: https://u.ali213.net/detail/403.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221022/bd3819a1fff3438abbe4e11e0d5ca4a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: /images/20221022/2f7119614c1942388b6043c3594fc34e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2]: /images/20221022/8c6c2fdbd9064beba6149e1370c15ab9.png