骑士周游问题

基本介绍

（1）骑士周游问题也被称为马踏棋盘算法

（2）将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。

实现思路

骑士周游问题(马踏棋盘问题)实际上是图的深度优先搜索(DFS)的应用。

（1）创建棋盘chessBoard，是一个二维数组。

（2）将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合中(ArrayList),最多有8个位置，每走一步，就令step+1。

（3）遍历ArrayList中存放的所有位置，看看哪个可以走通,如果走通，就继续，走不通，就回溯。

（4）判断马儿是否完成了任务，使用step和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置0。

注意：马儿不同的走法，会得到不同的结果，也会影响效率。这里就可以使用贪心算法进行优化，对ArrayList中存放的所有位置按照下一个可以走通结点集合的个数进行非递减排序。

代码实现

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

public class KnightTravel {
    private static int X; // 棋盘列数
    private static int Y; // 棋盘行数

    private static boolean[] visited;

    private static boolean finished;

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int col = 1;
        int[][] chessBoard = new int[X][Y];
        visited = new boolean[X * Y];
        long startTime = System.currentTimeMillis();
        knightTravel(chessBoard, row - 1, col - 1, 1);
        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime + "ms");
        for (int[] rows : chessBoard) {
            System.out.println(Arrays.toString(rows));
        }
    }

    /**
     * @param chessBoard 棋盘
     * @param row        当前行
     * @param col        当前列
     * @param step       当前步数
     */
    public static void knightTravel(int[][] chessBoard, int row, int col, int step) {
        chessBoard[row][col] = step;
        visited[row * X + col] = true; // 从左到右，从上至下、
        ArrayList<Point> points = next(new Point(col, row));
        sort(points);
        while (!points.isEmpty()) {
            Point p = points.remove(0);
            if (!visited[p.y * X + p.x]) {
                knightTravel(chessBoard, p.y, p.x, step + 1);
            }
        }
        if (step < X * Y && !finished) {
            chessBoard[row][col] = 0;
            visited[row * X + col] = false;
        } else {
            finished = true;
        }
    }

    // 功能:根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList)，最多有8个位置
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> points = new ArrayList<>();
        Point p1 = new Point();
        // 5
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            points.add(new Point(p1));
        }
        // 6
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            points.add(new Point(p1));
        }
        // 7
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            points.add(new Point(p1));
        }
        // 0
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            points.add(new Point(p1));
        }
        // 1
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            points.add(new Point(p1));
        }
        // 2
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            points.add(new Point(p1));
        }
        // 3
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            points.add(new Point(p1));
        }
        // 4
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            points.add(new Point(p1));
        }
        return points;
    }

    public static void sort(ArrayList<Point> points) {
        points.sort((o1, o2) -> {
            int size1 = next(o1).size();
            int size2 = next(o2).size();
            return size1 - size2;
        });
    }
}