马踏棋盘算法_马踏棋盘的规则

马踏棋盘算法

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

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

2.马踏棋盘游戏代码实现

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

• 代码：

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) {
        System.out.println("骑士周游：");
        X = 8;
        Y = 8;
        int row = 1; //骑士初始行
        int col = 1; //骑士初始列
        //创建棋盘
        int[][] chessboard = new int[X][Y];
        //初始值都为false
        visited = new boolean[X * Y];
        long start = System.currentTimeMillis();
        traversalChessboard(chessboard, row -1, col - 1, 0);
        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 骑士当前位置的行
     * @param col 骑士当前位置的列
     * @param step 当前骑士走的是第几步，初始时为1
     */
    public static void traversalChessboard(int[][] chessboard, int row, int col, int step){
        //记录骑士第step步访问该位置
        chessboard[row][col] = step;
        //将该位置记录为已访问
        visited[row * X + col] = true;
        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> next = next(new Point(col, row));
        //对next进行排序  排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
        sort(next);

        while (!next.isEmpty()){
            //取出骑士下一个走的位置
            Point p = next.remove(0);
            //判断下一个位置是否已经访问过，没有访问则访问
            if(!visited[p.y * X + p.x]){
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }

        //判断骑士是否完成周游，如果骑士走的步数小于 X * Y 则表示没有完成任务，此时，将整个棋盘置0
        //step < X * Y有两种情况：1.棋盘还没有走完  2.棋盘此时正在回溯
        if(step < X * Y - 1  && !finished){
            chessboard[row][col] = 0;
            visited[row * X + col] = false;
        }else {
            finished  = true;
        }

    }

    /**
     * 根据当前的位置(Point为java的内置对象)，计算骑士下一步能走的位置，最多有8个位置
     * @param curPoint
     * @return 包含当前位置能访问的下一个位置的坐标！！！(坐标横着的是X轴！！！)
     */
    public static ArrayList<Point> next(Point curPoint){
        ArrayList<Point> nextList = new ArrayList<>();
        Point p = new Point();

        //表示骑士可以走5这个位置
        if((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y - 1) >= 0){
            nextList.add(new Point(p));
        }

        //表示骑士可以走6这个位置
        if((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y - 2) >= 0){
            nextList.add(new Point(p));
        }

        //表示骑士可以走7这个位置
        if((p.x = curPoint.x + 1) < X && (p.y = curPoint.y - 2) >= 0){
            nextList.add(new Point(p));
        }

        //表示骑士可以走0这个位置
        if((p.x = curPoint.x + 2) < X && (p.y = curPoint.y - 1) >= 0){
            nextList.add(new Point(p));
        }

        //表示骑士可以走1这个位置
        if((p.x = curPoint.x + 2) < X && (p.y = curPoint.y + 1) < Y){
            nextList.add(new Point(p));
        }

        //表示骑士可以走2这个位置
        if((p.x = curPoint.x + 1) < X && (p.y = curPoint.y + 2) < Y){
            nextList.add(new Point(p));
        }

        //表示骑士可以走3这个位置
        if((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < Y){
            nextList.add(new Point(p));
        }

        //表示骑士可以走4这个位置
        if((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < Y){
            nextList.add(new Point(p));
        }

        return  nextList;
    }


    //根据当前这一步的所有的下一步的选择位置，进行非递减排序，减少回溯的次数
    private static void sort(ArrayList<Point> next) {
        next.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                //获取o1下一步的所有位置个数
                int count1 = next(o1).size();
                //获取o2下一步的所有位置个数
                int count2 = next(o2).size();
                if(count1 < count2){
                    return -1;
                }else if(count1 == count2){
                    return 0;
                }else {
                    return 1;
                }
            }
        });
    }
}
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

• 结果：