Java编程：马踏棋盘算法（骑士周游问题）

马踏棋盘算法介绍和游戏演示

1. 马踏棋盘算法也被称为骑士周游问题
2. 将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格
3. 游戏演示: http://www.4399.com/flash/146267_2.htm

马踏棋盘游戏代码分析

1. 马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
2. 如果使用回溯（就是深度优先搜索）来解决，假如马儿踏了53个点，如图：走到了第53个，坐标（1,0），发现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回溯…… ，思路分析+代码实现
3. 分析第一种方式的问题，并使用贪心算法（greedyalgorithm）进行优化。解决马踏棋盘问题.
4. 使用前面的游戏来验证算法是否正确。
   

图解

代码实现

package horse;

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

public class HorseChessBoard {
    private static int X;   // 棋盘的列
    private static int Y;   // 棋盘的行
    // 创建一个数组，标记棋盘的各个位置是否被访问过
    private static boolean[] visited;
    // 使用一个属性，标记是否棋盘的所有位置都被访问
    private static boolean finished;    // 如果为true，表示成功

    public static void main(String[] args) {
        // 测试骑士周游算法是否正确
        X = 8;
        Y = 8;
        int row = 1;    // 马儿初始位置的行，从1开始编号
        int column = 1; // 马儿初始位置的列，从1开始编号
        // 创建棋盘
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];   // 初始值都是false
        // 测试一下耗时
        long start = System.currentTimeMillis();
        traversalChessBoard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时：" + (end - start) + "毫秒");
        // 输出棋盘
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 完成马踏棋盘（骑士周游问题）的算法
     *
     * @param chessboard 棋盘
     * @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 * X + column] = true;   // 当前位置标记为已访问
        // 获取当前位置可以走的下一个位置的集合
        ArrayList<Point> ps = next(new Point(column, row));
        // 对ps进行排序，排序的规则就是对ps所有的Point对象的下一步的位置，进行非递减排序
        sort(ps);
        // 遍历ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0); // 取出下一个可以走的位置
            // 判断该点是否已经访问过
            if (!visited[p.y * X + p.x]) {  // 说明还没有访问过
                traversalChessBoard(chessboard, p.y, p.x, step + 1);
            }
        }
        // 判断马儿是否完成了任务，使用step和应该走的步数比较，
        // 如果没有达到数量，则表示没有完成任务，将整个棋盘置0
        // 说明：step < X * Y成立的情况有两种
        // ① 棋盘到目前为止，仍然没有走完
        // ② 棋盘已经走完，目前处于回溯过程中
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    /**
     * 功能：根据当前位置（Point对象），计算马儿还能走哪些位置（Point）
     * 并放入到一个集合中（ArrayList），最多八个位置
     *
     * @param curPoint 当前位置
     * @return 能走的位置集合
     */
    public static ArrayList<Point> next(Point curPoint) {
        // 创建一个ArrayList
        ArrayList<Point> ps = new ArrayList<>();
        // 创建一个point
        Point p1 = new Point();
        // 周遭所有可能
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    // 根据当前这一步的所有的下一步的选择位置，进行非递减排序，减少回溯的次数
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                // 获取o1 点的下一步的所有位置
                /*int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }*/
                // 注释部分简化
                return Integer.compare(next(o1).size(), next(o2).size());
            }
        });
    }

}

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