骑士周游列国问题

题目背景

国际象棋棋盘由共个黑白相间的块组成，每个棋子占据一个块。在国际象棋中，马的行走方式与中国象棋类似，即可以向以自身为角点的“日”字形的对角线移动。

经检验，当棋盘上有且仅有一个马时，无论其初始位置如何，均可沿规则允许的方式不重不漏地走遍棋盘的全部位置。

题目描述

已知棋盘上只有一个马，其初始位置为，求解一条满足上述要求的路径。

输入格式

每个数据一行，每行两个数字，分别代表初始行和初始列。数字间以空格隔开，行末尾为

输出格式

输出的矩阵，其中代表沿此路径行走时，到达方格的步数（初始位置步数记为，以此类推）。数字间以空格隔开（行末无空格），每行以结尾（含最后一行）。

注意：满足题意的路径可能不只有一种，输出时只输出一种结果。

样例 #1

样例输入 #1
1
2 6
样例输出 #1
1
2
3
4
5
6
7
8
33 30 57 20 55 18 5 2
58 21 32 29 6 3 54 17
31 34 23 56 19 52 1 4
22 59 28 35 64 7 16 53
45 24 63 8 43 36 51 14
60 9 44 27 48 15 42 39
25 46 11 62 37 40 13 50
10 61 26 47 12 49 38 41

提示

问题分析

解法 Ⅰ 普通的搜索回溯

首先对于骑士周游列国这一问题，我们很难找到一个多项式复杂度的算法，所以我们考虑搜索之后再进行剪枝的做法。

对于搜索，我们可以直接使用深度优先搜索的方式，在每一次记录当前所在的点坐标以及当前的步数，通过 x，y 的变化代表位置的转移，注意回溯即可

之后我们为了简化代码，采用定义偏移数组的方式进行位置的变化，数组表达如下

int dx[] = {1, 2, -1, -2, 2, 1, -1, -2}; int dy[] = {2, 1, 2, 1, -1, -2, -2, -1};

这八位的数组分别代表八个方向偏移的坐标，用来 x，y 来表示当前点的位置，用 nowx，nowy 代表

每次到达对应的 nowx，nowy 之后，我们再对这些点进行检测，如果超出棋盘范围，就舍去。

按照这样的方式，我们肯定能够在遍历所有可能性之后确定这条路线，代码如下

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <stack>
#define debug(x) cerr << #x << " = " << x << endl
#define int long long
#define all(x) (x).begin(), (x).end()
#define endl ('\n')

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 2e5 + 5, mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int dx[] = {1, 2, -1, -2, 2, 1, -1, -2};
int dy[] = {2, 1, 2, 1, -1, -2, -2, -1};
// const double eps = 1e-6;

int n, m, k;
int a[10][10];

bool In(int x, int y) // 判断是否在棋盘内
{
    if (x < 0 || x >= 8 || y < 0 || y >= 8)
        return false;
    else
        return true;
}

bool dfs(int x, int y, int step) // 暴力搜索
{
    if (step == 64)
        return true;
    vector<array<int, 3>> v;
    for (int i = 0; i < 8; i++)
    {
        int nowx = x + dx[i];
        int nowy = y + dy[i];
        if ((!In(nowx, nowy)) || a[nowx][nowy] != 0)
            continue;
        else{
            a[nowx][nowy] = step + 1;
            if(dfs(nowx, nowy, step + 1))
				return true;
            a[nowx][nowy] = 0;
        }

    }
    return false;
}

