类华容道问题，谁会编程解决？（小学计算机奥赛题）

三岛由纪夫

在3*3的方格内，任给打乱的8个数字1-8的一种布局，按照华容道那种走法上下左右，使之排列成顺序的，编程求解，输入数字1-8任意一种布局，输出每一步的走法。

这是我小学计算机奥赛时候的一道练习题

扩展：nXn的方给内任给数字1到n*n-1的一种布局，输出每一步走法

jh2009

设计一个N x N的matrix, 把0-N随机放进去，只有0和临近（0位置P的P－N，P+N，P－1，P+1）的数字可以交换位置。接下来就是枚举，直到0位置（或者1位置）往后的数字都比前一个数字大1为止。记录下成功排序的执行步骤。

程序也许会写得很复杂所以不写代码了，思路就是这样。

三岛由纪夫

设计一个N x N的matrix, 把0-N随机放进去，只有0和临近（0位置P的P－N，P+N，P－1，P+1）的数字可以交换位置。接下来就是枚举，直到0位置（或者1位置）往后的数字都比前一个数字大1为止。记录下成功排序的执行步骤。 ...
jh2009 发表于 26.9.2009 13:45

（sorry，原题我有笔误，就是在3X3的方阵内放打乱的8个连续数字（3X3-1），或在n*n方阵内放打乱n*n-1个连续数字）

不用写代码，请写个伪代码，谢谢先

顺便给个计算复杂度的度量

顺便说一下：你这思路里面没有判敛函数，恐怕计算机得算一辈子。如果真这么简单也不用奥赛了，直接当作小学入学考试题得了。

GoodOldBilly

《人工智能》那门课里面的，楼主在中国学CS的话，应该知道的算法

清华计算机系马少平讲的

jh2009

你说得没错，3x3可以枚举，NxN枚举就死了。

老规矩，自己拉的屎自己擦，大家围观一下就行了。

三岛由纪夫

《人工智能》那门课里面的，楼主在中国学CS的话，应该知道的算法

清华计算机系马少平讲的
GoodOldBilly 发表于 26.9.2009 16:01

弄道小学题目给大家玩玩儿，免得有了孩子后，孩子上了小学，问你题目你都不会算。

只会枚举的自己枚举玩儿去吧。3*3就能枚举了？不懂装懂的人还真是有。

jh2009

你NB也没给个结论嘛，只知道拉屎不懂擦屁股。

shannon

A* + using alpha-beta-pruning to optimize the searching process.

Vesper_Lynd

需要解决:
搜索的解空间巨大，如何存储和编码棋盘棋局
如何快速在已存棋盘格局中搜索新产生的棋局在以前是否已经产生

Eros

A* + using alpha-beta-pruning to optimize the searching process.
shannon 发表于 27/9/2009 22:34

说的对呵

重要的不是广度优先搜索，重要的是快速查询和剪枝，提高效率


网上kiang来的华容道算法，不是lz这道题的：

/************************************************************************/
/* 华容道初稿
/* GPL,大家可以任意修改,但是需要保留原作者,谢谢
/* Author: L.T.Dreamy
/* 2007-10-5 完成于西安电子科技大学
/*
/************************************************************************/

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#include "string.h"
#include "time.h"

struct GridNode{
        unsigned char grid[5][4];        //棋盘
        GridNode *next_queue;        //队列中的下一个节点
        GridNode *parent;        //其父亲节点
        GridNode *next_hash;        //hash 表中的下一节点
};

//这样复制速度快
#define g_copy(g1,g2){/*复制棋盘 g2->g1*/\
        unsigned int *t1,*t2;\
        t1=(unsigned int*)(g1);\
        t2=(unsigned int*)(g2);\
        t1[0]=t2[0];\
        t1[1]=t2[1];\
        t1[2]=t2[2];\
        t1[3]=t2[3];\
        t1[4]=t2[4];\
}

#define Width 4        //
#define Height 5

//出口
#define X 3
#define Y 1

//棋盘边界
struct Bound {
        int top;
        int bottom;
        int left;
        int right;
};

//边界
Bound bound={0,4,0,3};

//哈希表结构
struct hashlink{
        unsigned char len; //此桶中数据大小
        GridNode *next;
};

//队列结构
struct queuelink{
        GridNode *first;
        GridNode *iterater;
        GridNode *tail;
};

#define MAX_CON 65536        //设最大为2^16
//哈希表
hashlink hlink[MAX_CON]={0};
//队头
queuelink queue;

FILE *f;

