华容道算法设计

Author:L.T.Dreamy

2007-10-5

 

1引言
华容道游戏是古老的中国传统益智游戏，以其变化多端百玩不厌的特点，与魔方独立钻石棋一起被国外智力专家并称为智力游戏界的三个不可思议。日本藤村幸三朗曾在《数理科学》杂志上发表华容道基本布局的最少步法为85步。后来清水达雄找出更少的步法为83步。美国著名数学家马丁·加德纳又进一步把它减少为81步。此后，至今还未曾见到打破这一记录的报道。而对解题效率的提升，则有数学家指出，此问题单靠数学方法很难求解。

华容道游戏的棋盘是由20个小正方形组成的长方形宽4 格长5 格，共有10 个棋子。其中五个棋子为张飞，赵云，马超，黄忠和关羽等。五虎将每个棋子占两格，可以是横的，也可以是竖的。四个棋子为刘备兵，各占一格。另一个棋子为曹操，占四格形状为正方形。棋盘的下部有两个空置的小格，作为华容道的出口。棋盘上仅有两个小方格，空着玩法就是通过棋子在这个长方形的棋盘内滑动，用最少的步数把曹操移出华容道.

 

2分析

对于像华容道、七巧板之类的滑块游戏来说，一般都是利用搜索解空间的方式获得可行的走步，象棋和围棋已然如此，只不过可以在可以在比较复杂的游戏中添加开局图和残局图也就是以前已有的走步历史，那么可以在搜索的过程中利用这些已有的结果，可以大大缩短解空间的个数和解题时间，对于华容道来说，广度优先的解空间搜索已经满足要求了，不需要添加历史棋局。

广度优先搜索大家都会，而且有一定的套路，下面是其伪代码：

 

Procedure 广度搜索(){
展开首节点得所有儿子节点，加入到处理队列中
While(队列不空){
  取出队列头节点；
  For(取出的节点的所有可能情况){
    将新产生节点加入到队列中；
  }
}
}


但是就华容道来说，需要解决一些问题。
1 搜索的解空间比较巨大，如何存储和编码棋盘棋局
2 如何快速在已存的棋盘格局中搜索探测是否新产生的棋局在以前已经产生
以最常见的布局:“立马横刀”为例，讲解华容道算法的设计和实现。见下图。

因为对于除关羽以外的其它四位五虎将都是竖立的，我们去掉其身份信息，只是表明其为V兵（竖着），而关羽因为是横着的，所以命名H兵，曹操直接C兵，其他普通兵则为S兵，空格为B（blank），而且都以每个兵在棋盘中的左上角的坐标来标识，而这个兵所占的其余部分设置为‘0’。这样，上图中的格局可以表示为

因为在虚走步的过程中会产生很多的重复步骤，即以前出现过的棋盘格局，所以每次产生新的棋盘格局之后需要对向前查找，看是否有跟当前棋盘格局一样的格局，如果有，则这个新产生的格局不加入到将要处理的队列中。
前人已有利用AVL平衡树和哈希表结构来处理重复节点搜索的，我们这里也是利用hash链表，只不过做了细微的变化。

下图是整个华容道算法的核心数据结构-用于存放棋盘格局

 

需要解释一下:所有节点都根据棋盘格局数据进行哈希得出其对应的哈希表中的桶,然后探测这一桶中是否有相同的棋盘格局,如果没有则添加到这个hash链的最后,并且,将其加入到队列的链表尾,同时其parent父节点域指向生成这个新格局的棋局节点处.整个网结构中有3种主要的结构,1队列,用于广度优先搜索,2hash链表,用于快速搜索[几乎是O(1)时间复杂度]重复节点,3父节点指针,用于最后生成解节点后,回溯输出整个华容道的走步(移动).[表中有点乱,而且不能追究其对与否,只是一个示意图]

 

3 数据结构

记录棋盘格局节点的数据结构：

struct GridNode{

         unsigned char grid[5][4];       //棋盘

         GridNode *next_queue;         //队列中的下一个节点

         GridNode *parent;        //其父亲节点

         GridNode *next_hash; //hash 表中的下一节点

};

它将被串在hash表上。

哈希表：

//哈希表结构

struct hashlink{

         unsigned char len; //此桶中数据大小

         GridNode *next;

};

#define MAX_CON 65536   //设最大为2^16

//哈希表

hashlink hlink[MAX_CON]={0};

处理队列：[所有新产生的格局都将加入到队列链尾，每次从头开始取棋盘格局进行虚走步产生新的格局]：

//队列结构

struct queuelink{

         GridNode *first;

         GridNode *iterater;

         GridNode *tail;

};

//队头

queuelink queue;

 

同时，我们用了简单的hash处理：

//获得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;
}

 

最后提一下关于运行时间的测量,以前没有用过这种方法.

 

<Time.h>这个头文件

 clock_t start;
 clock_t finish;
 start = clock();

   //这里是运算:

 finish = clock();
 double tt=(double)(finish-start)/CLOCKS_PER_SEC;
 printf("Execute time is : %lf 秒\n",tt);


 

 

3实现

最终打印出结果如下图:[上一排是最开始几个格局,下一排是最后几个格局]

初稿源代码[没时间仔细完美了..将就着看吧..大伙]:

文件:	华容道初稿源码.rar
大小:	3KB
下载:	下载

4时间测试

可能我的机器好一些,相对于http://www.cppblog.com/tx7do/archive/2006/09/18/12691.html这一篇的结果要好,P4 2.0 超线程, 1G 内存, 立马横刀0.58秒,但是走步在116步,并不是最少的85步,这些需要进一步的再测试,看是什么问题..最近没时间,没办法继续了.以后有时间再继续吧.其他只要是10子的华容道格局都可以,稍微修改一下就可以了..对于大于10子的,以此类推.

有资料显示双向搜索更优,我这里只是实现了单向搜索.大家可以讨论和考虑一下.

5联系:

如果谁有兴趣,可以跟我讨论,我的邮箱:[e-mail]  L.T.Dreamy,注意,转载前请先告知我..

L.T.Dreamy at 2007十一假期