本题知识点和基本代码来自《算法竞赛 入门到进阶》（作者：罗勇军 郭卫斌）
如有问题欢迎巨巨们提出
题意：八数码问题是在一个3*3的棋盘上放置编号为1~8的方块，其中有一块为控制，与空格相邻的数字方块可以移动到空格里。我们要求指定初始棋盘和目标棋盘，计算出最少移动次数，同时要输出数码的移动数列。初始棋盘样例已给出，目标棋盘为“1 2 3 4 5 6 7 8 x”
输入：
2 3 4 1 5 x 7 6 8
输出：
ullddrurdllurdruldr 详解：
八数码是经典的BFS问题，可以用“康托展开”判重。那什么事康托展开呢？
康托展开是一种特殊的哈希函数，针对八数码问题，康托展开完成了如表所示的工作。
| 状态 | 012345678 | 012345687 | 0123456768 | ...... | 876543210 |
| Cantor | 0 | 1 | 2 | ...... | 362880-1 |
函数Cantor（）实现的功能是：输入一个排序，即第一行的某个排序，计算它的Cantor值，即第二行的数。Cantor的时间复杂度为O(n*n)，n是集合中元素的个数，利用CANTOR展开可以实现八数码的快速判重。
距离康托展开的实现原理：
例：判断2143是{1,2,3,4}的全排列中第几大的数。
计算排在2143前面的排列数目，可以转换成以下排列的和：
（1）首位小于2的所有排序，比2小的只有一个数，后面三个数的排序有3!个。
（2）首位为2，第2位小于1的所有排序，无，写成0*2!=0.
（3）前两位为21，第三位小于4的数，即2134，写成1*1！=1.
(4)前三位为214，第四位小于3的数，无，即0*0！=1.
sum=8.即2143是第八大的数。 把一个集合产生的全排列按字典序排序，第X个排序的计算公式如下：
X=a[n]*(n-1)!+a[n-1]*(n-2)!+....+a[i]*(i-1)!+...+a[2]*1!+a[1]*0![1].其中，a[i]为当前未出现的元素排在第几个。（从0开始）0<=a[i]<i. 康托展开的基础代码：
int visited[maxn] = { }; //判断改装备是否被访问过
long int factory[] = { ,,,,,,,,, };//阶乘数
bool Cantor(int str[], int n)
{
long result = ;
for (int i = ; i < n; i++)
{
int counted = ;
for (int j = i + ; j < n; j++)
{
if (str[i] > str[j])
++counted;
}
result += counted * factory[n - i - ];
}
if (!visited[result])
{
visited[result] = ;
return ;
}
else return ;
}
这道题看了很多博客，存步骤的答案方式很多，我是在结构体里设置string，然后在bfs过程中逐步保存步骤，最后输出达到最终状态的答案。看代码应该能理解。还有保存图的时候要注意，样例里空格不止一个，所以灵活点保存。我最后时间跑出来是750ms，比较慢，可用其他搜索方法优化。
AC代码：
#pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<string>
#include<map>
#include<vector>
#include<ctime>
#include<stack>
using namespace std;
#define mm(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int maxn = ;
const int inf = 0x3f3f3f3f; struct node
{
int state[];
int dis;
string ans;
}; int dir[][] = { {-,},{,-},{,},{,} };
char turn[] = { 'l','u','r','d' };
int visited[maxn] = { };
int start[];
int goal[] = {,,,,,,,,}; long int factory[] = { ,,,,,,,,, }; bool Cantor(int str[], int n)
{
long result = ;
for (int i = ; i < n; i++)
{
int counted = ;
for (int j = i + ; j < n; j++)
{
if (str[i] > str[j])
++counted;
}
result += counted * factory[n - i - ];
}
if (!visited[result])
{
visited[result] = ;
return ;
}
else return ;
} bool check(int x, int y)
{
if (x >= && x < && y >= && y < )
return true;
else return false;
} queue<char>ans; int bfs()
{
node head;
memcpy(head.state, start, sizeof(head.state));
head.dis = ;
queue<node>q;
Cantor(head.state, );
q.push(head);
while (!q.empty())
{
head = q.front();
q.pop();
int z;
for (z = ; z < ; z++)
{
if (head.state[z] == )
break;
}
int x = z % ;
int y = z / ;
for (int i = ; i < ; i++)
{
int newx = x + dir[i][];
int newy = y + dir[i][];
int nz = newx + * newy;
if (check(newx, newy))
{
node newnode = head;
swap(newnode.state[z], newnode.state[nz]); //0的交换
newnode.dis++;
if (memcmp(newnode.state, goal, sizeof(goal)) == )
{
newnode.ans = newnode.ans + turn[i];
cout << newnode.ans << endl;
return newnode.dis;
}
if (Cantor(newnode.state, ))
{
newnode.ans = head.ans + turn[i];
q.push(newnode);
}
}
}
}
return -;
} int main()
{
char s[];
cin.getline(s, );
int pos = ;
for (int i = ; s[i] != '\0'; i++)
{
if (s[i] == ' ') continue;
else if (s[i] == 'x') start[pos++] = ;
else start[pos++] = s[i] - '';
}
int num = bfs();
//printf("%d\n", num);
if (num == -) printf("unsolvable\n");
return ;
}