//获得hash表的hash值
unsigned short GetHashValue(unsigned int *grid)
{
        unsigned int mask1 = 524287; //19个1
        unsigned int mask2 = 8191; //13个1
        unsigned short len = 65535;

        unsigned int result =0;
        result += ((grid[0] & (mask1<<13))>>13)|((grid[0] & mask2)<<19);
        result ^= grid[1];
        result += ((grid[2] & (mask1<<13))>>13)|((grid[2] & mask2)<<19);
        result ^= grid[3];
        result ^= ((grid[4] & (mask1<<13))>>13)|((grid[4] & mask2)<<19);
        result += grid[5];

        return result%len;
}

void print(unsigned char* grid)
{
        int i;
        /*
        fprintf(f,"\n--------------\n");
        for(int i=0;i<Height;i++)
        {
                for(int j=0;j<Width;j++)
                        fprintf(f,"%c",*(grid+Width*i+j));
                fprintf(f,"\n");
        }
        fprintf(f,"--------------\n\n");
*/
        fprintf(f,"\n");
        for(i=0;i<=Height*2;i++)
        {
                for(int j=0;j<=Width*4;j++)
                {
                       
                        if(i%2==0) //奇数行画--
                        {
                                if(j%4!=0)
                                {
                                        if(i/2-1>=0 && (*(grid+Width*(i/2-1)+(j/4))=='V'||\
                                                *(grid+Width*(i/2-1)+(j/4))=='C'||\
                                                *(grid+Width*(i/2-1)+(j/4-1))=='C'))
                                                fprintf(f," ");
                                        else
                                                fprintf(f,"-");
                                }
                                else
                                        fprintf(f,"+");
                        }else{ //偶数行画 | 和 字母
                                if(j%4==0)
                                {
                                        if(j/4+1<=Height && (*(grid+Width*(i/2)+(j/4-1)) == 'H' ||\
                                                *(grid+Width*(i/2)+(j/4-1)) == 'C' ||\
                                                *(grid+Width*(i/2-1)+(j/4-1)) == 'C'))
                                                fprintf(f," ");
                                        else
                                                fprintf(f,"|");
                                }
                                else if(j%4==2)
                                {
                                        if(*(grid+Width*(i/2)+(j/4))!='0')
                                                fprintf(f,"%c",*(grid+Width*(i/2)+(j/4)));
                                        else
                                                fprintf(f," ");
                                }else
                                        fprintf(f," ");
                        }
                }
                fprintf(f,"\n");
        }
}

//将新的棋盘格局加入到hash表中,并且将此新生成的节点加入到队列链表中,并将其与其父亲节点关联起来
char * InsertNode(unsigned *grid,GridNode *parent)
{
        //检测是否有相同的棋盘格局
        unsigned short index= GetHashValue(grid);
        GridNode *p = hlink[index].next;
        GridNode *q = NULL;

        if(hlink[index].len == 0)
        {
                GridNode *g = new GridNode;
                //复制棋盘
                g_copy(g->grid,grid);
                g->next_queue = NULL;
                g->next_hash = NULL;
                g->parent = parent;
                queue.tail->next_queue = g;
                queue.tail=g;
               
                hlink[index].next = g;
               
                //此hash链数据值++
                hlink[index].len ++ ;

                return (char*)g; //返回此节点的指针
        }

        if(hlink[index].len > 0)
        {
                while(p!=NULL)
                {
                        //如果相同,则返回NULL,表示不用再插入相同的棋盘格局了
                        if(grid[0] == *((unsigned int*)(p->grid[0]))&&\
                                grid[1] == *((unsigned int*)(p->grid[1]))&&\
                                grid[2] == *((unsigned int*)(p->grid[2]))&&\
                                grid[3] == *((unsigned int*)(p->grid[3]))&&\
                                grid[4] == *((unsigned int*)(p->grid[4])))
                        {
                                //fprintf(f,"Same Node\n");
                                return NULL;
                        }
                        q = p;
                        p = p->next_hash;
                }
                GridNode *g = new GridNode;
                //复制棋盘
                g_copy(g->grid,grid);
                g->next_queue = NULL;
                g->next_hash = NULL;
                g->parent = parent;
                queue.tail->next_queue = g;
                queue.tail=g;               
               
                q->next_hash = g;
               
                //此hash链数据值++
                hlink[index].len ++ ;

                return (char*)g; //返回此节点的指针
        }       
       
        return NULL; //返回此节点的指针
}

//检测是否可以走动
//00H-不能移动,01H-上,10H-左,100H - 右,1000H -下 [返回值]
int Detect(unsigned char* grid,int row,int col,int w,int h)
{
        int result= 0;
        //检测上边,如果上边还有一层
        if(row-1>=0)
        {
                for(int j=0;j<w;j++)
                {
                        if(*(grid+(row-1)*Width+(col+j))!='B')
                        {
                                break;
                        }
                }
                if(j==w)
                        result += 1<<0;
        }
       
        //左边
        if(col-1>=0)
        {
                for(int j=0;j<h;j++)
                {
                        if(*(grid+(row+j)*Width+(col-1))!='B')
                        {
                                break;
                        }
                }
                if(j==h)
                        result += 1<<1;
        }
       
        //下边
        if(row+h<Height)
        {
                for(int j=0;j<w;j++)
                {
                        if(*(grid+(row+h)*Width+(col+j))!='B')
                        {
                                break;
                        }
                }
                if(j==w)
                        result += 1<<2;
        }
       
        //右边
        if(col+w<Width)
        {
                for(int j=0;j<h;j++)
                {
                        if(*(grid+(row+j)*Width+(col+w))!='B')
                        {
                                break;
                        }
                }
                if(j==h)
                        result += 1<<3;
        }       

        return result;        //
}

