洛谷刷题记——P1379 八数码难题（朴素广搜实现）

八数码问题是所有BFS问题中最经典的问题之一，而且非常考验做题人对广搜的综合理解，建议先去查阅学习广搜相关资料，再看看《洛谷刷题记——P1443 马的遍历》这篇文章，最后再来挑战这道难题。

题目描述

见“P1379 八数码难题”。

知识链接

康托展开

定义：康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

看到这段话，你肯定一脸雾水（因为这段话直接引自百科，而众所周知写百科的人都不喜欢说人话），所以我们用人话来描述一下康托展开。

观察以下数对：(0, 012345678), (1, 012345687), (2, 012345768),······,(362879, 876543210)，通过找规律我们可以看出这些数对中前一个数，是后一个数在{0, 1, 2, 3, 4, 5, 6, 7, 8}的全排列中的序数（不知道全排列的可以自行Google）。什么意思呢？我们将这九个数做全排列，可以看到012345678是第一个全排列，所以它对应的数就是0；而012345687是第二个全排列，所以它对应的数就是1······一直到876543210，可以看出它是所有全排列中最后一个，所以对应的编号为362879（共有362880个排列）。而这个“编号”，就是这个数的康托展开。

一句话：一个数的康托展开就是这个数在全排列中的排行。

至于全排列如何去算呢？我们有如下公式：

$$ X = \alpha_{n}(n – 1)! + \alpha_{n – 1}(n – 2)! + \cdots + \alpha_{1} \cdot 0! $$

其中，\( \alpha_{i} \) 为整数，并且 \( 0 \leq \alpha_{i} < i, 1 \leq i \leq n \)。

至于实现方面，就按照上面的公式来即可。只不过注意一点：在程序中动态算阶乘时间损耗过高，可以提前算好，然后保存进数组。下面以之前的9位数来做康拓展开的例子：

// 以9位数为例的康托展开

array<int, 10> kFactories = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 这个数组存的是公式里的那些阶乘结果

int Cantor(const array<int, 10>& str) { // str是传进去的数，输出这个数的康托展开
  int res(0); // 康托展开结果

  for (int i = 0; i < 9; ++i) {
    int cnt(0);

    for (int j = i + 1; j < 9; ++j) // 这层循环可以用线段树优化，但本题中n最大只有9，所以没有必要
      if (str[i] > str[j])
        ++cnt;

    res += cnt * kFactories[8 - i];
  }

  return res;
}

这样一算，发现是 \( O(n^2) \) 的复杂度，在这里大约只要循环81次左右，是很不错的方法。当然，第二层循环用线段树优化后能达到 \( O(n\log n) \) 的复杂度。不过，正如代码中所说的，在这个例子中没有必要。如果读者对此有兴趣的话，可以参见《排列数，康托展开及其线段树优化》这篇文章。

另：康拓展开有一个非常重要的特性，就是每一个展开只对应一个全排列，由此可以看出康托展开其实就是一种哈希函数。这是一个非常重要的特性，这也是我们为什么能用康托展开判重的原因。“康托逆展开”也是基于这样一个原理，有兴趣的读者可以自己查阅资料了解一下。

解题思路

本题是一个考察综合BFS能力的题，与其他题类似，这道题只需要分别将空位四个方向的数码拖拽到空位上来，再分别将这四种情况入队即可。注意：一定要判断四个方向的位置是否合法。

当然，如果你这么做了的话，是 \( O(n!n!) \) 的复杂度，显然会是超时的。怎么办呢？记忆化搜索！至于如果想要直接判重的话，最大的情况转化为一维数就是876543210，直接开一个876543210的数组肯定是会MLE的······等等，这个数怎么这么熟悉？对的，就是我们刚才的康托展开！刚才我们算过，九位数的康托展开最大只到362880，而这样一个数组显然是不会越界的。搜索的 \( O(n!) \) 的复杂度，加上康托展开 \( O(n^2) \) 的复杂度，总共加起来是 \( O(n!n^2) \)，对付本题绰绰有余了。

于是总体思路就定了：首先将当前状态用康托展开设为已访问过，然后将可能的四种状态加入队列继续搜索，直到找到目标。

