八数码

题目地址:

Acwing

HDU

在一个 3×3 的网格中，1∼8 这 8 个数字和一个 X 恰好不重不漏地分布在这 3×3 的网格中
在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为正确排列

把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。
现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列

我花了好几个晚上才完整的写了出来，毕竟还是新手，但独立写出来之后还有一点成就感(当然有参考)。下面就来小小提提我的思路吧。

bfs不仅可以搜索路径，还可以搜索状态。

这是我从黑书上看到的一句话，从后几个晚上便开始了我的不归路。

所以我也用黑书上的思路，bfs+cantor解决这道题

这题要寻找最短路径，所以bfs更适合

1. 广度优先搜索 (BFS)

这个思路很好理解

1
2
3
4
5
6
7
初始状态入队
	while(队列不为空)
		取出队首
		if(找到目标)
			返回答案
		else
			相邻状态入队

伪代码非常清晰，现在我们把文字展开成代码实现得到。

首先我们联系一下问题

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

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

1
2
3
1 2 3 
x 4 6 
7 5 8

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

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。
如果答案不唯一，输出任意一种合法方案即可。
如果不存在解决方案，则输出 unsolvable。

我们可以用多种方式存储状态，我这里选择的一维数组。
因为输出行动记录，我的思路就是用一个结构体存储数组和上次到这次的行动，还有上次状态的地址。

语言描述有点难懂，现在来看看代码实现。

1
2
3
4
5
struct state{
	int num[9];	//数组
	char ch;	//上次到这次的行动
	int re;		//上次状态的地址
};

在这里说到说到上次状态的地址，这是一个整数而不是一个指针。
这是因为我们使用数组模拟bfs中的队列，这个整数是数组下标,
搜索的元素出队后，不会删除，而是数组头指针和尾指针的移动。所以我们可以这样记录地址

更详细的可以学习下队列相关知识。

实现一下，看不懂没关系，稍后会解释(看起来代码很长，其实很多重复的地方，读者可以试着优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
state bfs()
    //初始状态入队，把初始状态的上状态地址设为-1，以便区别与普通状态
	begin.re = -1;
	q[++tt] = begin;
	while(tt >= hh){
		//是否找到，如果队首的九个数都和目标相同，则为找到。也可用memcmp等函数
		int cnt = 0;
		for(int i = 0;i < 9;++i)
			if(q[hh].num[i] == aim[i])
				cnt++;
		if(cnt == 9) return q[hh];
        //寻找0的位置，我们在输入的时候把x换成0，这样子,方便数组存储
		int z;
		for(z = 0;z < 9;++z)
			if(q[hh].num[z] == 0)
				break;
        //判断相邻状态
		if((z+1)%3){//是否能向左，依题意得2 5 8这三个位置不能向左 
			state tmp;
			tmp.ch = 'r';
			tmp.re = hh;
			memcpy(tmp.num,q[hh].num,sizeof (q[hh].num));
			swap(tmp.num[z],tmp.num[z+1]);
			//是否查找过状态，vis定义为  如果找过则返回false，反则true
            //具体代码实现就不给了，因为后面后用一个更nb的函数代替
            if(vis(tmp.num))
                q[++tt] = tmp;
		}
		if(z % 3){//同上
			state tmp;
			tmp.ch = 'l';
			tmp.re = hh;
			memcpy(tmp.num,q[hh].num,sizeof (q[hh].num));
			swap(tmp.num[z],tmp.num[z-1]);
			if(vis(tmp.num)) q[++tt] = tmp;;
		}
		if(z > 2){//ts
			state tmp;
			tmp.ch = 'u';
			tmp.re = hh;
			memcpy(tmp.num,q[hh].num,sizeof (q[hh].num));
			swap(tmp.num[z],tmp.num[z-3]);
			if(vis(tmp.num)) q[++tt] = tmp;
		}
		if(z < 6){//t
			state tmp;
			tmp.ch = 'd';
			tmp.re = hh;
			memcpy(tmp.num,q[hh].num,sizeof (q[hh].num));
			swap(tmp.num[z],tmp.num[z+3]);
			if(vis(tmp.num)) q[++tt] = tmp;
		}
		++hh;//弹出队首，因为我们前面不是取出队首，而是直接用队首，所以在此弹出队首
	}
	return begin;//如果没有找到，返回begin
}

