python/TangDou/AcWing/AStar/179.md

## [$AcWing$ $179$ 八数码](https://www.acwing.com/problem/content/181/)

### 一、题目描述

在一个 $3×3$ 的网格中，$1$∼$8$ 这 $8$ 个数字和一个 $X$ 恰好不重不漏地分布在这 $3×3$ 的网格中。

例如：
```c++
1 2 3
X 4 6
7 5 8
```
在游戏过程中，可以把 $X$ 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

```c++
1 2 3
4 5 6
7 8 X
```
例如，示例中图形就可以通过让 $X$ 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

```c++
1 2 3   1 2 3   1 2 3   1 2 3
X 4 6   4 X 6   4 5 6   4 5 6
7 5 8   7 5 8   7 X 8   7 8 X
```

把 `X` 与上下左右方向数字交换的行动记录为 `u`、`d`、`l`、`r`。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。


**输入格式**
输入占一行，将 $3×3$ 的初始网格描绘出来。

例如，如果初始网格如下所示：

```c++
1 2 3 
x 4 6 
7 5 8 
```

则输入为：`1 2 3 x 4 6 7 5 8`


**输出格式**

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。

如果答案不唯一，输出任意一种合法方案即可。

如果不存在解决方案，则输出 `unsolvable`。

**输入样例**：
```cpp {.line-numbers}
2  3  4  1  5  x  7  6  8 
```

**输出样例**
```cpp {.line-numbers}
ullddrurdllurdruldr
```

### 二、八数码定理

对于给定八数码棋局的初始状态，我们的目标是通过交换空格与其相邻棋子使棋盘达到目标状态。
其中，游戏规则是只能交换空格与其上下左右四个方向的相邻棋子。

假设棋局目标状态为如下形式：（$A、B、C、D、E、F、G、H$表示棋子）
```cpp {.line-numbers}
A  B  C
D  E  F
G  H          
```
而初始状态就是$A、B、C、D、E、F、G、H$这八个棋子在这九个棋格上的任意分布。

并且我们对棋盘中每个棋格进行如下形式的编号：
```cpp {.line-numbers}
1  2  3
4  5  6
7  8  9
```

那么，对于一个任意的棋局状态，我们可以取得这八个棋子（$A、B、C、D、E、F、G、H$）的一个数列：棋子按照棋格的编号依次进行排列，记为
$p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8]$（即$A、B、C、D、E、F、G、H$的一个排列）。

在分析之前，先引进 **逆序** 和 **逆序数** 的概念：对于棋子数列中任何一个棋子$c[i]$$（1≤i≤8）$，如果有$j>i$且$c[j]<c[i]$，那么 $c[j]$是$c[i]$的一个逆序，或者$c[i]$和$c[j]$构成一个逆序对。定义棋子$c[i]$的逆序数为$c[i]$的逆序个数；棋子数列的逆序数为该数列所有棋子的逆序数总和。
> **注**：约定$A<B<C<D<E<F<G<H$。

现在，我们对一个任意的棋局状态$p=c[1]c[2]c[3]c[4]c[5]c[6]c[7]c[8]$进行分析：

#### 引理$1$：如果交换任何两个相邻的棋子，那么棋子数列的逆序数将发生奇偶性互变
>（奇偶性互变是指由奇数变为偶数，或由偶数变为奇数，下同）。

证明:假设交换的是$c[i]$和$c[i+1]$，那么对于$c[j]$（$1≤j≤i-1$或$i+2≤j≤8$）的逆序数并不改变。若交换之前 $c[i]<c[i+1]$，那么交换之后，$c[i]$的逆序数不变，而$c[i+1]$的逆序数加$1$（因为$c[i]$成了它的一个逆序）；同理，若交换之前 $c[i]>c[i+1]$，那么交换之后，$c[i]$的逆序数减$1$，而$c[i+1]$的逆序数不变。所以，引理$1$成立。

#### 引理$2$：如果棋子数列经过$n$次相邻棋子交换后，若$n$为偶数，则数列逆序数奇偶性不变；若$n$为奇数，则数列逆序数将发生奇偶性互变。
   其证明可以由引理$1$简单推出。

