8-Puzzle Problem
P1379 eight digital puzzles - Luogu
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.
Simple BFS
Through the simple analysis of the topic, it is easy to write simple BFS code. When making access marks, you can use the idea of hash to convert the matrix into an integer, and then std::unordered_set storage. 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:
#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;
}
Bidirectional 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;
}