解释: 因为我们用一维数组存储当前格子的状态，也就是（已经把x换成0）

1
2
3
1 2 3
4 5 6
7 8 0

存为 1 2 3 4 5 6 7 8 0 对应的a[0] = 1,a[1] = 2,a[3] = 2 也就是3对应的位置数组下标为2

由此可知，当0的位置数组下标为2，5，8是，不能往左走
同理 0，1，2时,不能往上 0，3，6不右 6，7，8不下
随后用if条件判断即可。

而行走我们用了swap函数，交换0(即x)的位置数组下标和目标位置的下标，完成一次行走

最后把上次到这次的行动和上次位置地址存储到tmp上，如果符合条件就入队。

康托展开 (Cantor Expansion)

代码主体部分已经基本完成，但还有很多问题，比如判重函数 _vis()_ 还没有实现，如果没有判重，程序会产生很多无效操作，复杂度大大增加，但如果使用暴力的方法判重，每次把新状态和9! = 362880 个状态对比，可能有9!*9!次检查，必TLE

所以我们用到了这种数学方法“康托展开”判重

康托展开是一种特殊的哈希函数

实际上，康托展开听起来很高大上，其实就是把几个数的排列映射到值上，每个值对应一种排列，如4个数的全排列可以用4! = 24个值表示，见下表

状态 Cantor
0123 0
0132 1
0213 2
0231 3
…… ……
3210 23

那如何完成从状态到值的转换呢，当然是有公式滴

其中， $a_i$ 表示原数的第i位在当前为出现的原数中排第几个(从0开始数的)
乱七八糟，对吧

其实这东西真不难，看着唬人而已，我们来展开几个数试试。

0 2 3 1
第4位为0，0排第0个，0个数中没有数出现过，$a_4$ = 0 - 0 = 0;
第3位为2，2排第2个，2个数中1个0出现过，$a_3$ = 2 - 1 = 2
第2位为3，3排第3个，3个数中2个数(0,2)出现过，$a_2$ = 3 - 2 = 1
第1位为1，1排第1个，1个数中1个0出现过，$a_1$ = 1 - 1 = 0
所以
$X = 0\times3! + 1\times2! + 1\times1! + 0\times0! = 3$

1 0 3 2
第4位为1，1排第1个，1个数中没有数出现过，$a_4$ = 1 - 0 = 1;
第3位为0，0排第0个，0个数中没有数出现过，$a_3$ = 0 - 0 = 0
第2位为3，3排第3个，3个数中2个数(0,1)出现过，$a_2$ = 3 - 2 = 1
第3位为2，2排第2个，2个数中2个数(0,1)出现过，$a_1$ = 2 - 2 = 0
所以
$X = 1\times3! + 0\times2! + 1\times1! + 0\times0! = 7$

作了这些练习，有没有一种编程的欲望？下面给出代码实现(我自己写的，当然还有优化空间)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int org[10] = {0,1,2,3,4,5,6,7,8};//原数
int factory[11] = {1,1,2,6,24,120,720,5040,40320,362880};//阶乘打表
//bool basket[10]之前定义在外面,debug找了好久才出错,数组很容易犯这种错

//查看有几个数出现过
inline int g(int x,int * basket){//因为basket为cantor()的成员变量,所以传进来
	int cnt = 0;		
	for(int i = 0;i < x;++i)
		if(basket[i])
			++cnt;
	return cnt;
}
inline int cantor(int * a){
	int x = 0;
    bool basket[10] = {0};//查看有什么数出现过,记得定义为成员变量,并初始化
	for(int i = 0;i < 9;++i){
		x += (a[i] - g(a[i],basket)) * factory[8-i];
		basket[a[i]] = true;//找过的置1
	}
	return x;
}