我的实现是用的数组来存的八数码状态，当然用字符串也可以存。还有，如果想要更好的复杂度可以使用STL的map判重，或使用上面所说的线段树实现康托展开判重。

代码展示

拒绝抄袭，共创和谐社会[机智]

#include <cstdio> // std::getchar, std::puts, std::printf

#include <array> // std::array
#include <queue> // std::queue
#include <utility> // std::pair
#include <algorithm> // std::swap

using namespace std;

array<int, 10> kStart = {1, 2, 3, 8, 0, 4, 7, 6, 5, -1}; // 初始状态，由题目给出
array<int, 10> kGoal; // 目标状态，由输入确定
array<array<int, 2>, 4> kPosMove = {0, 1, -1, 0, 0, -1, 1, 0}; // 上下左右四个方向的数码移动
array<int, 10> kFactories = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 康托展开用到的常数
array<bool, 362885> kIsVisited; // 判重
queue<pair<array<int, 10>, int> > kBfsQueue; // 队列

int Bfs(void); // 广搜
bool Cantor(const array<int, 10>& /* str */); // 康托展开，直接返回是否重复
inline bool IsValid(int /* dx */, int /* dy */); // 判断坐标是否越界

int main(void) {
  // 初始化
  kGoal.fill(-1);
  kIsVisited.fill(false);

  for (int i = 0; i < 9; ++i)
    kGoal[i] = getchar() - '0';

  if (kGoal == kStart) // 如果两种情况相等
    puts("0"); // 可以直接输出
  else
    printf("%d\n", Bfs()); // 输出广搜结果

  return 0;
}

int Bfs(void) {
  pair<array<int, 10>, int> head(make_pair(kStart, 0)), new_node; // 当前状态和新状态
  Cantor(head.first); // 将起始状态设为当前状态，用康托展开设为已访问
  kBfsQueue.push(head); // 起点入队

  while (!kBfsQueue.empty()) {
    bool is_find_zero(false); // 是否找到当前状态中的空位
    int zero_pos(-1); // 空位的位置

    head = kBfsQueue.front(); // 将队首取出，设为当前状态
    kBfsQueue.pop();

    for (int i = 0; i < 9 && !is_find_zero; ++i) { // 寻找当前状态的空位
      if (0 == head.first[i]) { // 找到了
        zero_pos = i;
        is_find_zero = true;
      }
    }

    int zero_x(zero_pos % 3), zero_y(zero_pos / 3); // 将一维位置化为二维

    for (int i = 0; i < 4; ++i) { // 列举上面的往下、左边的往右、下边的网上、右边的往左四种情况
      int new_zero_x(zero_x + kPosMove[i][0]), // 新空位的x值
          new_zero_y(zero_y + kPosMove[i][1]); // 新空位的y值
      int new_zero_pos(new_zero_x + new_zero_y * 3); // 将二维位置化为一维

      if (IsValid(new_zero_x, new_zero_y)) { // 坐标没有越界
        new_node = head;
        swap(new_node.first[zero_pos], new_node.first[new_zero_pos]); // 移动数码
        ++(new_node.second); // 步数加一

        if (new_node.first == kGoal) // 如果该状态等于目标状态
          return new_node.second; // 直接返回即可

        if (Cantor(new_node.first)) // 如果该状态没有搜索过
          kBfsQueue.push(new_node); // 加入队列
      }
    }
  }

  return -1;
}

// 康托展开，在“知识链接”中有讲解
bool Cantor(const array<int, 10>& str) {
  int res(0);

  for (int i = 0; i < 9; ++i) {
    int cnt(0);

    for (int j = i + 1; j < 9; ++j)
      if (str[i] > str[j])
        ++cnt;

    res += cnt * kFactories[8 - i];
  }

  if (!kIsVisited[res]) { // 这部分，直接判重返回
    kIsVisited[res] = true;
    return true;
  } else {
    return false;
  }
}

inline bool IsValid(int dx, int dy) {
  if (-1 < dx && dx < 3 && -1 < dy && dy < 3)
    return true;
  else
    return false;
}

写在最后

这道八数码问题是一道非常综合的广搜题目，做出了这道题后可以说是登堂入室了。但是这里只写出了朴素的BFS写法，还有很多的优化空间，如双向广搜、BFS A*、IDDFS和IDA*等，后面会一一讲解。