八数码问题(8-Puzzle Problem)(8-puzzle problem)

八数码问题(8-Puzzle Problem)

P1379 八数码难题 – 洛谷
题目概述:在 \(3 \times 3\) 的棋盘上摆放着 \(8\) 个棋子,棋子的编号分别为 \(1\) 到 \(8\),空格则用 \(0\) 表示。与空格直接相连的棋子可以移至空格中,这样原来棋子的位置就成为空格。现给出一种初始布局,求到达目标布局的最少步数。为简单起见,目标布局总是如下:
123
804
765

P1379 八数码难题 – 洛谷
题目概述:在 \(3 \times 3\) 的棋盘上摆放着 \(8\) 个棋子,棋子的编号分别为 \(1\) 到 \(8\),空格则用 \(0\) 表示。与空格直接相连的棋子可以移至空格中,这样原来棋子的位置就成为空格。现给出一种初始布局,求到达目标布局的最少步数。为简单起见,目标布局总是如下:

123
804
765

本题是一道经典的搜索题,下面将介绍几种常见的搜索算法。以下所有代码均需要 C++11 标准。

朴素 BFS

通过对题目的简单分析,很容易写出朴素的 BFS 代码。进行访问标记时,可以利用哈希的思想,将矩阵转化为整数,再用 存储。由于本题的数据范围较小,朴素的 BFS 算法也能通过本题测试,但是效率较低。具体代码如下:

std::unordered_set
#include <bits/stdc++.h>

using namespace std;
const int tar_x = 2, tar_y = 2, target = 123804765;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
struct Status {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    int t;           // step number

    explicit Status(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }
};

