Describe：
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:
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
曾经有位大牛说过，没做过八数码问题的人生不是一个完整的人生，等我认认真真做完一遍之后，不管别人信不信，反正我信了┓(;´_｀)┏。
这道题我用了康托展开这样一个小技巧，它是一种hash函数，是数列和数字之间的双映射函数，相当于对一个数列进行全排列，不同的排列方式之间用一个方法给他们排个序，每一个排列对应的序号数就是这个排列（数列）与这个数字之间的hash映射。公式如下：
设有一个n位的每一位均不同的数列，则其对应的hash值X为：
X = a[n] * (n-1)! + a[n-1] * (n-2)! + … + a[i] * (i-1)! + … + a[1] * 0!
其中i为第i位，a[i]为数列中第i位右边（即比i低的位）比第i位数小的数字的个数。
这样就可以将一个数列，更进一步地，一个字符串，压缩成一个整数，大大节省了空间，在对两个数列判重的时候也不用一位一位地去判断了，节省了计算量。
而这道题主体的思想（其中一种，当然其他解法也有很多）就是A*搜索，他是一种广泛用于AI及游戏开发的一类搜索算法，我才疏学浅，估计讲不明白，贴一个个人认为比较好的连接：
https://blog.csdn.net/coutamg/article/details/53923717
这样综合应用一下就解出了这道八数码，HDU结果：
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
const int MAXN = 370000;
const int aim = 46233;
int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int vis[MAXN];
char index[] = {'l', 'u', 'r', 'd'};
int mov[] = {-1, -3, 1, 3};
struct node
{
int s[15];
int zero, Hash = -1;
string path;
int h, g;
};
bool operator<(node a, node b)
{
return a.h!=b.h ? a.h>b.h : a.g>b.g;
}
void Swap(int& a, int& b)
{
int tmp;
tmp = a;
a = b;
b = tmp;
}
int cantor(int s[])
{
int sum = 0;
for(int i = 0; i < 9; i++)
{
int cnt = 0;
for(int j = i + 1; j < 9; j++)
if(s[j] < s[i]) cnt++;
sum += cnt * fac[9-i-1];
}
return sum;
}
bool ifUnsolvable(int s[])
{
int cnt = 0;
for(int i = 0; i < 9; i++)
if(s[i])
for(int j = i + 1; j < 9; j++)
if(s[j] < s[i] && s[j]) cnt++;
if(cnt % 2) return true;
return false;
}
int geth(int s[])
{
int sum = 0;
for(int i = 0; i < 9; i++)
{
int x1, y1, x2, y2;
if(s[i] != 0)
{
y1 = ((i+1)+2)/3;
y2 = (s[i]+2)/3;
x1 = ((i+1)+2)%3 + 1;
x2 = (s[i]+2)%3 + 1;
sum += (abs(x1-x2) + abs(y1-y2));
}
}
return sum;
}
void init(node cur)
{
memset(vis, -1, sizeof(vis));
cur.Hash = cantor(cur.s);
cur.h = geth(cur.s);
cur.g = 0;
vis[cur.Hash] = 1;
}
bool check(node c, int i)
{
if(c.zero-2<=0 && i==1) return false;
if(c.zero+2>=8 && i==3) return false;
if((c.zero+3)%3==0 && i==0) return false;
if((c.zero+1)%3==0 && i==2) return false;
return true;
}
void Astar(node IN)
{
priority_queue<node> OPEN;
node cur, opt;
cur = IN;
init(cur);
OPEN.push(cur);
while(!OPEN.empty())
{
cur = OPEN.top();
OPEN.pop();
for(int i = 0; i < 4; i++)
{
opt = cur;
if(check(opt, i))
{
int tmp = opt.zero;
int mv = mov[i];
int a = opt.s[tmp], b = opt.s[tmp+mv];
Swap(a, b);
opt.s[tmp] = a, opt.s[tmp+mv] = b;
opt.zero += mv;
opt.Hash = cantor(opt.s);
if(opt.Hash == cur.Hash) continue;
if(vis[opt.Hash] == -1)
{
vis[opt.Hash] = 1;
opt.g = cur.g + 1;
opt.h = geth(opt.s);
opt.path += index[i];
OPEN.push(opt);
}
if(opt.Hash == aim)
{
cout << opt.path << endl;
return;
}
}
}
}
printf("unsolvable\n");
}
int main()
{
node in;
char ch[100];
while(gets(ch))
{
memset(in.s, 0, sizeof(in.s));
in.path.clear();
int l = strlen(ch);
int j = 0;
for(int i = 0; i < l; i++)
{
if(ch[i]>='0' && ch[i]<='9')
in.s[j++] = ch[i] - '0';
else if(ch[i]=='x')
{
in.zero = j;
in.s[j++] = 0;
}
}
in.Hash = cantor(in.s);
if(in.Hash == aim)
{
printf("\n");
continue;
}
else if(ifUnsolvable(in.s))
printf("unsolvable\n");
else
Astar(in);
}
return 0;
}
京公网安备 11010502036488号