# 搜索专题3 | 八数码 HDU - 1043

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:

15谜题已经有100多年历史了。即使不知其名，肯定也见过。它由15个滑动块组成，每个滑动块由数字1到15标记，并且被放在4x4大小的框框里面，缺失一个块。缺失的称之为x。谜题的目标就是将这些块有序的整理起来。如下图：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 x

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8

9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12

13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x

r-> d-> r->

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.

Input

You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle

1 2 3

x 4 6

7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.

Sample Input

2 3 4 1 5 x 7 6 8

Sample Output

ullddrurdllurdruldr

1：初始化，将起始位置放入队列

priority_queue<state_t> q; q.push(a);

2：4个方向前进，计算每个方向的估值，这里的估值是计算曼哈顿距离，也就是x/y轴的差值绝对值之和。当前步数作为当前消耗的代价G。放入队列。

3：取队列元素，重复2过程。

```#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 4e5 + 10;

int ha[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
/*这个ha[9]数组是用来计算hash值的，这个数组中的值分别是0!,1!,2!,3!,4!,5!,6!,7!,8!*/
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char d[10] = "udlr";
int vis[maxn];  //判重

struct state_t {
int f[3][3];  //当前这个转态每个位置上的值
int x, y;
int g, h;
int hash_num;

// 估值为h+g
bool operator<(const state_t a) const {
return h + g > a.h + a.g;  //优先队列保证出队的是估值函数值较小的。
}
};

struct path {
int pre;
char ch;
} p[maxn];  //用于记录路径

// 评估函数，获得评估值
// 计算1~8的数字回到原点需要的步数作为评估值，必定小于实际操作数
int get_h(state_t a) {
int i, j, ans = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (a.f[i][j]) {
// 曼哈顿距离
ans += abs(i - (a.f[i][j] - 1) / 3) + abs(j - (a.f[i][j] - 1) % 3);
}
}
}
return ans;
}

//康托展开
int get_hash(state_t e) {
int a[9], i, j, k = 0, ans = 0;
for (i = 0; i < 3; i++)  //将数据排成一排，便于计算
{
for (j = 0; j < 3; j++)
a[k++] = e.f[i][j];
}
for (i = 0; i < 9; i++)  //计算hash值
{
k = 0;
for (j = 0; j < i; j++)
if (a[j] > a[i])
k++;
ans += ha[i] * k;
}
return ans;
}

void print(int x) {
if (p[x].pre == -1)
return;
print(p[x].pre);
printf("%c", p[x].ch);
}

void AStar(state_t a) {
memset(vis, 0, sizeof(vis));
int end_ans, xx, yy, k;
state_t vw, vn;

// 最终状态的值
for (int i = 0; i < 9; i++) {
vw.f[i / 3][i % 3] = (i + 1) % 9;  //目标转态时各个位置的值
}

end_ans = get_hash(vw);  //目标转态时的hash值
a.hash_num = get_hash(a);

a.g = 0;         //初始状态到状态a的代价函数
a.h = get_h(a);  //从状态a到目标状态的最佳路径的估计代价

vis[a.hash_num] = 1;
p[a.hash_num].pre = -1;

if (a.hash_num == end_ans) {
printf("\n");
return;
}

priority_queue<state_t> q;
q.push(a);

while (!q.empty()) {
a = q.top(), q.pop();

for (int i = 0; i < 4; i++) {
xx = a.x + dir[i][0];
yy = a.y + dir[i][1];
if (xx < 0 || yy < 0 || xx >= 3 || yy >= 3)
continue;

vw = a;
swap(vw.f[a.x][a.y], vw.f[xx][yy]);  //交换双方的值

k = get_hash(vw);
if (vis[k])
continue;

vis[k] = 1;
vw.hash_num = k;
// 当前x的位置
vw.x = xx;
vw.y = yy;
// 更新g，增加1
vw.g++;
// 评估距离
vw.h = get_h(vw);

p[k].pre = a.hash_num;
p[k].ch = d[i];

//如果当前状态的hash值等于目标状态的hash值，表示已经到达目标状态
if (k == end_ans)
{
print(k);
printf("\n");
return;
}

q.push(vw);
}
}
}

int main() {
char a[30];

while (gets(a)) {
int i, j, k, n;
// 输入初始状态
state_t e;
n = strlen(a);

for (i = 0, j = 0; i < n; i++) {
if (a[i] == ' ')
continue;
if (a[i] == 'x') {
// x设置为0
e.f[j / 3][j % 3] = 0;
e.x = j / 3;
e.y = j % 3;
} else
e.f[j / 3][j % 3] = a[i] - '0';
j++;
}

// 这边涉及到一个逆序数问题，如果开始状态的逆序数为奇数，那么这个状态只能到达逆序数为奇数的转态，同理偶数逆序数的状态也只能到达逆序数为偶数的状态
// 逆序数：前面的数大于后面的数
for (i = 0, k = 0; i < 9; i++) {
if (e.f[i / 3][i % 3] == 0)
continue;
for (j = 0; j < i; j++) {
if (e.f[j / 3][j % 3] == 0)
continue;
if (e.f[j / 3][j % 3] > e.f[i / 3][i % 3])
k++;
}
}
// 求逆序数
if (k & 1)
printf("unsolvable\n");
else
AStar(e);
}
return 0;
}
```

0 条评论

• ### 翻转瓷砖Fliptile（开关反转）- POJ 3279

Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

• ### CodeForces 982F：The Meeting Place Cannot Be Changed（有向图）

Petr is a detective in Braginsk. Somebody stole a huge amount of money from a ba...

• ### POJ-3641：Pseudoprime numbers（快速幂）

Fermat's theorem states that for any prime number p and for any integer a > 1, a...

• ### 翻转瓷砖Fliptile（开关反转）- POJ 3279

Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

• ### 实习杂记（22）：仿照VideoView+MediaPlayerController做视频

主要是抽取出来，有些方法是hide,有些类是  internal层的，无法使用，所以需要自己去想办法弄，

• ### LintCode 交错正负数题目分析代码

样例 给出数组[-1, -2, -3, 4, 5, 6]，重新排序之后，变成[-1, 5, -2, 4, -3, 6]或者其他任何满足要求的答案

• ### POJ-3641：Pseudoprime numbers（快速幂）

Fermat's theorem states that for any prime number p and for any integer a > 1, a...

• ### Android打造不一样的新手引导页面（一）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

• ### 仿qq最新侧滑菜单

为了后续对这个项目进行优化，比如透明度动画、背景图的位移动画，以及性能上的优化。 我把这个项目上传到github上面，请大家随时关注。 github地址 htt...

• ### Greedy & Violent

1 2 3//坐标缩小后就可以更方便的选择 double pos = (double)i / n * (n + m);//原来雕像的位置 ans += f...