int bfs(int num) {
    queue<Status> q;
    unordered_set<int> vis;
    q.emplace(num);
    vis.insert(num);
    while (!q.empty()) {
        Status now = q.front();
        q.pop();
        if (now.x == tar_x && now.y == tar_y && now.to_int() == target)
            return now.t;
        ++now.t;
        int x = now.x, y = now.y;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[x][y], now.maze[tx][ty]);
            now.x = tx;
            now.y = ty;
            if (!vis.count(now.to_int())) {
                q.push(now);
                vis.insert(now.to_int());
            }
            now.x = x;
            now.y = y;
            swap(now.maze[x][y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << bfs(num) << endl;
    return 0;
}

双向 BFS

对于本题这类已知初始状态和目标状态的题目,可以考虑双向 BFS。在搜索开始前,同时将初始状态和目标状态放进 BFS 队列中。搜索过程中,除了要标记每种状态是否被访问过,还要标记访问时的搜索方向以及从对应起点出发的步数。当一种状态被两个方向同时搜到时,这两个方向的步数之和就是所求答案。BFS 的性质保证了这一答案一定是最小值。这样的算法称为 Meet in the Middle,通过将实际拓展的层数减半,大大提高了搜索效率,避免了许多不必要的状态拓展。具体代码如下:

#include <bits/stdc++.h>

using namespace std;
const int target = 123804765;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
struct Matrix {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    bool d;          // bfs direction (true: forward, false: back)
    int t;           // step number

    explicit Matrix(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        if (num == target)
            d = false;
        else
            d = true;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }
};

int bfs(int num) {
    queue<Matrix> q;
    unordered_map<int, pair<int, bool>> vis;
    q.emplace(target);
    vis[target] = make_pair(0, false);
    q.emplace(num);
    vis[num] = make_pair(0, true);
    while (!q.empty()) {
        Matrix now = q.front();
        q.pop();
        if (vis.count(now.to_int()) && vis[now.to_int()].second != now.d)  // meet in the middle
            return now.t + vis[now.to_int()].first;
        ++now.t;
        int x = now.x, y = now.y;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
            swap(now.x, tx);
            swap(now.y, ty);
            if (!vis.count(now.to_int()) || vis[now.to_int()].second != now.d) {
                q.push(now);
                vis[now.to_int()] = make_pair(now.t, now.d);
            }
            swap(now.x, tx);
            swap(now.y, ty);
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << bfs(num) << endl;
    return 0;
}

A*

A* 算法是一种启发式搜索,即利用估值函数进行剪枝,以避免盲目搜索中许多不必要的状态拓展。A* 算法以 BFS 为基础,用优先队列代替 BFS 队列,以估值函数为优先级。A* 算法中,每个状态的估值函数由两部分组成,即 \(f(x)=g(x)+h(x)\),其中 \(g(x)\) 是已经走过的步数,\(h(x)\) 是预估到达终点至少还要走的步数,两者之和 \(f(x)\) 即这一状态的估值函数。因此,为确保算法正确,\(h(x)\) 的值一定不大于实际距离终点的步数,即 $f(x) 的值一定不大于实际总步数。本题中,可以使用每个棋子到目标位置的曼哈顿距离作为其 \(h(x)\)。容易证明,该函数满足上述条件。具体代码如下:

#include <bits/stdc++.h>

using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int pos_x[] = {2, 1, 1, 1, 2, 3, 3, 3, 2};
const int pos_y[] = {2, 1, 2, 3, 3, 3, 2, 1, 1};
struct Status {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    int t;           // step number

    explicit Status(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int h() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j)
                if (maze[i][j] != 0 &&
                    (i != pos_x[maze[i][j]] || j != pos_y[maze[i][j]]))
                    ++ans;
        return ans;
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }

    bool operator<(const Status& other) const {
        return h() + t > other.h() + other.t;  // compare by f(x)
    }
};

int a_star(int num) {
    priority_queue<Status, vector<Status>> pq;
    set<int> vis;
    pq.push(Status(num));
    vis.insert(num);
    while (!pq.empty()) {
        if (pq.top().h() == 0) return pq.top().t;
        Status now = pq.top();
        pq.pop();
        ++now.t;
        for (int i = 0; i < 4; ++i) {
            int tx = now.x + dx[i], ty = now.y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
            swap(now.x, tx);
            swap(now.y, ty);
            if (!vis.count(now.to_int())) {
                pq.push(now);
                vis.insert(now.to_int());
            }
            swap(now.x, tx);
            swap(now.y, ty);
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << a_star(num) << endl;
    return 0;
}

IDA*

IDA* 就是基于迭代加深搜索的 A* 算法。所谓迭代加深,就是在 DFS 的基础上控制其搜索深度,一旦超过深度限制就停止搜索,若当前深度无法得到答案,则再增加深度限制。迭代加深搜索结合了 DFS 与 BFS 的优点,不需要占用大量空间,能够支持回溯,同时可以快速找到最优解,尽可能避免进入过深的枝节。此外,由于 迭代加深算法基于 DFS,其实现难度也较低。IDA* 则是在迭代加深搜素的基础上加上了估值函数的剪枝。本题的估值函数在 A* 中已经说明。具体代码如下:

#include <bits/stdc++.h>

using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int pos_x[] = {2, 1, 1, 1, 2, 3, 3, 3, 2};
const int pos_y[] = {2, 1, 2, 3, 3, 3, 2, 1, 1};
int lim;  // depth limit
int m[5][5];

int h() {
    int ans = 0;
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            if (m[i][j] != 0)
                ans += abs(i - pos_x[m[i][j]]) + abs(j - pos_y[m[i][j]]);
    return ans;
}

bool dfs(int x, int y, int t, int lx, int ly) {
    int dis = h();
    if (t + dis > lim) return false;  // prune with f(x)
    if (dis == 0) return true;
    for (int i = 0; i < 4; ++i) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
        if (tx == lx && ty == ly) continue;
        swap(m[x][y], m[tx][ty]);
        if (dfs(tx, ty, t + 1, x, y)) return true;
        swap(m[x][y], m[tx][ty]);
    }
    return false;
}

int main() {
    int num;
    cin >> num;
    int sx, sy;
    for (int i = 3; i >= 1; --i) {
        for (int j = 3; j >= 1; --j) {
            m[i][j] = num % 10;
            num /= 10;
            if (m[i][j] == 0) sx = i, sy = j;
        }
    }
    lim = 0;
    while (!dfs(sx, sy, 0, -1, -1)) ++lim;  // IDA*
    cout << lim << endl;
    return 0;
}
————————

八数码问题(8-Puzzle Problem)

< strong > p1379 eight digital puzzle – Luogu < / strong >
Title Overview: on the board of \ (3 \ times 3 \), there are \ (8 \) pieces, the numbers of which are \ (1 \) to \ (8 \), and the spaces are represented by \ (0 \). The pieces directly connected with the space can be moved to the space, so that the original position of the pieces becomes a space. An initial layout is given to find the minimum number of steps to reach the target layout. For simplicity, the target layout is always as follows:
one hundred and twenty-three
eight hundred and four
seven hundred and sixty-five

< strong > p1379 eight digital puzzle – Luogu < / strong >
Title Overview: on the board of \ (3 \ times 3 \), there are \ (8 \) pieces, the numbers of which are \ (1 \) to \ (8 \), and the spaces are represented by \ (0 \). The pieces directly connected with the space can be moved to the space, so that the original position of the pieces becomes a space. An initial layout is given to find the minimum number of steps to reach the target layout. For simplicity, the target layout is always as follows:

123
804
765

This question is a classic search question. The following will introduce several common search algorithms. All of the following codes require the C + + 11 standard.

朴素 BFS

Through the simple analysis of the topic, it is easy to write simple BFS code. When making access marks, we can use the idea of hash to convert the matrix into an integer and then store it. Because the data range of this problem is small, the simple BFS algorithm can also pass the test, but the efficiency is low. The specific codes are as follows:

std::unordered_set
#include <bits/stdc++.h>

using namespace std;
const int tar_x = 2, tar_y = 2, target = 123804765;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
struct Status {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    int t;           // step number

    explicit Status(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }
};

int bfs(int num) {
    queue<Status> q;
    unordered_set<int> vis;
    q.emplace(num);
    vis.insert(num);
    while (!q.empty()) {
        Status now = q.front();
        q.pop();
        if (now.x == tar_x && now.y == tar_y && now.to_int() == target)
            return now.t;
        ++now.t;
        int x = now.x, y = now.y;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[x][y], now.maze[tx][ty]);
            now.x = tx;
            now.y = ty;
            if (!vis.count(now.to_int())) {
                q.push(now);
                vis.insert(now.to_int());
            }
            now.x = x;
            now.y = y;
            swap(now.maze[x][y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << bfs(num) << endl;
    return 0;
}

双向 BFS

For this kind of problem with known initial state and target state, two-way BFS can be considered. Before the search starts, the initial state and target state are put into the BFS queue at the same time. In the search process, in addition to marking whether each state has been accessed, the search direction during access and the number of steps from the corresponding starting point should also be marked. When a state is searched in two directions at the same time, the sum of steps in the two directions is the answer. The nature of BFS ensures that this answer must be the minimum. This algorithm is called meet in the middle. By halving the number of layers actually expanded, it greatly improves the search efficiency and avoids many unnecessary state expansion. The specific codes are as follows:

#include <bits/stdc++.h>

using namespace std;
const int target = 123804765;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
struct Matrix {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    bool d;          // bfs direction (true: forward, false: back)
    int t;           // step number

    explicit Matrix(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        if (num == target)
            d = false;
        else
            d = true;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }
};

int bfs(int num) {
    queue<Matrix> q;
    unordered_map<int, pair<int, bool>> vis;
    q.emplace(target);
    vis[target] = make_pair(0, false);
    q.emplace(num);
    vis[num] = make_pair(0, true);
    while (!q.empty()) {
        Matrix now = q.front();
        q.pop();
        if (vis.count(now.to_int()) && vis[now.to_int()].second != now.d)  // meet in the middle
            return now.t + vis[now.to_int()].first;
        ++now.t;
        int x = now.x, y = now.y;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
            swap(now.x, tx);
            swap(now.y, ty);
            if (!vis.count(now.to_int()) || vis[now.to_int()].second != now.d) {
                q.push(now);
                vis[now.to_int()] = make_pair(now.t, now.d);
            }
            swap(now.x, tx);
            swap(now.y, ty);
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << bfs(num) << endl;
    return 0;
}

A*

A * algorithm is a heuristic search, that is, pruning using the estimation function to avoid many unnecessary state expansion in blind search. A * algorithm is based on BFS, uses priority queue instead of BFS queue, and takes estimation function as priority. In a * algorithm, the estimation function of each state consists of two parts, namely \ (f (x) = g (x) + H (x) \, where \ (g (x) \) is the number of steps that have been taken and \ (H (x) \) is the number of steps that must be taken at least to reach the end point. The sum of the two \ (f (x) \) is the estimation function of this state. Therefore, in order to ensure the correctness of the algorithm, the value of \ (H (x) \) must not be greater than the actual number of steps from the end point, that is, the value of $f (x) must not be greater than the actual total number of steps. In this question, you can use the Manhattan distance from each chess piece to the target position as its \ (H (x) \). It is easy to prove that the function satisfies the above conditions. The specific codes are as follows:

#include <bits/stdc++.h>

using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int pos_x[] = {2, 1, 1, 1, 2, 3, 3, 3, 2};
const int pos_y[] = {2, 1, 2, 3, 3, 3, 2, 1, 1};
struct Status {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    int t;           // step number

    explicit Status(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int h() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j)
                if (maze[i][j] != 0 &&
                    (i != pos_x[maze[i][j]] || j != pos_y[maze[i][j]]))
                    ++ans;
        return ans;
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }

    bool operator<(const Status& other) const {
        return h() + t > other.h() + other.t;  // compare by f(x)
    }
};

int a_star(int num) {
    priority_queue<Status, vector<Status>> pq;
    set<int> vis;
    pq.push(Status(num));
    vis.insert(num);
    while (!pq.empty()) {
        if (pq.top().h() == 0) return pq.top().t;
        Status now = pq.top();
        pq.pop();
        ++now.t;
        for (int i = 0; i < 4; ++i) {
            int tx = now.x + dx[i], ty = now.y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
            swap(now.x, tx);
            swap(now.y, ty);
            if (!vis.count(now.to_int())) {
                pq.push(now);
                vis.insert(now.to_int());
            }
            swap(now.x, tx);
            swap(now.y, ty);
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << a_star(num) << endl;
    return 0;
}

IDA*

Ida * is an a * algorithm based on iterative deepening search. The so-called iterative deepening is to control the search depth based on DFS. Once the depth limit is exceeded, the search will be stopped. If the current depth cannot be answered, the depth limit will be added. Iterative deepening search combines the advantages of DFS and BFS, does not need to occupy a lot of space, can support backtracking, can quickly find the optimal solution, and avoid entering too deep branches as much as possible. In addition, because the iterative deepening algorithm is based on DFS, its implementation difficulty is also low. Ida * adds the pruning of the estimation function on the basis of iterative deepening search. The valuation function of this problem has been described in a *. The specific codes are as follows:

#include <bits/stdc++.h>

using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int pos_x[] = {2, 1, 1, 1, 2, 3, 3, 3, 2};
const int pos_y[] = {2, 1, 2, 3, 3, 3, 2, 1, 1};
int lim;  // depth limit
int m[5][5];

int h() {
    int ans = 0;
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            if (m[i][j] != 0)
                ans += abs(i - pos_x[m[i][j]]) + abs(j - pos_y[m[i][j]]);
    return ans;
}

bool dfs(int x, int y, int t, int lx, int ly) {
    int dis = h();
    if (t + dis > lim) return false;  // prune with f(x)
    if (dis == 0) return true;
    for (int i = 0; i < 4; ++i) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
        if (tx == lx && ty == ly) continue;
        swap(m[x][y], m[tx][ty]);
        if (dfs(tx, ty, t + 1, x, y)) return true;
        swap(m[x][y], m[tx][ty]);
    }
    return false;
}

int main() {
    int num;
    cin >> num;
    int sx, sy;
    for (int i = 3; i >= 1; --i) {
        for (int j = 3; j >= 1; --j) {
            m[i][j] = num % 10;
            num /= 10;
            if (m[i][j] == 0) sx = i, sy = j;
        }
    }
    lim = 0;
    while (!dfs(sx, sy, 0, -1, -1)) ++lim;  // IDA*
    cout << lim << endl;
    return 0;
}