这就是图论中的最短路径问题。
每一种状态为一个结点，共有9!个结点。两种可以相互转换的状态之间有一条边。
求出此图以最终状态（123456780）为根的最小生成树即可。在9!个结点中有一部分是不在这棵树里的，它们是不可到达的状态，也就是说这种状态不可能恢复到123456780。
走法就是这种状态对应结点到根的这条路径。如果这种状态不在树里则说明无解。

嗯。解的判定问题已经有答案了。

给出一个状态，求一下它的逆序数，会有奇偶两种情况。
有一个定理：说移动这种操作不改变序列的奇偶性。由于答案是偶的，所以任何奇序列都不可解。（这个定理很好证）
不知道老杨是不是用这个方法判定的。

但那个定理并不意味偶序列就都可解。
我有点记不清了，但印象里这是个事实。就是的确偶的都可解。（这个怎么证我就不知道了）
所以全部可解的序列就是 9!/2 这么多个。

八数码这个问题是很经典的人工智能问题。想求最优解就是广搜，不太需要图论的知识。

这和算法里一般指的那个最短路问题好像还挺不一样的吧。最短路的精典解法不是Dijkstra法么。

呵呵。在下本科的毕业设计就做的是图论方面的东西。不过研究的是网络连通度方面的问题。
研究的东西比较理论，和算法没什么太大关系。但由于自己有兴趣，也私下看了不少求连通度的算法。
算法的复杂度还是很高的，计算机学家研究的很深，而且有不少人坚信现在已知的算法离可能的复杂度下限还有距离。

隔的有点久了，发现也忘了不少了。

[ 本帖最后由 pangding 于 2012-3-7 00:03 编辑 ]

呵呵，明天我给你实现一下这个算法吧。

广搜可以解决这个问题，但每次玩一次都搜一遍效率太低了。建立最小生成树也需要进行一次广搜，但建立之后每次玩只需要从树中找到相应结点即可。

关于这个游戏还可以用A*算法进行启发式搜索，但并不保证一定能找到最少的步骤。这就看启发函数的选择了。

嗯。我当年也写过八数码，也是建好了树每次查的。我是说只解一次的话，广搜就行了。也可以用双端广搜。
不过 杨大哥 要是有时间写算法，我当然很乐意了。写好了的话，能从中学的东西还是很多的。

要是谁能想出启发函数，没准对人工解八数码问题也能有点帮助呢~~
其实这个游戏我还是研究了好一会才会自己玩的。不过要过一关普遍也得走个 4，50 步。现在还玩的没以前好了。

谢谢pangding大侠的指点  我会把初始状态随机生成  移动成功后给点提示

其实原理很简单   就是康托展开式  + 广度有限搜索  

当你打开程序的时候你会发现需要等一会  其实那一会就是在广搜进行路径打表

也就是对于9！这么多状态的最短路径表  等玩的时候就可以在O（1）时间内找到最短路径

提示无法移动的原理是路径表内这个状态的路径为空  至于你说的那个逆序数我回去学习下

[ 本帖最后由 laoyang103 于 2012-3-7 07:02 编辑 ]

接分

受教了

这是建立树的代码，时间仓促没有进行很好的优化。
可以测试一下，初始化的时间在我的机器上是300ms。主要是为了节省空间而进行的运算比较耗时，换成位运算可以更快但内存消耗要增加一半。
输入只需直接输入成一行即可。比如
0 1 2
3 4 5
6 7 8
输入的格式为012345678。其它格式将被认为是无意义数据，程序退出。输出为每次该移动的方向。

#include<stdio.h>

#define UP        1
#define LEFT    2
#define DOWN    3
#define RIGHT    4

#define COUNT    362880

typedef struct
{
    int state;
    int father_id;
    char direction;
    char zr;
    char zc;
}STATE;

STATE states[COUNT];