这就是康托展开，我上面的解释是以编程，即应用的角度出发去理解的。读者也可以思考一下他的数学内涵(可从排列的角度出发)

AC代码

我们的基本思路就是BFS+Cantor解决这玩意，当然还有双向bfs和A*等算法，读者可以尝试，下面给出我的AC代码(优化的可以)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <iostream>
using namespace std;

struct state{
	int num[9];
	char ch;
	int re;
};//定义状态结构体

vector<char> ans;//用vector存答案
state q[666666];//模拟队列
int hh,tt = -1;//头,尾指针
int beg[9];//开始数组
int aim[9] = {1,2,3,4,5,6,7,8,0};//目标数组
int org[9] = {0,1,2,3,4,5,6,7,8};//原数组，Cantor展开用
int factory[11] = {1,1,2,6,24,120,720,5040,40320,362880};//阶乘打表
bool vis[362881];//找过的数放进来

inline int g(int x,int * basket){
	int cnt = 0;
	for(int i = 0;i < x;++i)
		if(basket[i])
			++cnt;
	return cnt;
}
inline bool cantor(int * a){
	int x = 0;
	int basket[9] = {0};
	for(int i = 0;i < 9;++i){
		x += (a[i] - g(a[i],basket)) * factory[8-i];
		basket[a[i]] = true;
	}
	if(vis[x])//判断是否找过
		return false;//找过就false
	vis[x] = true;//没找过就放进来
	return true;//没找过就true
}

state bfs(){
	state begin;
	memcpy(begin.num,beg,sizeof beg);//把begin数组给初始状态
	begin.re = -1;
	q[++tt] = begin;
	while(tt >= hh){
		int cnt = 0;
		for(int i = 0;i < 9;++i)
			if(q[hh].num[i] == aim[i])
				cnt++;
		if(cnt == 9) return q[hh];
		int z;
		for(z = 0;z < 9;++z)
			if(q[hh].num[z] == 0)
				break;
		if((z+1)%3){
			state tmp;
			tmp.ch = 'r';
			tmp.re = hh;
			memcpy(tmp.num,q[hh].num,sizeof (q[hh].num));
			swap(tmp.num[z],tmp.num[z+1]);
			if(cantor(tmp.num)) q[++tt] = tmp;
		}
		if(z % 3){
			state tmp;
			tmp.ch = 'l';
			tmp.re = hh;
			memcpy(tmp.num,q[hh].num,sizeof (q[hh].num));
			swap(tmp.num[z],tmp.num[z-1]);
			if(cantor(tmp.num)) q[++tt] = tmp;;
		}
		if(z > 2){
			state tmp;
			tmp.ch = 'u';
			tmp.re = hh;
			memcpy(tmp.num,q[hh].num,sizeof (q[hh].num));
			swap(tmp.num[z],tmp.num[z-3]);
			if(cantor(tmp.num)) q[++tt] = tmp;
		}
		if(z < 6){
			state tmp;
			tmp.ch = 'd';
			tmp.re = hh;
			memcpy(tmp.num,q[hh].num,sizeof (q[hh].num));
			swap(tmp.num[z],tmp.num[z+3]);
			if(cantor(tmp.num)) q[++tt] = tmp;
		}
		++hh;
	}
	return begin;
}

int main(){
	char chtmp;
	for(int i = 0;i < 9;++i){
		cin >> chtmp;
		if(chtmp == 'x')
			beg[i] = 0;
		else 
			beg[i] = chtmp - '0';
	}//读入begin数组

	cantor(beg);//初始状态放进vis
	state answer = bfs();
	if(answer.re == -1){//如果没找到目标，输出unsolvable
		printf("unsolvable\n");
		return 0;
	}
	while(answer.re != -1){
		ans.push_back(answer.ch);
		answer = q[answer.re];//一层一层向上找，把ch存入答案
	}

	for(auto i = ans.end()-1;i >= ans.begin();--i)
		printf("%c",*i);//逆序输出答案
	puts("");
	return 0;
}

Thats all