# 八数码问题（8-Puzzle Problem）(8-puzzle problem)-其他

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

### 八数码问题（8-Puzzle Problem）

P1379 八数码难题 – 洛谷

123
804
765

P1379 八数码难题 – 洛谷

123
804
765


### 朴素 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

#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* 算法以 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;
}