图的深度优先搜索(DFS)的应用--马踏棋盘问题(骑士周游问题)

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

马踏棋盘游戏代码实现

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

如果使用回溯(就是深度优先搜索)来解决，假如马儿踏了53个点，走到了第53个，坐标(1,0) ，发现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回退…

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

使用前面的游戏来验证算法是否正确。

解决步骤和思路： https://blog.csdn.net/zhang0558/article/details/50497298

• 创建棋盘chessBoard，是一个二维数组

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

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

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

注意:马儿不同的走法(策略)，会得到不同的结果，效率也会有影响(优化)

public class HorsechessBoard {
    private static int X; // 表示列
    private static int Y; // 表示行
    private static boolean visited[]; // 是否被访问
    private static boolean finished; // 是否全部完成
    // 进行行走
    public static void traversal(int[][] arr, int row, int col, int step) {
        arr[row][col] = step;
        visited[row * X + col] = true;// 初始位置标记为已访问
        // 获取下一步集合
        ArrayList<Point> ps = next(new Point(col, row));
        sort(ps); //然后在traversal方法当中的ps进行排序：
        // 遍历集合
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);
            // 判断该点是否访问过
            if (!visited[p.y * X + p.x]) { // 没有访问过
                traversal(arr, p.y, p.x, step+1);
            }
        }
        if (step < X * Y && !finished) {
            arr[row][col] = 0;
            visited[row * X + col] = false;
        } else {
            finished = true;
        }
    }
    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;
                }
            }
        });
    }
    // 根据当前位置计算还有哪些位置可以走
    static int weizhi[][] = {{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};
    public static ArrayList<Point> next(Point cutPoint) {
        ArrayList<Point> ps = new ArrayList<Point>();
        Point p1 = new Point();
        // 判断是否可以走下一个位置
        if ((p1.x = cutPoint.x - 2) >= 0 && (p1.y = cutPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = cutPoint.x - 1) >= 0 && (p1.y = cutPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = cutPoint.x + 1) < X && (p1.y = cutPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = cutPoint.x + 2) < X && (p1.y = cutPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = cutPoint.x + 2) < X && (p1.y = cutPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = cutPoint.x + 1) < X && (p1.y = cutPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = cutPoint.x - 1) >= 0 && (p1.y = cutPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = cutPoint.x - 2) >= 0 && (p1.y = cutPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }
    public static void main(String[] args) {
        X = 9;//chg to 6
        Y = 9;
        int row = 5;
        int col = 5;
        int[][] arr = new int[X][Y];
        visited = new boolean[X * Y];
        System.out.println("开始");
        long start = System.currentTimeMillis();
        traversal(arr, row-1, col-1,1);
        long end = System.currentTimeMillis();
        System.out.println("耗时 = "+ (end-start)+" 毫秒");
        for(int[] rows:arr) {
            for(int step :rows) {
                System.out.print(step+"\t");
            }
            System.out.println();
        }
        System.out.println("结束");
    }
}