【数据结构与算法】骑士周游算法/马踏棋盘算法的介绍和程序实现

1. 马踏棋盘算法介绍

将马随机放在国际象棋8×8棋盘的某个方格中，马按走棋规则(马走日字)不断的进行移动

要求每个方格只进入一次，走遍棋盘上全部64个方格(即移动63次)

如下所示为一个方格的马能移动的位置

2. 马踏棋盘算法的原理

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

假如马儿踏了53个点，坐标为(1,0)，发现没有位置可以移动了，就只能进行回溯，查看其他的路径。不断的进行移动和回溯就能走遍所有方格

可以使用贪心算法(greedyalgorithm)对马踏棋盘问题进行优化。先走当前位置的下一个位置的下一个位置个数较小，的下一个位置

3. 马踏棋盘算法的程序实现

马踏棋盘算法的程序实现如下：

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

public class HorseChessboard {

    // 棋盘的最大行数，从1开始
    private static int MAX_ROW;
    // 棋盘的最大列数，从1开始
    private static int MAX_COLUME;

    // 标记棋盘的各个位置是否被访问过。true为已访问，false为未访问
    private static boolean[] visited;
    // 如果棋盘所有位置都被访问，则为true，否则为false
    private static boolean finished;

    public static void main(String[] args) {
        MAX_ROW = 8;
        MAX_COLUME = 8;
        visited = new boolean[MAX_ROW * MAX_COLUME];

        // 马开始的行号，从1开始
        int startRow = 1;
        // 马开始的列号，从1开始
        int startColumn = 1;

        // 创建棋盘。用来保存每个方格都是第几步进入的
        int[][] chessboard = new int[MAX_ROW][MAX_COLUME];

        // 测试骑士周游问算法耗时
        System.out.println("骑士周游算法，开始运行");
        long startTime = System.currentTimeMillis();
        traversalChessboard(chessboard, startRow - 1, startColumn - 1, 1);
        long endTime = System.currentTimeMillis();
        System.out.println("共耗时: " + (endTime - startTime) + "毫秒");

        // 输出棋盘各个位置都是第几步进入的
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    // 根据当前位置，将马能走的下一步位置放入一个集合中。下一步位置最多有8种可能
    public static ArrayList getNextPoints(Point currentPoint) {
        ArrayList nextPoints = new ArrayList();

        Point tmpPoint = new Point();

        // 先进行赋值，在进行比较
        // 表示马儿可以走5这个位置
        if ((tmpPoint.x = currentPoint.x - 2) >= 0 && (tmpPoint.y = currentPoint.y - 1) >= 0) {
            nextPoints.add(new Point(tmpPoint));
        }
        // 判断马儿可以走6这个位置
        if ((tmpPoint.x = currentPoint.x - 1) >= 0 && (tmpPoint.y = currentPoint.y - 2) >= 0) {
            nextPoints.add(new Point(tmpPoint));
        }
        // 判断马儿可以走7这个位置
        if ((tmpPoint.x = currentPoint.x + 1) < MAX_COLUME && (tmpPoint.y = currentPoint.y - 2) >= 0) {
            nextPoints.add(new Point(tmpPoint));
        }
        // 判断马儿可以走0这个位置
        if ((tmpPoint.x = currentPoint.x + 2) < MAX_COLUME && (tmpPoint.y = currentPoint.y - 1) >= 0) {
            nextPoints.add(new Point(tmpPoint));
        }
        // 判断马儿可以走1这个位置
        if ((tmpPoint.x = currentPoint.x + 2) < MAX_COLUME && (tmpPoint.y = currentPoint.y + 1) < MAX_ROW) {
            nextPoints.add(new Point(tmpPoint));
        }
        // 判断马儿可以走2这个位置
        if ((tmpPoint.x = currentPoint.x + 1) < MAX_COLUME && (tmpPoint.y = currentPoint.y + 2) < MAX_ROW) {
            nextPoints.add(new Point(tmpPoint));
        }
        // 判断马儿可以走3这个位置
        if ((tmpPoint.x = currentPoint.x - 1) >= 0 && (tmpPoint.y = currentPoint.y + 2) < MAX_ROW) {
            nextPoints.add(new Point(tmpPoint));
        }
        // 判断马儿可以走4这个位置
        if ((tmpPoint.x = currentPoint.x - 2) >= 0 && (tmpPoint.y = currentPoint.y + 1) < MAX_ROW) {
            nextPoints.add(new Point(tmpPoint));
        }

        return nextPoints;
    }

    // 将当前位置的下一个位置，按当前位置的下一个位置的下一个位置个数，从小到大进行排列
    // nextPoints是当前位置，马能走的下一步位置集合
    // 比如当前位置的下一个位置A和B，A的下一个位置有2个，B的下一个位置有3个，则A在前，B在后
    public static void sortNextPoints(ArrayList nextPoints) {
        nextPoints.sort(new Comparator() {
            @Override
            public int compare(Point point1, Point point2) {
                // 获取point1的下一个位置的个数
                int point1NextPointCount = getNextPoints(point1).size();
                // 获取point2的下一个位置的个数
                int point2NextPointCount = getNextPoints(point2).size();

                // 按从小到大排列
                if (point1NextPointCount < point2NextPointCount) {
                    return -1;
                } else if (point1NextPointCount == point2NextPointCount) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }

    // 骑士周游算法实现
    // 参数pointX: 马当前的point X
    // 参数pointY: 马当前的point Y
    // 参数step: 马已经走的步数
    public static void traversalChessboard(int[][] chessboard, int pointX, int pointY, int step) {
        chessboard[pointX][pointY] = step;

        // 标记当前位置为已访问
        visited[pointY * MAX_COLUME + pointX] = true;

        // 获取当前位置可以走的下一个位置的集合
        ArrayList nextPoints = getNextPoints(new Point(pointX, pointY));

        // 使用贪心算法进行优化
        // 将当前位置的下一个位置，按当前位置的下一个位置的下一个位置个数，从小到大进行排列(非递减, 即具有相同大小的递增排列)
        // 这样就会先走当前位置的下一个位置的下一个位置个数较小，的下一个位置
        sortNextPoints(nextPoints);

        // 遍历nextPoints。如果下一个位置没有访问，则进行访问
        // 如果都访问过，会执行完该方法，进行回溯
        for (Point nextPoint : nextPoints) {
            if (!visited[nextPoint.y * MAX_COLUME + nextPoint.x]) {
                traversalChessboard(chessboard, nextPoint.x, nextPoint.y, step + 1);
            }
        }

        // 如果步数还不够，且finished为false，则表示还未走完，表示走不通了
        // 则在回溯前，需要对这一步已经设置的状态进行重置
        if (step < MAX_ROW * MAX_COLUME && !finished) {
            chessboard[pointX][pointY] = 0;
            visited[pointY * MAX_COLUME + pointX] = false;
        } else {
            // 如果步数够了，则finished为true
            // 如果步数够了，finished为true，则还是finished为true
            finished = true;
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

运行程序，最后显示的结果如下：

骑士周游算法，开始运行
共耗时: 26毫秒
1	38	15	30	61	40	13	28	
16	31	36	39	14	29	58	41	
37	2	49	60	55	62	27	12	
32	17	54	35	52	59	42	57	
3	48	33	50	63	56	11	26	
18	21	64	53	34	51	8	43	
47	4	23	20	45	6	25	10	
22	19	46	5	24	9	44	7
1
2
3
4
5
6
7
8
9
10