游戏玩法：在start.txt文件中设置初始状态   按上下左右移动到1 2 3 4 5 6 7 8 空 为止

主要是帮忙测试下

额 这个我不知道怎么弄 做可视化的东西一直都是这样弄的

可以啊  上下左右按钮就可以控制

呵呵 电脑寻得的可都是最短路径哦   希望你能找出一种比电脑用的步数还少的方法来

那样你就算帮我忙啦    还有就是电脑提示不能移动的  你能移动出来也算帮我忙了

准备在这挂几天  然后把内核拿去做Android游戏

就是让你帮忙来验证电脑的判断是否正确

比如它提示不能移动 你移动出来啦  那说明我算法有漏洞

比如它用了10步才移动出来  而你用了9步  那说明那个我的算法是错的

就是这个意思

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

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

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

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

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

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

9!不过36万而已  先广搜预处理 把这36万多个状态的最短路径全部存储起来

至于怎么在O（1）的时间内找到这个状态  就是康托展开式的应用  

比如3！有 123 132 213 231 312 321 这六个  要找到任何一个排列是第几个数

比如123 就是第一个  132 就是第二 。。。 321 就是第六个

其实康托展开式找到的是任何一个排列数前面有几个排列数  具体算法是

对于排列数的每一位判断后面有几个位置 可以把那几个比它小的安排进去

比如123 i = 0*2！(有0个比1小的数)(后面有两个位置) + 0*1！(有1个比2小的数，但是1已经在前面出现了)(后面有1个位置) + 0*0(有2个比3小的数，但是都在前面出现了)(后面有0个位置) = 0 （在123这个排列前面的排列数目为0）

比如231 i = 1*2！(有1个比2小的数)(后面有两个位置) + 1*1！(有2个比3小的数，但是2已经在前面出现了)(后面有1个位置) + 0*0(有0个比1小的数)(后面有0个位置) = 3 （在123这个排列前面的排列数目为3）



[ 本帖最后由 laoyang103 于 2012-3-8 17:15 编辑 ]

把核心代码给大牛们看一下啊  其实就是一个广度有限搜索  还有一个 状态定位函数

int CLaoYangWnd::kangtuo(char a[])
{
    int fac[]={1,1,2,6,24,120,720,5040,40320};//康托展开判重
    int i,j,sum = 0,t = 0;
    for(i = 0;i<9;i++)
    {
        t = 0;
        for(j = i+1;j<9;j++)
            if(a[j]<a[i])
                t++;
        sum += t*fac[9-i-1];
    }
    return sum+1;
}

void CLaoYangWnd::bfs()
{
    char h[4] = {'d','u','r','l'};
    int i,x,y;
    Node now,next;now.pa = "";next.pa = "";
    for(i = 0;i<8;i++)now.a[i] = i+1;
    now.a[8] = 0;now.pos = 8;
    now.index = 46234;foot[46234] = true;   
    queue<Node> q;q.push(now);
    int dec[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        for(i = 0;i<4;i++)
        {
            x = now.pos/3+dec[i][0];
            y = now.pos%3+dec[i][1];
            if(x<0 || y<0 || x>2 || y>2)
                continue;
            next = now;
            next.pos = 3*x+y;
            next.a[next.pos] = 0;
            next.a[now.pos] = now.a[next.pos];
            next.index = kangtuo(next.a);
            if(!foot[next.index])
            {
                foot[next.index] = true;
                next.pa += h[i];
                path[next.index] = next.pa;
                q.push(next);
            }
        }
    }
   
}

完整的工程

[ 本帖最后由 laoyang103 于 2012-3-8 17:24 编辑 ]

为啥不可以呢   有VC6.0就行