#define ggrid(x,y) (*((unsigned char*)cur_q->grid+Width*(x)+(y)))

bool test(GridNode *cur_q)
{
        for(int i=0;i<Height;i++)
        {
                for(int j=0;j<Width;j++)
                {
                        switch(ggrid(i,j)) {
                        case 'C':
                                if(ggrid(i+1,j)!='0' || \
                                        ggrid(i,j+1)!='0' ||\
                                        ggrid(i+1,j+1)!='0')
                                        goto error;
                                break;
                        case 'V':
                                if(ggrid(i+1,j)!='0')
                                        goto error;
                                break;
                        case 'H':
                                if(ggrid(i,j+1)!='0')
                                        goto error;
                                break;
                        default:
                                break;
                        }
                }
        }
        return false;
error:
        print((unsigned char*)cur_q->grid);
        fprintf(f,"Parent \n");
        print((unsigned char*)cur_q->parent->grid);
       
        return false;
}

bool IsResoluted(unsigned char* grid)
{
        if(*(grid+X*Width+Y)=='C')
                return true;
        return false;
}

//根据不同的man探测并生成新的格局,如果返回true表明找到结果了..false表示未移动
bool GenNewGrid(unsigned char* old_grid,int row,int col,GridNode *cur_q)
{
        int w,h;
        switch(*(old_grid+Width*row+col)) {
        case 'C':        //曹操
                w=2;
                h=2;
                break;
        case 'V':        //竖着的五虎将
                w=1;
                h=2;
                break;
        case 'H':        //横着的五虎将,关羽
                w=2;
                h=1;
                break;
        case 'S':        //卒
                w=1;
                h=1;
                break;
        case 'B':        //空格,nothing to do
                break;;
        default:               
                printf("error 士兵 %c \n",*(old_grid+Width*row+col));
                return false;
        }

        //探知方向
        int direct = Detect(old_grid,row,col,w,h);
        //printf("Direct : ++++ %0x  \n",direct);
       
        unsigned char new_grid[5][4];
               
        //如果探知可以移动,则移动,并将新的格局加入到队列
        if(direct!=0)
        {
                int i,j;
                //向上
                if((direct & 0x01) == 0x01)
                {
                        //将旧的格局copy到新的格局,在新的格局中修改数据
                        g_copy(new_grid,old_grid);
                        for(i=0;i<h+1;i++)
                        {
                                for(j=0;j<w;j++)
                                {
                                        if(i==h)
                                        {
                                                new_grid[row-1+i][col+j] = 'B';
                                                continue;
                                        }
                                        new_grid[row-1+i][col+j]=new_grid[row+i][col+j];
                                }                               
                        }
                        //printf("上**********************\n");
                        //print((unsigned char*)new_grid);

                        InsertNode((unsigned *)new_grid,cur_q);
                        test(cur_q);
                        if(IsResoluted((unsigned char*)new_grid))
                        {
                                printf("@@@@@@@@@ Resolution is Gernated! @@@@@@@@@@@@\n");
                                return true;
                        }
                       
                }
                //向左
                if((direct & 0x02) == 0x02)
                {
                        //将旧的格局copy到新的格局,在新的格局中修改数据
                        g_copy(new_grid,old_grid);
                        for(i=0;i<w+1;i++)
                        {
                                for(j=0;j<h;j++)
                                {
                                        if(i==w)
                                        {
                                                new_grid[row+j][col-1+i] = 'B';
                                                continue;
                                        }
                                        new_grid[row+j][col-1+i]=new_grid[row+j][col+i];
                                }                               
                        }
                        //printf("左**********************\n");
                        //print((unsigned char*)new_grid);

                        InsertNode((unsigned *)new_grid,cur_q);
                        test(cur_q);
                        if(IsResoluted((unsigned char*)new_grid))
                        {
                                printf("@@@@@@@@@ Resolution is Gernated! @@@@@@@@@@@@\n");
                                return true;
                        }
                }
                //向下
                if((direct & 0x04) == 0x04)
                {
                        //将旧的格局copy到新的格局,在新的格局中修改数据
                        g_copy(new_grid,old_grid);
                        for(i=h;i>=0;i--)
                        {
                                for(j=0;j<w;j++)
                                {
                                        if(i==0)
                                        {
                                                new_grid[row+i][col+j] = 'B';
                                                continue;
                                        }
                                        new_grid[row+i][col+j]=new_grid[row-1+i][col+j];
                                }                               
                        }
                        //printf("下**********************\n");
                        //print((unsigned char*)new_grid);

                        InsertNode((unsigned *)new_grid,cur_q);
                        test(cur_q);
                        if(IsResoluted((unsigned char*)new_grid))
                        {
                                printf("@@@@@@@@@ Resolution is Gernated! @@@@@@@@@@@@\n");
                                return true;
                        }
                }
                //向右
                if((direct & 0x08) == 0x08)
                {
                        //将旧的格局copy到新的格局,在新的格局中修改数据
                        g_copy(new_grid,old_grid);
                        for(i=w;i>=0;i--)
                        {
                                for(j=0;j<h;j++)
                                {
                                        if(i==0)
                                        {
                                                new_grid[row+j][col+i] = 'B';
                                                continue;
                                        }
                                        new_grid[row+j][col+i]=new_grid[row+j][col+i-1];
                                }                               
                        }
                        //printf("右**********************\n");
                        //print((unsigned char*)new_grid);

                        InsertNode((unsigned *)new_grid,cur_q);
                        test(cur_q);
                        if(IsResoluted((unsigned char*)new_grid))
                        {
                                printf("@@@@@@@@@ Resolution is Gernated! @@@@@@@@@@@@\n");
                                return true;
                        }
                }
               
        }

        return false;
}