void solve()
{
    int x, y;
    cin >> x >> y;
    a[x][y] = 1;
    dfs(x, y, 1);
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 7; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << a[i][7] << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

但是此时我们的复杂度还是比较高的，经测试此时这样的算法只能完成 6*6 的棋盘搜索，对于 8*8 的表格是无法在 1s 之内完成的

我们可以考虑进行优化

解法 Ⅱ 搜索+剪枝优化

留意到，在搜索的过程之中，下一步前往的点之间是存在差异的，

例如有些点到达后再能够往后走的路径并不多，即到达后的选择较少，优先到访这样的点其实是更优的选择

为什么呢？

对于按顺序来访问的情况，我们可以认为每个格子之后访问的节点数量都差不多，假设每次走到节点的子节点有 3~4 个，那么整体的搜索路径大概是这样的三叉树或者四叉树（仅仅画出部分以示意，因为不同节点的子节点可能不同，最终结果并不是一颗满三叉树）

但是如果我们加入偏好，类似于启发式搜索中的估价函数，给这些节点都加上对应的权重，然后优先到访权重小的，假设此时每个节点只剩 1~2 个子节点，情况就大概是二叉树如下所示（仅仅画出部分，右侧其实还有很多多叉的节点，但是其实那些节点是不会被访问到的），对应的量级就下降了很多。

实际上，如果我们带上偏好的进行搜索，我们就能够节省进入死胡同之后退出来的成本，假设真的走入了一条没有结果的路，那样我们付出的成本也不算太高，因而能够优化整体的时间

我们这一优化的缺点在于，如果完成全部搜索来找到所有可能的路径，那么无论如何都要将所有的可能搜索完成。无论是用类似二叉树的情况或者是三叉树的情况搜索那么我们的优化就没有意义。

时间复杂度：由于剪枝之后的复杂度计算变得很复杂，不方便采用 O 表示法来计算，但是时间上大概还是在指数量级

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <stack>
#define debug(x) cerr << #x << " = " << x << endl
#define int long long
#define all(x) (x).begin(), (x).end()
#define endl ('\n')

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 2e5 + 5, mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int dx[] = {1, 2, -1, -2, 2, 1, -1, -2};
int dy[] = {2, 1, 2, 1, -1, -2, -2, -1};
// const double eps = 1e-6;

int n, m, k;
int a[10][10];

bool In(int x, int y)
{
    if (x < 0 || x >= 8 || y < 0 || y >= 8)
        return false;
    else
        return true;
}

int get_weight(int x, int y) {
    int temp_x, temp_y, weight = 0;
    for (int i = 0; i < 8; i++)
    {
        temp_x = x + dx[i], temp_y = y + dy[i];
        if (In(temp_x, temp_y) && a[temp_x][temp_y] == 0)
            weight++;
    }
    return weight;
}

bool dfs(int x, int y, int step)
{
    // cout << x << " " <<  y << endl;
    if (step == 64)
        return true;
    // cout << x << " " << y << endl;
    vector<array<int, 3>> v;
    for (int i = 0; i < 8; i++)
    {
        int nowx = x + dx[i];
        int nowy = y + dy[i];
        if ((!In(nowx, nowy)) || a[nowx][nowy] != 0)
            continue;
        else{
            v.push_back({get_weight(nowx, nowy), nowx, nowy});
        }

    }
    sort(v.begin(), v.end());
    for (auto temp: v){
        int nowx = temp.at(1), nowy = temp.at(2);
        // cout << nowx << " " << nowy << endl;
        a[nowx][nowy] = step + 1;
        if (dfs(nowx, nowy, step + 1))
            return true;
        a[nowx][nowy] = 0;
    }
    return false;
}

void solve()
{
    int x, y;
    cin >> x >> y;
    a[x][y] = 1;
    dfs(x, y, 1);
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 7; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << a[i][7] << endl;
    }
    // checkAns(x, y);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

解法 Ⅲ Trick 解法

在此之外，其实还有一种更为快速，但是有一点投机取巧性质的做法

留意到在题目所给的样例中，从 64 是可以走到 1 的，那这样这一条路径就形成了一条环，如下所示

1 -> 2 -> 3 -> ... -> 64 -> 1...

那按照这样的方式，这一条环覆盖了棋盘上的所有点，那么如果我们只需要找到一条合法的解，且棋盘的大小不变的情况下，我们可以通过将这条环进行移动来构造可行解。

例如我们现在的起点在样例给的答案中的第 15 个位置上，那么我让到访这个点之前的所有点都回退 15 位，这样子就能把原本的答案改写成为由该位置出发的一个可行解。

为了防止超过 64，只需要进行取模即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;

int old[8][8] = {{33, 30, 57, 20, 55, 18, 5, 2}, {58, 21, 32, 29, 6, 3, 54, 17}, {31, 34, 23, 56, 19, 52, 1, 4},
                 {22, 59, 28, 35, 64, 7, 16, 53}, {45, 24, 63, 8, 43, 36, 51, 14}, {60, 9, 44, 27, 48, 15, 42, 39},
                 {25, 46, 11, 62, 37, 40, 13, 50}, {10, 61, 26, 47, 12, 49, 38, 41}};

int main(){
    int x, y;
    cin >> x >> y;
    for (int i = 0; i < 8; i ++){
        for (int j = 0; j < 8; j ++){
            int temp = (old[i][j] - old[x][y] + 1 + 64) % 64;
            cout << (temp == 0 ? 64 : temp) << " \n"[j == 7];
        }
    }
    return 0;
}

时间复杂度：这时其实我们只是进行一个数字的转写，总共只需要遍历棋盘一次(64 次)，复杂度在常数级