#### 引理$3$：在满足上述约定的八数码问题中，空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。
**证明**：显然空格与左右棋子交换不会改变棋子数列的逆序数（因为数列并没有改变）。现在考虑空格与上下棋子交换的情况：若空格与上方的棋子交换（假设交换是可行的），将得到一个新数列。若假设交换棋子为$c[i]=X$，那么原数列
$$p=c[1]...X c[i+1]c[i+2]...c[8]$$
将变为新数列$q=c[1]...c[i+1]c[i+2]X ...c[8]$
>**注意**：在棋盘中，上下相邻的两棋格之间隔有两个棋格

由原数列$p$到新数列$q$的转变可以通过如下方式加以解释：**用$X$与$c[i+1]、 c[i+2]$ 先后进行两次相邻交换而完成状态转变**。
所以根据引理$2$知，由$p$状态到$q$状态并不会改变改变棋子数列的逆序数的奇偶性。同理可证空格与下方棋子交换也不会改变棋子数列的逆序数的奇偶性。所以，空格与相邻棋子的交换不会改变棋局中棋子数列的逆序数的奇偶性。

#### 定理
- 当初始状态棋局的棋子数列的逆序数是奇数时，八数码问题无解；
- 当初始状态棋局的棋子数列的逆序数是偶数时，八数码问题有解。

证明：由引理$3$知，按照八数码问题的游戏规则，在游戏过程中，棋局的棋子数列的逆序数的奇偶性不会发生变化。而上面规定的目标状态没有逆序存在，所以目标状态下棋局的逆序数为偶数（实际为$0$）。

显然，可能的初始状态棋局的棋子数列的逆序数可能为奇数，也可能为偶数（因为把一个初始状态中任意相邻两个棋子交换，得到的新的状态作为初始状态，它们的奇偶性相反）。所以，对于任意一个初始状态，若其棋局的棋子数列的逆序数为奇数，则永远也不可能达到目标状态，即八数码问题无解；若其棋局的棋子数列的逆序数为偶数。

###　三、$bfs$
$2663 \ ms$
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
typedef unordered_map<string, int> MSI;
typedef unordered_map<string, pair<char, string>> MSP;
// 无脑BFS解法
//  2997 ms 可以AC掉本题
string st, ed = "12345678x";
// 上右下左 四个方向
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char op[] = {'u', 'r', 'd', 'l'};
MSP pre; // 字符串，前驱操作符，前驱字符串

void bfs() {
    queue<string> q;
    MSI dist; // 标识某个状态是否用过，如果用过，那么记录的最短距离是多少

    // 入队列
    q.push(st);
    dist[st] = 0; // 记录出发点最短距离

    // 开始bfs
    while (q.size()) {
        // 取出队头字符串
        string t = q.front();
        q.pop();

        // 如果到达最终状态，结束
        if (t == ed) {
            string res;
            while (ed != st) {
                res += pre[ed].first;
                ed = pre[ed].second;
            }
            for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
            break;
        }
        int d = dist[t]; // 现在记录的最短路径长度

        int k = t.find('x');                                  // 在字符串t中查找x的索引位置
        int tx = k / 3, ty = k % 3;                           // 映射的二维数组中的行与列
        for (int i = 0; i < 4; i++) {                         // 枚举四个方向
            int x = tx + dx[i], y = ty + dy[i];               // 目标位置
            if (x < 0 || x >= 3 || y < 0 || y >= 3) continue; // 出界

            string v = t;
            swap(v[x * 3 + y], v[k]); // x与目标位置交换一下
            if (!dist.count(v)) {     // 如果t字符串出现过，注意C++取unorderd_map是否存在元素时，需要用count
                dist[v] = d + 1;      // 记录是上一个距离+1得到的
                q.push(v);            // 新位置进入队列
                pre[v] = {op[i], t};  // 记录v这个字符串的前驱字符串是t，并且，是通过操作符op[i]转化而来
            }
        }
    }
}

