写在前面

• 数据结构与算法全文

骑士周游问题（马踏棋盘）

class HorseChessboard {
    private static int X;
    private static int Y;
    //创建一个数组，标记棋盘的各个位置是否被访问过
    private static boolean visited[][];
    //标记棋盘的是否都被访问
    private static boolean finished; //true 表示成功0

    public static void main(String[] args) {
        X=8;
        Y=8;
        int row = 1;
        int column = 1;
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X][Y];
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        for (int[] ints : chessboard) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * @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][column] = true;
        //获取当前位置可以走的集合
        //point.x 对应列，point.y对应行
        ArrayList<Point> points = next(new Point(column, row));
        //对points的所有选择的下一步的可能性进行非递增排序
        sort(points);
        //遍历points
        while (!points.isEmpty()) {
            //取出可以走的位置
            Point point = points.remove(0);
            if (!visited[point.y][point.x]) { //没有访问过
                traversalChessboard(chessboard, point.y, point.x, step + 1);
            }
        }
        //是否完成任务，使用step判断，如果没有达到数量，则表示没有完成任务，将这个位置还原
        //step < X * Y 棋盘到目前为止仍然没有走完；棋盘处于一个回溯过程
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row][column] = false;
        } else {
            finished = true;
        }
    }
    //根据当前位置，计算还能走哪些位置，并放到集合中
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> points = new ArrayList<>();
        Point p = new Point();
        //大于0还能在棋盘内
        //5
        if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y - 1) >= 0) {
            points.add(new Point(p));
        }
        if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y - 2) >= 0) {
            points.add(new Point(p));
        }
        if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y - 2) >= 0) {
            points.add(new Point(p));
        }
        if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y - 1) >= 0) {
            points.add(new Point(p));
        }
        if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y + 1) < Y) {
            points.add(new Point(p));
        }
        if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y + 2) < Y) {
            points.add(new Point(p));
        }
        if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < Y) {
            points.add(new Point(p));
        }
        if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < Y) {
            points.add(new Point(p));
        }
        return points;
    }

    //非递减排序 1,2,2,2,3,4,5 在递增的过程中，可以有相等的数
    //根据当前这一步的所有下一步的选择位置，进行非递减排序
    public static void sort(ArrayList<Point> points) {
        //对points中的所有选择的下一步进行非递减排序，先尝试最少的可能性
        points.sort((o1, o2) -> next(o1).size() - next(o2).size());
    }
}
复制代码

总结

整体思想是，针对一个点计算这个点的下一步的位置next(Point curPoint)，并假设这个是可行的chessboard[row][column] = step; visited[row][column] = true;，进行递归尝试，直到这个点的所有可能性尝试完后退出。当失败的退出条件为这个点的所有可能都尝试完成，但是仍然不能走完所有位置，那么就证明这个点假设错误，要将这个点的假设还原chessboard[row][column] = 0; visited[row][column] = false;

finished标志位，当走到最后一步成功的时候，则需要改变标志位finished。如果没有finished标志位，假设这个点，有A B两种可能性，A是正确的选择，此时先进行A，A正常回来后，没有finished表示A已经完成任务，仍需要进行B，但是B返回后，由于没有保存A结果的正确，那么就会对该访问点的进行错误清除，所以当找到正确的结果，需要修改标识位finished，保证找到正确的路径后，可以一直回溯到最开始

优化，重写sort方法，针对这次选择中的可能性，计算出这些可能性中的下一次可能，结合贪心算法的思想，优先选择下一步可能性少的可能性先尝试。