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;
}