uva 10181 15-Puzzle Problem IDA*

缘起

【1】中处理了八数码问题。用的是宽度类型的搜索（单向bfs、双向bfs、A*）. 现在来处理15数码问题. uva 10181 15-Puzzle Problem

分析

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
就是给你一个4*4的数字矩阵, 0表示空白. 要你在50步之内给出答案. 如果50步给不出来, 就打印
"This puzzle is not solvable."

【输入】
多样例. 第一行给出样例数. 然后就是各个样例. 每个样例就是一个4*4的数字矩阵(1~15的数字)。

【输出】
给出解或者打印"This puzzle is not solvable."

【样例输入】
2
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11 15
13 1 2 4
5 0 3 7
9 6 10 12
15 8 11 14

【样例输出】
LLLDRDRDR
This puzzle is not solvable.

【限制】
15s

注意，本题有50步的限制. 所以考虑使用IDA* 而不是A*. 因为A* 对于内存的需求太大了. 而IDA* 不怎么消耗内存. 如果使用 A*的话, 可能会MLE. 而使用的启发式函数和A*算法是一样的.

本题和【2】极为相似. 代码结构基本一致.

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL
#include <algorithm>
using namespace std;
#define ABS(a,b) ((a)>(b)?((a)-(b)):((b)-(a)))

int a[4][4],depth, dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}},x,y; // x和y是0的位置
char ans[55], op[4]={'U','D','L','R'};

bool success()
{
	if (x!=3||y!=3) // 空白必须要放在最右下角
	{
		return false;
	}
	for (int i = 0; i<4; i++)
	{
		for (int j = 0; j<4; j++)
		{
			if (i==3&&j==3)
			{
				continue;
			}
			if (a[i][j]!=4*i+j+1)
			{
				return false;
			}
		}
	}
	return true;
}

int h() //计算启发式函数
{
	int ans = 0;
	for (int i =0; i<4; i++)
	{
		for (int j = 0; j<4;j++)
		{
			if (!a[i][j]) // 和八数码一样, 不考虑空白位置
			{
				continue;
			}
			ans+=ABS(i, (a[i][j]-1)/4)+ ABS(j, (a[i][j]-1)%4);
		}
	}
	return ans;
}

bool ok(char prev, char cur) // prev是上一步的移动指令, cur是此次的移动指令
{
	if (prev=='U')
	{
		return cur!='D';
	}
	if (prev == 'L')
	{
		return cur!='R';
	}
	if (prev=='D')
	{
		return cur!='U';
	}
	if (prev == 'R')
	{
		return cur!='L';
	}
}

bool ida(int step) // 决定 ans[step]的移动
{
	if (success())
	{
		for (int i = 0; i< step; i++)
		{
			putchar(ans[i]);
		}
		puts("");
		return true;
	}
	if (step+h()>depth) // IDA*剪枝
	{
		return false;
	}
	int b[4][4],xx,yy;
	memcpy(b,a, sizeof(a));
	xx = x, yy=y; // 保存现场
	for (int i = 0,nx,ny; i<4; i++)
	{
		if (step && !ok(ans[step-1],op[i])) // 这里是针对本题的一个小优化（而不是IDA*的优化）——如果上一次来的是U,那么此次'D'就是显然不必要的, 这可以节省不少无效状态的搜索,如果没有这个剪枝, 则被T掉
		{
			continue;
		}
		nx = x+dir[i][0];
		ny = y+dir[i][1];
		if (nx<0||nx>3||ny<0||ny>3)
		{
			continue;
		}
		swap(a[x][y], a[nx][ny]);
		x = nx,y=ny;
		ans[step] = op[i];
		if (ida(step+1))
		{
			return true;
		}
		memcpy(a,b,sizeof(a)); // 恢复现场
		x = xx, y=yy;
	}
	return false; // 四个方向拓展都是不行的,则此路不通
}

bool failed() // 15数码的判定存在解的条件是不包括空白的序列的逆序数+空白所在的行数（从1开始）必须要是偶数, 如果是奇数的话, 无解
{
	int c[20];
	for (int i = 0;i<4; i++)
	{
		for (int j = 0; j<4; j++)
		{
			c[4*i+j] = a[i][j];
		}
	}
	int ans = x+1;
	for (int i = 0;i<15; i++)
	{
		for (int j = i+1; j<16; j++)
		{
			if (c[j] && c[i]>c[j])
			{
				ans++;
			}
		}
	}
	return ans&1; // 奇数, 返回true, 表示此15 Puzzle问题无解
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		for (int i = 0; i<4; i++)
		{
			for (int j = 0; j<4; j++)
			{
				scanf("%d", a[i]+j);
				if (!a[i][j])
				{
					x = i;
					y = j;
				}
			}
		}
		if (failed())
		{
			puts("This puzzle is not solvable.");
			continue;
		}
		depth = h(); // 这个屌~ 即初始步骤用启发函数的值来做. 而不是从1开始
		while(depth<=50)
		{
			if (ida(0))
			{
				break;
			}
			depth++; // 加深迭代搜索
		}
		if (depth>50)
		{
			puts("This puzzle is not solvable.");
		}
	}
	return 0;
}

ac情况.

Status Accepted
Time 570ms
Length 2657
Lang C++11 5.3.0
Submitted 2019-09-18 16:12:35
Shared
RemoteRunId 23925445

顺便提一下~ 【1】中我写的三份宽度类型的搜索代码在hdu都没过（全部在poj ac掉），尤其是A*的那份是被内存卡掉的. 所以估计hdu 1043 只能用IDA*的姿势来过了.

而且IDA* 的代价在【2】中也说了——可能搜索重复的状态. 而且无法使用【2】中说的那样——开一个book数组来防止一次IDA* 搜索中搜索重复状态. 因为这里如果要哈希状态的话，将是16! 的空间, 一定被MLE掉的.

参考

【1】https://yfsyfs.github.io/2019/09/13/hdu-1043-Eight-%E5%85%AB%E6%95%B0%E7%A0%81-%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80-%E6%90%9C%E7%B4%A2/

【2】https://yfsyfs.github.io/2019/09/14/ZOJ-2477-Magic-Cube-IDA/