void GenarateState(STATE **ss, int *e, int from, int n)
{
    int i, j, t;
    if(from >= n)
    {
        for(i = 0; i < n; i++)
        {
            (*ss)->state = (*ss)->state * 10 + e[i];
            if(e[i] == 0){ (*ss)->zr = i / 3; (*ss)->zc = i % 3;}
        }
        (*ss)++;
        return;
    }
    for(i = from; i < n; i++)
    {
        for(t = e[i], j = i; j > from; j--) e[j] = e[j - 1];
        e[from] = t;
        GenarateState(ss, e, from + 1, n);
        for(t = e[from], j = from; j < i; j++) e[j] = e[j + 1];
        e[i] = t;
    }
}

int SwapDigit(int state, int i, int j)
{
    int e[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    int ai, aj;
    ai = state / e[i] % 10;
    aj = state / e[j] % 10;
    return state - ai * e[i] - aj * e[j] + ai * e[j] + aj * e[i];
}

int GetStateIndex(STATE *s, int state)
{
    int i, j, d;
    for(i = 0, j = COUNT - 1; i <= j;)
    {
        d = (i + j) >> 1;
        if(s[d].state == state) return d;
        if(s[d].state < state) i = d + 1; else j = d - 1;
    }
    return -1;
}

int GetNextStateIndex(STATE * s0, STATE * s, int direction)
{
    int i, j;
    i = s->zr;
    j = s->zc;
    switch(direction)
    {
        case UP:    if(i > 0) return GetStateIndex(s0, SwapDigit(s->state, 8 - (i - 1) * 3 - j, 8 - i * 3 - j)); break;
        case LEFT:    if(j > 0) return GetStateIndex(s0, SwapDigit(s->state, 8 - i * 3 - j + 1, 8 - i * 3 - j)); break;
        case DOWN:    if(i < 2) return GetStateIndex(s0, SwapDigit(s->state, 8 - (i + 1) * 3 - j, 8 - i * 3 - j)); break;
        case RIGHT:    if(j < 2) return GetStateIndex(s0, SwapDigit(s->state, 8 - i * 3 - j - 1, 8 - i * 3 - j)); break;
    }
    return -1;
}

void InitStates(STATE * s)
{
    int si[COUNT], e[] = {0, 1, 2, 3, 4, 5, 6, 7, 8}, i, j, d, fid;
    STATE * ts;
    ts = s;
    GenarateState(&ts, e, 0, 9);
    si[0] = GetStateIndex(s, 123456780);
    s[si[0]].father_id = si[0];
    for(i = 0, j = 1; i < j; i++)//这个循环是建立最小生成树的主要逻辑代码，其它都是辅助完成状态的计算和转移
    for(d = 1; d <= 4; d++)
    {
        fid = GetNextStateIndex(s, s + si[i], d);
        if(fid >= 0 && s[fid].direction == 0)
        {
            s[fid].father_id = si[i];
            s[fid].direction = d;
            si[j++] = fid;
        }
    }
}

void PrintStep(STATE * s, int state)
{
    int root_id, id;
    root_id = GetStateIndex(s, 123456780);
    id = GetStateIndex(s, state);
    if(s[id].direction == 0)
    {
        printf("此状态无解\n");
        return;
    }
    while(id != root_id)
    {
        switch(s[id].direction)
        {
            case UP:    printf("上"); break;
            case LEFT:    printf("左"); break;
            case DOWN:    printf("下"); break;
            case RIGHT:    printf("右"); break;
        }
        id = s[id].father_id;
    }
}

int main()
{
    int state;
    InitStates(states);
    for(;;state = 0)
    {
        printf("\n\n输入初始状态（输入无意义则退出）：");
        scanf("%d", &state);
        if(GetStateIndex(states, state) < 0) break;
        PrintStep(states, state);
    }
    return 0;
}

[ 本帖最后由 beyondyf 于 2012-3-7 22:18 编辑 ]