int main() {
    // 原始输入是用的一个字符一个空格的形式，无法使用string进行读入
    char c;
    for (int i = 0; i < 9; i++) cin >> c, st += c;

    // 八数码定理:检查逆序对数量
    int nums = 0;
    for (int i = 0; i < 9; i++) {
        if (st[i] == 'x') continue; // 保证不是x
        for (int j = i + 1; j < 9; j++) {
            if (st[j] == 'x') continue; // 保证不是x
            if (st[j] < st[i]) nums++;  // 逆序数
        }
    }
    // 如果逆序对数量是奇数个，则输出-1
    if (nums & 1)
        puts("unsolvable");
    else // 否则通过bfs输出路径
        bfs();

    return 0;
}
```

###　四、$A*$寻路

$A*$ **最重要** 的是 **估值函数**，本题中使用的估值函数办法是 **曼哈顿距离**：

估计距离可以理解为理想距离，举个栗子：

<!-- 让表格居中显示的风格 -->
<style>
.center 
{
  width: auto;
  display: table;
  margin-left: auto;
  margin-right: auto;
}
</style>
<div class="center">

| 出发             | 目标           |
| ---------------- | -------------- |
| $\large 1~ 5 ~4$ | $\large 1~2~3$ |
| $\large 3~ 7 ~6$ | $\large 4~5~6$ |
| $\large 8~ x ~2$ | $\large 7~8~x$ |
</div>

> 现实中$4$要走到理想位置的话，先要向左走两步，再向下一步
> 现实中$8$要向右走一步到达
> 理想步数即为横纵坐标差距绝对值之和

现位置$(x_1,y_1)$到目标位置$(x_2,y_2)$:
 $$\large 曼哈顿距离 =  |x_1-x_2|+|y_1-y_2|$$

$74ms$
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

typedef unordered_map<string, int> MSI;
typedef unordered_map<string, pair<char, string>> MSP;

string st, ed = "12345678x";

// 上下左右
char op[] = {'u', 'd', 'l', 'r'};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
struct Node {
    int dist;
    string str;
    const bool operator<(const Node &b) const {
        return b.dist < dist;
    }
};
// 前驱
MSP pre;
MSI dist;
priority_queue<Node> q;

// 估值函数【每个位置的现实值与理想值的曼哈顿距离差值和】
int f(string str) {
    int res = 0;
    for (int i = 0; i < str.size(); i++)
        if (str[i] != 'x') {
            int t = str[i] - '1'; // str[i]对应的数字，应该在下标从0开始的字符串哪个位置
            // ① 利用除3模3大法，将下标从0开始的坐标转换为二维坐标,并计算理想值与目标值的曼哈顿距离
            // ② 曼哈顿距离的累加值才是当前状态与理想状态的整体差距
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    return res;
}

string astar() {
    // 将估价函数与字符串形成数对，放入到优先队列中
    q.push({f(st), st});
    dist[st] = 0; // 记录距离为0

    while (q.size()) {
        string t = q.top().str;
        q.pop();

        if (t == ed) break;

        int k = t.find('x');
        int tx = k / 3, ty = k % 3;
        for (int i = 0; i < 4; i++) { // 枚举udlr
            int x = tx + dx[i], y = ty + dy[i];
            if (x < 0 || x >= 3 || y < 0 || y >= 3) continue; // 出界
            string v = t;                                     // 将t字符串复制出来一个，生成 v字符串
            swap(v[k], v[x * 3 + y]);                         // 将原字符串中x与目标位置进行交换，生成新的目标状态字符串v

            if (dist[v]) continue;
            dist[v] = dist[t] + 1;       // 更新最小值
            q.push({dist[v] + f(v), v}); // 将新的估价函数计算更新，重新入队列
            pre[v] = {op[i], t};
        }
    }

    // 将路径倒转过来
    string res;
    while (ed != st) {
        res += pre[ed].first;
        ed = pre[ed].second;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    char c;
    for (int i = 0; i < 9; i++) cin >> c, st += c;

    // 八数码定理
    int nums = 0;
    for (int i = 0; i < 9; i++) {
        if (st[i] == 'x') continue;
        for (int j = i + 1; j < 9; j++) {
            if (st[j] == 'x') continue;
            if (st[j] < st[i]) nums++; // 逆序数
        }
    }
    // 奇数个逆序对，无解
    if (nums & 1)
        puts("unsolvable");
    else
        cout << astar() << endl; // 运行astar算法，返回最短距离

    return 0;
}

```


