骑士周游回溯算法 - 图1
    骑士周游回溯算法 - 图2

    1. /**
    2.  * 《骑士周游回溯算法》
    3.  *
    4.  *    马踏棋盘算法也被称为骑士周游问题，将马随机放在国际象棋的8X8棋盘，Board[0~7][0~7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格
    5.  *
    6.  *  骑士周游问题的解决步骤和思路
    7.  *    1.创建棋盘chessBoard,是一个二维数组
    8.  *    2.将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，
    9.  *      并放入到一个集合中(ArrayList),最多有8个位置，每走一步，就使用step+1
    10.  *    3.遍历ArrayList中存放的所有位置，看看哪个可以走通,如果走通，就继续，走不通，就回溯
    11.  *    4.判断马儿是否完成了任务,使用step 和应该走的步数比较,如果没有达到数量，则表示没有完成任务，将整个棋盘置0
    12.  *  注意:马儿不同的走法(策略) ,会得到不同的结果，效率也会有影响(优化)
    13.  */
    14. public class HorseChessboard {
    16.     /**
    17.      * 棋盘的行数
    18.      */
    19.     private int x;
    20.     /**
    21.      * 棋盘的列数
    22.      */
    23.     private int y;
    25.     /**
    26.      * 创建二维数组，表示棋盘
    27.      */
    28.     private int[][] chessboard;
    30.     /**
    31.      * 创建一个数组，标记棋盘的各个位置是否被访问过
    32.      */
    33.     private boolean visited[];
    35.     /**
    36.      * 使用一个属性，标记是否棋盘的所有位置都被访问过，如果是true,表示成功
    37.      */
    38.     private boolean finished;
    40.     /**
    41.      * 马儿的位置
    42.      */
    43.     private class Point{
    45.         /**
    46.          * 行数
    47.          */
    48.         private int x;
    50.         /**
    51.          * 列数
    52.          */
    53.         private int y;
    55.         public Point() {
    56.         }
    58.         public Point(int x, int y) {
    59.             this.x = x;
    60.             this.y = y;
    61.         }
    62.         public Point(Point p) {
    63.             this.x = p.x;
    64.             this.y = p.y;
    65.         }
    66.     }
    68.     public HorseChessboard(int x, int y) {
    69.         this.x = x;
    70.         this.y = y;
    71.         this.chessboard = new int[x][y];
    72.         this.visited = new boolean[x * y];
    73.         this.finished = false;
    74.     }
    76.     /**
    77.      * 从指定位置开始
    78.      */
    79.     public void start(int row, int column) {
    80.         traversalChessboard(chessboard, row, column, 1);
    81.         //输出棋盘的最后情况
    82.         for (int[] rows : chessboard) {
    83.             for (int step : rows) {
    84.                 System.out.print(step + "\t");
    85.             }
    86.             System.out.println();
    87.         }
    88.     }
    90.     /**
    91.      * 完成骑士周游问题的算法
    92.      *
    93.      * @param chessboard 棋盘
    94.      * @param row        马儿当前的位置的行 从0开始
    95.      * @param column     马儿当前的位置的类 从0开始
    96.      * @param step       是第几步，初始位置就是第1步
    97.      */
    98.     public void traversalChessboard(int[][] chessboard, int row, int column, int step) {
    99.         chessboard[row][column] = step;
    100.         // 标记该位置已经访问
    101.         visited[row * this.x + column] = true;
    102.         // 获取当前位置可以走的下一个位置的集合
    103.         ArrayList<Point> ps = next(new Point(row, column));
    104.         //遍历ps
    105.         while (!ps.isEmpty()) {
    106.             // 取出下一个可以走的位置
    107.             Point p = ps.remove(0);
    108.             // 判断该点是否已经访问过
    109.             if (!visited[p.x * this.x + p.y]) {
    110.                 traversalChessboard(chessboard, p.x, p.y, step + 1);
    111.             }
    112.         }
    113.         //判断马儿是否完成了任务，使用step 和应该走的步数比较
    114.         //如果没有达到数量，刚表示没有完成任务，将整个棋盘置0
    115.         //说明:step < X * Y  成立的情况有两种
    116.         // 1、棋盘到目前位置，仍然没有走完
    117.         //2、棋盘处于一个回溯过程
    118.         if (step < this.x * this.y && !finished) {
    119.             chessboard[row][column] = 0;
    120.             visited[row * this.x + column] = false;
    121.         } else {
    122.             finished = true;
    123.         }
    124.     }
    126.     /**
    127.      * 功能:根据当前位置(Point)对象，计算马儿还能走哪些位置(Point)，并放入
    128.      * 到一个集合中(ArrayList),最多有8个位置
    129.      * @return
    130.      */
    131.     public ArrayList<Point> next(Point curPoint) {
    132.         //创建一个ArrayList
    133.         ArrayList<Point> ps = new ArrayList<>();
    135.         //创建一个Point
    136.         Point p1 = new Point();
    137.         //表示马儿可以走5这个位置
    138.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
    139.             ps.add(new Point(p1));
    140.         }
    141.         //表示马儿可以走6这个位置
    142.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
    143.             ps.add(new Point(p1));
    144.         }
    145.         //表示马儿可以走7这个位置
    146.         if ((p1.x = curPoint.x + 1) < this.x && (p1.y = curPoint.y - 2) >= 0) {
    147.             ps.add(new Point(p1));
    148.         }
    149.         //表示马儿可以走0这个位置
    150.         if ((p1.x = curPoint.x + 2) < this.x && (p1.y = curPoint.y - 1) >= 0) {
    151.             ps.add(new Point(p1));
    152.         }
    153.         //表示马儿可以走1这个位置
    154.         if ((p1.x = curPoint.x + 2) < this.x && (p1.y = curPoint.y + 1) < this.y) {
    155.             ps.add(new Point(p1));
    156.         }
    157.         //表示马儿可以走2这个位置
    158.         if ((p1.x = curPoint.x + 1) < this.x && (p1.y = curPoint.y + 2) < this.y) {
    159.             ps.add(new Point(p1));
    160.         }
    161.         //表示马儿可以走3这个位置
    162.         if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < this.y) {
    163.             ps.add(new Point(p1));
    164.         }
    165.         //表示马儿可以走4这个位置
    166.         if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < this.y) {
    167.             ps.add(new Point(p1));
    168.         }
    169.         return ps;
    170.     }
    172.     public static void main(String[] args) {
    173.         HorseChessboard horseChessboard = new HorseChessboard(8, 8);
    174.         long start = System.currentTimeMillis();
    175.         horseChessboard.start(0,0);
    176.         long end = System.currentTimeMillis();
    177.         System.out.println("耗时：" + (end - start) + "ms");
    178.     }
    180. }