//棋盘格局生成器,即走步器
void Traverse(unsigned int *grid)
{
        //初始化队列
        GridNode head;
        queue.first = &head;
        queue.tail = &head;
               
        //加入初始棋盘格局
        if((queue.first = (GridNode*)InsertNode(grid,NULL))==NULL)
        {
                printf("Init error!\n");
                return;
        }
        queue.iterater = queue.first;
       
        //如果队列不空,则继续广度搜索
        while(queue.iterater!=NULL)
        {
                //对于棋盘中的每一个元素进行探测,看是否可以移动
                unsigned char *c_grid = (unsigned char*)(queue.iterater->grid);        //获取队列头的棋盘格局
                //print((unsigned char*)c_grid);
                for(int i=0;i<Height;i++)
                {
                        for(int j=0;j<Width;j++)
                        {
                                //已经处理的或空格的情况
                                if(*(c_grid+Width*i+j)=='0' || *(c_grid+Width*i+j)=='B')
                                        continue;
                               
                                //表明此网格上有一个man
                                //printf("-----  %c  -----\n",*(c_grid+Width*i+j));
                                if(GenNewGrid((unsigned char*)c_grid,i,j,queue.iterater)==true)
                                {
                                        //找到结果了..^_^
                                        //打印结果
                                        GridNode *p=queue.iterater;
                                        fprintf(f,"^^^^^^^^^^^^^^^^^\n\n");
                                        int n=0;
                                       
                                        while(p!=NULL)
                                        {
                                                print((unsigned char*)p->grid);
                                                p = p->parent;
                                                n++;
                                        }
                                        fprintf(f,"\n-------------\n%d 步\n",n);
                                       
                                        int sum=0;
                                        for(int i=0;i<MAX_CON;i++)
                                        {
                                                fprintf(f,"%d  ",hlink.len);
                                                if(hlink.len>10)
                                                        fprintf(f,"$$$$$$$$$$$$$$$$\n");
                                                if(i%20==0)
                                                        fprintf(f,"\n");
                                                sum += hlink.len;
                                        }
                                        printf("搜索节点数目：%d \n",sum);
                                        return;
                                       
                                }
                        }
                }
                queue.iterater = queue.iterater->next_queue;
        }

        if (queue.iterater == NULL)
        {
                printf("*** No resultion! ***\n");
                return ;
        }

}

//主函数
int main(int argc, char* argv[])
{
        f=fopen("a.txt","w+");       

        unsigned char init_grid[5][4]={
                'V','C','0','V',\
                '0','0','0','0',\
                'V','H','0','V',\
                '0','S','S','0',\
                'S','B','B','S'
        };

        //char a[]={32,0,0,0x80};
        //printf("%0x\n",GetHashValue((unsigned int*)a));

        //初始化
        memset((char*)hlink,0,sizeof(hashlink)*MAX_CON);
        memset((char*)&queue,0,sizeof(queuelink));
       
        clock_t start;
        clock_t finish;
        start = clock();

        Traverse((unsigned int*)init_grid);
        finish = clock();
        double tt=(double)(finish-start)/CLOCKS_PER_SEC;
        printf("Execute time is : %lf 秒\n",tt);
        fclose(f);
        return 0;
}