###　五、双向$bfs$
$102ms$
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;

// 　当前串，哪个操作，前序串
typedef unordered_map<string, pair<char, string>> MSP;
//  字符串，步数
typedef unordered_map<string, int> MSI;

// 操作符，上下左右
char op[] = {'u', 'd', 'l', 'r'};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 记录前驱路径
MSP aPre, bPre;
// 记录距离
MSI da, db;

string mid;           // 两个队列互相查看着搜索，当在对方HASH表中命中时，最终的那个两边都有的中间状态是什么样的字符串
queue<string> qa, qb; // 两个队列，分别用于存放从起点走出来的字符串和从终点走出来的字符串

int extend(queue<string> &q, MSI &da, MSI &db, MSP &aPre) {
    string u = q.front();
    q.pop();

    for (int i = 0; i < 4; i++) {
        int k = u.find('x');        // 在字符串t中查找x的索引位置
        int tx = k / 3, ty = k % 3; // 映射的二维数组中的行与列

        int x = tx + dx[i], y = ty + dy[i];               // 目标位置
        if (x < 0 || x >= 3 || y < 0 || y >= 3) continue; // 出界
        string v = u;
        swap(v[x * 3 + y], v[k]); // x与目标位置交换一下

        if (da[v]) continue;  // 如果搜索过
        aPre[v] = {op[i], u}; // 没有搜索过时，一定要马上记录它的前驱！！！不能因为它还没有进入队列就不先记录！！！
        // 原因：因为两段式搜索，最终要输出完整的路径，否则就会出现中间缺一条线的情况，比如　○→○→○ ←(这是这个箭头) ○←○←○，

        if (db[v]) {                  // 如果对方已经搜到了
            mid = v;                  // 将中间态保存到全局变量中，方便以后的操作
            return da[v] + db[v] - 1; // 返回中间点距离起点、终点距离和-1
        }

        da[v] = da[u] + 1; // 距离增加1
        q.push(v);
    }
    return -1; // 如果本次扩展没有找到连接前后的字符串，那就返回-1表示还需要继续找
}

// 出发状态，目标状态
string st, ed = "12345678x";

void bfs() {
    qa.push(st);
    da[st] = 0;

    qb.push(ed);
    db[ed] = 0;

    while (qa.size() && qb.size()) { // 双端宽搜套路
        int t;
        if (qa.size() <= qb.size())       // 这里面是一个双向bfs的优化策略，两个队列谁小就谁使劲跑
            t = extend(qa, da, db, aPre); // 从a中取状态进行扩展
        else
            t = extend(qb, db, da, bPre);
        if (t > 0) break;
    }
}

int main() {
    char c;
    for (int i = 1; i <= 9; i++) cin >> c, st += c;

    // 八数码定理:检查逆序对数量
    int nums = 0;
    for (int i = 0; i < 9; i++) {
        if (st[i] == 'x') continue; // 保证不是x
        for (int j = i + 1; j < 9; j++) {
            if (st[j] == 'x') continue; // 保证不是x
            if (st[j] < st[i]) nums++;  // 逆序数
        }
    }
    // 如果逆序对数量是奇数个，则输出-1
    if (nums & 1)
        puts("unsolvable");
    else {
        // 双向宽搜
        bfs();

        // 两段式输出
        //  ① 输出前半段，与传统BFS输出路径无异
        string res;
        string t = mid;
        while (t != st) {
            res += aPre[t].first;
            t = aPre[t].second;
        }
        reverse(res.begin(), res.end());

        // ② 输出后半段，因宽搜的方向问题，需要逆着来
        t = mid;
        while (t != ed) {
            char cmd = bPre[t].first;
            if (cmd == 'u' || cmd == 'd') cmd = 'u' + 'd' - cmd;
            if (cmd == 'l' || cmd == 'r') cmd = 'l' + 'r' - cmd;
            res += cmd;
            t = bPre[t].second;
        }
        // 输出
        cout << res << endl;
    }
    return 0;
}
```