软件开发>杂文>12

共享软件开发的点滴心得

[中文][English][日本語

Klotski puzzle

华容道

刘新宇

200611

现在商店里小孩子们的玩具可以说是琳琅满目,玩具可以说是孩子们最重要的宝贝。各种玩具中,我最喜欢拼插类玩具。小时候最爱不释手的是一套“插板”,每个插板是带有缺口的一小块塑料片。彼此可以插起来,一共有3种类型,如下图:

1、“插板”玩具

玩“插板”玩具最大的快乐在于可以用最简单的材料按照自己的想法构造出复杂的东西:汽车、坦克、飞机、大楼、机器人……。现在几乎没有小孩子还在玩“插板”了,但我坚持认为“插板”是我玩过的最好玩、最过瘾的玩具。现在我有时候还会玩LEGO的积木块,Mind Strom积木套装里还有一个电脑控制器(Lego Mind Strom 2.0机器人积木套装中的控制器RCX,内部使用日立的H8单片机)。2003年的阳历新年,我把自己关在屋子里组装“田宫”模型(TAMIYA)的豹II遥控坦克。每当我拼插出一个作品,都很有成就感,感觉自己发明了天大的东西。

仔细分析起来,小孩子最需要的就是这种成就感。通过手中的玩具,不断感觉自己的力量,感觉到自己能够按照意愿控制自己的小世界。好的玩具应该很容易让孩子获得成就感,而不是挫败他们的努力。从这个意义上说,华容道不是一个好玩具。

可能有些读者根本不知道“华容道”是一个什么玩具。按照通俗的说法,“华容道”和“九连环”、“七巧板”并称我国三大传统玩具。不过考证下来,似乎“华容道”有些像舶来品。一图胜千言,华容道玩具的样子如图[1]

2、“华容道”玩具

照片中的“华容道”玩具,都是木制的,我小时候有一个塑料的。其中人物都是彩色的传统水彩画,生动有趣,可惜没有留下照片。具体说,华容道是在一个长54的长方形盘子中,摆下10个大小不同的长方形小块作为棋子。盘子的底部有一个长2的缺口,棋子都摆下后,仍然会有2个空余空间,所以棋子间可以利用这两个空间互相滑动,变换位置。游戏的目标是将曹操移动到最下方的缺口。

华容道玩具明显来自《三国演义》中赤壁大战的故事。曹操在赤壁战败后,一路逃跑,遭到刘备军的数次埋伏,损兵折将。最后一次,曹操在名为“华容道”的地方遭到了刘备军将领关羽所带领伏兵的拦截。正常情况下,这对曹操军队的打击将是毁灭性的,曹操本人也必然被俘。但是关羽为人,重义轻利。考虑到曹操以前对自己的恩义,而放走了曹操极其军队。所以“华容道”游戏的目标,就是要让曹操这个最大的棋子从棋盘底部“逃掉”。并且关羽被设计为长12,特别难于移动,对当时战争情景的描绘真是惟妙惟肖。

我个人也相信 华容道在我国的历史不长。华容道玩具作者一定出自民间的普通匠人,因为很明显的一个错误是“华容道”玩具中的人物,里面刘备的五虎上将,关、张、赵、马、 黄一应俱全。而根据《三国演义》刘备凑齐五虎上将要等到入川之后,而赤壁大战发生时,刘备手下只有关羽、张飞和赵云。《三国演义》在民间普及至少要在明中 期以后,所以有人说“华容道”是民国年间发明的玩具也有一定的可能。

世界上其他各国也发现了类似的玩具,“华容道”玩具的英文名称是Klotski,来自波兰语[1]。日本在第二次世界大战期间也出现了类似的玩具,如下图[3]

3、日本的类似“华容道”的玩具

对孩子来说,华容道是一个非常难的玩具。如果没有别人指导,将曹操移动出来,几乎是“不可能任务(Mission impossible)”。类似的玩具还有“九连环”和“魔方”。不怕诸位笑话,我在小学二年级(8岁)时在老师推荐下买了一个华容道,直到初中一年级(13岁)才找到了把曹操移动出来的办法。当时我看到了别人成功走出了“横刀立马”的布局,但是太块,自己没有记住。回到家就按照印象边想边试,终于找到了答案。

事隔多年之后,我觉得可以重新玩华容道玩具了。不过这次不是我自己玩,而是我要通过计算机来玩。既然计算机比人类更有耐心,我就打算让计算机自己来找到“横刀立马”的解,并且是“最优解”——要在81步内,将曹操移动出来。

有读者说,网上不是有许多“华容道”游戏么?笔者这里不是要制作一个“华容道”的电子游戏,而是要制作一个智能的“华容道”电子游戏玩家。只要把初始布局摆放好后,程序就会自动计算,找出针对该布局的移动方法,在最少的步数内将曹操移动出来。

目前也存在着一些求解华容道的计算机程序[4][5]。这些程序在很早就已经给出了华容道的最优解。作者在这里不惜重复发明轮子,一来希望能够将解决一道题目的思路探讨清除,二来希望能够将最近流行的OO思想融入其中,所谓旧瓶装新酒,自娱自乐而已。

建模

静态模型

使用计算机程序解决华容道,第一步还是建模。最直观的想法是使用一个4x5的数组代表棋盘:

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0 0

然后不同的棋子,用不同的符号代表,填入此数组中。例如,“横刀立马”的起始布局可以表示如下:

1 x x 2

1 x x 2

3 4 4 5

3 7 8 5

6 0 0 9

这个模型固然直观,但是将来移动起来,程序就不大好写了。既然有C++和面向对象,以及性能较20年前突飞猛进的计算机,不妨奢侈一下,在保持直观的前提下,建立起稍微复杂,但是组织有序的对象模型。

首先要建立每个棋子(块)的模型,无论是正方形的曹操,还是长方形的关羽,在整个华容道移动过程中,都可以用其左上角的顶点位置,和棋子的大小(包括长,宽),以及其代表的人物,唯一确定下来。如下图:

4,右上角棋子赵云可以用3个因素确定:左上角顶点(3,0),大小(12),值(2)。

这个模型可以用一个C++类表示为:

class Block{

public:

//..

private:

Point _topLeft;

Size _size;

char _value;

};

为此还需要进一步定义PointSize,这两个类都非常容易实现。这里不在赘述,读者可以参考附录里面的参考实现。为了让Block可以方便地进行赋值,拷贝,以及放入STL容器。还需要给Block定义ctor, copy ctor, operator =,operator==等等。这些也都比较简单。

有了棋子的模型,还可以预先好曹操、赵云等一系列棋子,以方便后面布局,比如“横刀利马”,“插翅难飞”等等。为此引入一个安全类型枚举的概念。这个概念在Java中比较常见[6]C++中也不难实现,下面在给Block类内部定义了曹操,赵云等一系列预先定义的棋子:

class Block{

public:

// ..

public:

//

// 预定义好的棋子,stocked block enumerations

//

static Block ZhangFei;

static Block CaoCao;

static Block ZhaoYun;

static Block MaChao;

static Block GuanYu;

static Block HuangZhong;

static Block Solder1;

static Block Solder2;

static Block Solder3;

static Block Solder4;

// ..

};

由于C++标准规定,只有整形常量(包括bool型)才能在类内定义时初始化,所以这些棋子必须在类外初始化。下面的代码将布局初始化为“横刀立马”:

//

// "横刀立马"

//

Block Block::ZhangFei = Block(Point(0, 0), Size(1, 2), '1');

Block Block::CaoCao = Block(Point(1, 0), Size(2, 2), 'x');

Block Block::ZhaoYun = Block(Point(3, 0), Size(1, 2), '2');

Block Block::MaChao = Block(Point(0, 2), Size(1, 2), '3');

Block Block::GuanYu = Block(Point(1, 2), Size(2, 1), '4');

Block Block::HuangZhong = Block(Point(3, 2), Size(1, 2), '5');

Block Block::Solder1 = Block(Point(0, 4), Size(1, 1), '6');

Block Block::Solder2 = Block(Point(1, 3), Size(1, 1), '7');

Block Block::Solder3 = Block(Point(2, 3), Size(1, 1), '8');

Block Block::Solder4 = Block(Point(3, 4), Size(1, 1), '9');

曹操将来在打印输出的时候,将用字母’x’表示,张飞用’1’,赵云用’2’,依此类推。

有了棋子的表示模型还不够,还需要进一步为棋盘建模。采用上面的54列数组建模非常直观,这里可以仍然沿用。但是问题是,如何将前面的棋子模型和棋盘模型联系起来。方法就是根据棋盘中所有棋子模型,要能方便的计算出这个5x4数组的值。为此棋盘模型中至少要包含这样两个内容

  • 传统的5x4棋盘数组;
  • 棋盘中现有棋子的状态记录。

下面是一个棋盘的类定义。

class Klotski{

public:

static const int COL=4;

static const int ROW=5;

private:

char map[ROW][COL];

std::map<char, Block> blocks;

};

这里使用了map来代表所有棋子,并且利用棋子的值做索引,这样就可以方便快速地根据某个值定位到棋子。例如下面这几句,就可以用来非常方便地判断曹操是否已经逃跑了(走出了华容道):

const bool isSolved() const {

//找到“曹操”

std::map<char, Block>::const_iterator it = blocks.find('x');

return Point(1, 3) == (it->second).topLeft();

}

现在需要定义一些辅助函数讲棋盘和棋子联系起来。其思路就是当棋盘中棋子发生变化时,更新棋子所在位置的棋盘数组中的元素值。为此可以增加如下这些辅助函数:

class Klotski{

public:

// ..

private:

void clearMap(){

for(int y=0; y<ROW; ++y)

for(int x=0; x<COL; ++x)

map[y][x]='0';

}

void clearMap(const Block& block){

for(int i=0; i<block.size().height(); ++i)

for(int j=0; j<block.size().width(); ++j)

map[block.topLeft().y+i][block.topLeft().x+j]

= '0';

}

void updateMap(){

clearMap();

for(std::map<char, Block>::iterator it = blocks.begin();

it!=blocks.end(); ++it)

updateMap(it->second);

}

void updateMap(const Block& block){

for(int i=0; i<block.size().height(); ++i)

for(int j=0; j<block.size().width(); ++j)

map[block.topLeft().y+i][block.topLeft().x+j]

= block.value();

}

char map[ROW][COL];

std::map<char, Block> blocks;

};

clearMap有两个版本,一个将全部棋盘数组清0,另一个将某个棋子所在的位置清0;与此对应的updateMap也有两个版本,一个将某个棋子所在的位置对应的棋盘数组中的值设置为该棋子所代表的值,另一个将全部棋盘中的值根据所有的棋子都更新一遍。

动态模型

以上是华容道玩具中棋盘和棋子的静态模型。有了静态模型还不够,必须还建立该玩具的动态模型以模拟棋盘布局的建立过程和棋子移动的过程。

棋盘布局的建立比较简单,只需要将棋子依次放置到指定的位置后,更新棋盘数组即可。为此需要定义增加棋子的函数,并在增加后调用updateMap,例如:

void Klotski::addBlock(const Block& block){

blocks[block.value()] = block;

updateMap(block);

}

另外当棋盘初始化时,应该先保证棋盘被清0,当棋盘内容被拷贝或者赋值时,还应该更新棋盘数组,为此要在Klotski的构造函数和拷贝构造函数以及operator=中加入适当代码:

class Klotski{

public:

Klotski(){

clearMap();

}

Klotski(const Klotski& ref): blocks(ref.blocks){ updateMap(); }

const Klotski& operator=(const Klotski& ref){

if( *this == ref ) return *this;

blocks = ref.blocks;

updateMap();

return *this;

}

// ..

下面的代码完整地建立了“横刀立马”的棋局:

Klotski game;

game.addBlock(Block::ZhangFei);

game.addBlock(Block::CaoCao);

game.addBlock(Block::ZhaoYun);

game.addBlock(Block::MaChao);

game.addBlock(Block::GuanYu);

game.addBlock(Block::HuangZhong);

game.addBlock(Block::Solder1);

game.addBlock(Block::Solder2);

game.addBlock(Block::Solder3);

game.addBlock(Block::Solder4);

比较复杂的动态模型是移动棋子的模型,并非所有的棋子都能够移动,例如“横刀立马”起始状态中,曹操就根本无法移动。移动一枚棋子分为两步:

  • 判断一枚棋子是否可以向指定方向移动;
  • 如果能够移动,则移动它,并且更新棋盘数组。

任何一枚棋子都有上下左右4个移动方向,假设一次移动一步,则这4个移动方向可以表示为4个点:

  • Point(-1, 0):向左移动一步;
  • Point( 1, 0):向右移动一步;
  • Point( 0, -1):向下移动一步;
  • Point( 0, 1):向上移动一步;

判断一枚棋子是否能够移动可以用这样的方法:

  • 首先要判断这枚棋子在指定方向上移动一步后,是否会超出棋盘的范围,也就是移动后其任何一部分的横座标在04以内,而纵座标在05以内。
  • 第二步就是要判断移动后,是否会和其他棋子重叠造成冲突,方法是如果棋子移动后任何一部分在原来棋盘数组中的值既不是’0’(原来这里为空,没有任何棋子),也不是这枚棋子自己的值,就会发生冲突,如图5

这段代码可以表示如下:

bool Klotski::canMove(const Block& block, const Point& delta) const{

for(int i=0; i<block.size().height(); ++i)

for(int j=0; j<block.size().width(); ++j)

{

int x = block.topLeft().x + j + delta.x;

int y = block.topLeft().y + i + delta.y;

if( x<0 || x>=COL || y<0 || y>=ROW)

return false;

if(map[y][x] !='0' && map[y][x] !=block.value())

return false;

}

return true;

}

5、判断移动棋子是否和其他的棋子冲突

一旦判断棋子可以移动,就可以先更改棋子的左上角座标,然后在更新棋盘数组来表示这个移动的动作了,如下:

const Klotski& Klotski::moveBlock(const Block& block,

const Point& delta){

Block& ref = blocks[block.value()];

clearMap(ref);

ref.topLeft()+=delta;

updateMap(ref);

return *this;

}

算法

模型建立完毕 后,就可以在此基础上进一步考虑算法。在《交换青蛙》一文中,作者曾经给出了一个深度优先搜索算法。一般教科书上,也告知读者,对于只要求找到解,而不要 求在最少步数内找到解的问题,可以使用深度优先算法。但是在华容道问题中,如果因为仅仅希望找到解,而不是最优解而使用深度优先算法,就会陷入困难之中。 深度优先算法会根据某个合理的移动步骤一直尝试下去,直到找到解,如果在尝试中不幸钻入了死胡同,就会利用回溯倒退回去,再尝试其他步骤。

华容道问题的一大难点就是错误的尝试都很难钻入死胡同中,或者说需要很长时间才能钻入死胡同中。任何情况下,程序都需要针对10个棋子中的每个棋子都进行一次尝试,针对每个棋子的尝试都要判断其在上下左右4个方向能否移动。假设平均下来,每次有3个棋子能够移动,每个棋子平均可以在2个方向上移动。也就是说,平均每步有6种可能。那么当走10步后,就共有610次方,也就是6466176种移动方法。面对这么大的变化范围,深入优先算法就会沿着某个尝试一直深入下去。并且由于比较难钻进死胡同,深度优先算法可能在经过了相当长时间的尝试后仍然尚未找到解。

采用深度优先的第二个问题是递归深度的问题。如果为了直观采用《交换青蛙》一文中提到的递归算法,那么递归深度是受到一定限制的。例如传说中“横刀立马”的最优解是81步,深度优先算法的尝试步骤通常会超过81步,也就是递归深度超过81。某些系统下这个深度会超过最大递归深度的限制。作者中学时在8086上使用的BASIC系统的递归深度只有7。为此,必须采用消除递归的深度优先算法,将栈上的手工内容放到堆上,这样就失去了原来的直观简单的特点。

为此,本文将采用另外一种搜索策略——广度优先[7]来解决华容道问题。如果有读者没有听说过“广度优先”这个名词也没有关系。因为解决华容道问题的思想是朴素而直观的。考虑下面的示意图:

6、寻找“华容道”问题解的过程

在这个图中,首先得到的是“横刀立马”的起始布局,标记为1,从这个起始布局出发,一共有4种可能的移动方案,分别是6号兵向右,7号兵向下,8号兵向下和9号兵向左。至此,就得到了从华容道玩具“横刀立马”布局开始,走一步后的所有可能,把它们分别标记为2345。可以发现:不可能在走一步后就把曹操移动出来。所以接下来需要检查能否在走两步后把曹操移动出来。为此依次拿出2345这些布局,并针对每个布局找出继续前进1步后的所有可能布局。至此就得到了从开始出发,移动两步后的所有可能方案,把它们标记为6789……。检查它们看看是否有已经把曹操移动出来的情况。如果没有,就可以得出结论:不可能在两步以内移动出曹操。然后仿照上面的步骤,尝试是否有可能在三步以内移动出曹操,四步以内,五步以内……。

从上面的图和 相应的叙述可以发现一些有趣的规律。寻找解的过程会产生一棵树状的图。树是上下颠倒的,树根在最上面。“横刀立马”的起始布局就是树根。观察图中的序号可 以发现,这些序号标示出了在寻找解的过程中,是按照什么样的顺序,检查这棵树的:每次总是先将这棵树中同一层中的所有情况都检查完后,再统一检查下一层。 也就是先在水平方向的宽度上查找,在向垂直方向上的深度上查找。这就是“宽度优先”名字的含义。

实现宽度优先算法,可以按照上面的叙述,利用树状的数据结构来实现。但是相对于树形复杂的结构,有一种非常好的简化方法——就是利用队列Queue来概括上面的过程。如下图:

7、广度优先搜索的队列简化

其中绿色代表第2步的布局,红色代表第3步的布局。

如图所示,每次操作都在队列的头部(上侧)取出一个布局,检查曹操是否已经走出来,如果没有就根据其产生所有可能的布局,并把这些新布局加入队列的尾部(下侧)。然后重复这一过程。这样就能保证总是优先检查同一步数下的布局。

具体思路如下:

  1. 对于任何华容道棋盘中棋子的某个状态,首先判断曹操是否已经到达出口,如果已到达,则程序结束。
  2. 否则,找出当前布局中所有可移动的棋子,将其在上下左右各个方向上尝试移动1步。产生一个新布局。
  3. 判断新布局是否在以前出现过,如果以前出现过,表示已经尝试过此布局,可以将其忽略。
  4. 利用第23步骤,把根据当前布局继续移动一步的所有可能方案找出来,放到一个候选列表(队列)的尾部。
  5. 从这个候选列表(队列)的头部取出一个布局执行第1步。若候选列表为空则表示无解。

这里对候选列 表为空的情况略微解释一下。根据任意布局继续移动棋子一步,产生新布局时,有可能产生失败。例如所有的新布局以前都已经尝试过了,再例如错误的走法陷入了 死胡同。这时就没有新节点添加到队列的尾部。而寻找解的搜索过程会不断从队列的头部拿走候选布局。这样队列中的内容就会不断减少。当队列变成空时,表明所 搜过程已经测试了所有可能的布局而仍然没有找到结果。这说明起始布局无解。

算法实现

根据前面的叙述,算法可以大致实现为如下伪代码:

class KlotskiSolver{

public:

bool run(const Klotski& layout){

steps.push_back(new layout);

while(!steps.empty()){

Klotski step = steps.front();

if(step.isSolved()){

打印输出;

return true;

}

else{

steps.pop_front();

std::list<Klotski> nextLayouts = step.move();

foreach(it in nextLayouts){

if(不重复)

steps.push_back(*it);

}

}

}

return false;

}

private:

Queue steps;

};

这个伪代码产生了2个新问题:

  • 如何打印输出?
  • 如何判断一个新产生布局没有重复(以前曾经走过这样的布局)?

本着先易后难的原则,首先着手解决第一个问题,如何打印输出。当从队列中取出一个节点,比如第i个节点,检查后发现,曹操已经走出来了。这时就可以打印输出从起始布局到曹操走出的过程。为此必须直到第i个节点是从那个布局经过移动一步产生的,也就是必须直到i节点的父节点是谁。比如说是j节点。为此要继续找到j节点的父节点k,……,重复这个过程一直到找到最终的父节点,也就是根节点,华容道的起始布局“横刀立马”。

根据这个分析可以直到,队列中的任何节点,必须要知道自己的父节点是谁。为此直接将前面定义的Klotski放到队列中是不够的,为此可以使用一个反向链表来定义一个每次移动的步骤,如下:

template<class T> class Step{

public:

const T& value() const { return _value; }

const Step* prev() const { return _prev; }

private:

Step* _prev;

T _value;

};

这个Step是一个类模板,除了用于解决华容道问题,也可用作他用。在华容道问题中,每个Step都记录了其先前的一步prev和该Step对应的Klotski。为此修改KlotskiSolver如下:

class KlotskiSolver{

public:

typedef Step<Klotski> KlotskiStep;

typedef std::deque<KlotskiStep*> StepQueue;

bool run(const Klotski& layout){

steps.push_back(new KlotskiStep(layout));

while(!steps.empty()){

KlotskiStep* step = steps.front();

if(step->value().isSolved()){

printSteps(step);

return true;

}

else{

//..

}

}

return false;

}

private:

StepQueue steps;

};

有了链表来表示华容道的移动步骤,打印程序就可以很方便的实现了。打印程序接受移动步骤的最后一步,然后打印出从第一步到最后一步的变化过程。下面是一个递归的直观实现:

int KlotskiSolver::printSteps(const Step<Klotski>* step){

if(!step->prev()){

std::cout<<"=============step:[0]==============\n";

step->value().print();

return 0;

}

else{

int i=1+printSteps(step->prev());

std::cout<<"=============step:["<<i<<"]==============\n";

step->value().print();

return i;

}

};

Klotskiprint函数为:

void Klotski::print() const{

for(int y=0; y<ROW; ++y){

for(int x=0; x<COL; ++x)

std::cout<<map[y][x]<<" ";

std::cout<<"\n";

}

}

解决重复尝试造成的问题

在《交换青蛙》一文中,作者已经解释了为什么要消除重复尝试的原因。华容道问题中重复尝试的影响更加明显。重复尝试会极大地让尝试过程的树发散,消耗掉内存和时间。

华容道问题中,还必须仔细考虑一下“重复”棋局的含义。也棋局x和棋局y重复的定义是什么?如果xy都是Klotski的对象,能否简单地用x==y来判断xy是重复的?考虑下面4个棋局:

1 x x 2 3 x x 2 5 x x 1 1 x x 2

1 x x 2 3 x x 2 5 x x 1 1 x x 2

3 4 4 5 1 4 4 5 2 4 4 3 3 4 4 5

3 7 8 5 1 7 8 5 2 7 8 5 3 6 7 5

6 0 0 9 6 0 0 9 6 0 0 9 8 0 0 9

棋局1 棋局2 棋局3 棋局4

表面上看,这4个棋局像是不同的。可是仔细看看就会发现,如果从棋局1出发,经过一系列移动,得到了棋局2。不但没有让曹操移动一步,反而得到了一个极为类似的布局。这些移动几乎是做了无用功。再进一步观察,可以发现这4个布局中都有类似的问题。在搜索解的过程中,可以认为这4个布局,本质上就是1个布局,以避免多余的尝试。

那么这4个布局的特点是什么呢?深入考虑就可以得出这样的结论,判断布局相同与否,不能用棋盘上同一位置棋子代表的人物相同与否来判断,也就是说不能用棋子的值来判断。而要用棋子的形状来判断。例如,采用棋子的宽度x高度这个指标(也就是在Block中定义的棋子的size成员),用这个指标判断的话,张飞、赵云、黄忠、马超是等价的,4个士兵也是等价的。比如上面布局都可以用棋子的形状归纳为下面同一个布局:

(1x2) (4x4) (4x4) (1x2)

(1x2) (4x4) (4x4) (1x2)

(1x2) (2x1) (2x1) (1x2)

(1x2) (1x1) (1x1) (1x1)

(1x1) 0 0 (1x1)

采用了这个标准,就能够节省大量的多余尝试。下面再进一步观察下图的两个布局:

(1x2) (1x1) (4x4) (4x4) (4x4) (4x4) (1x1) (1x2)

(1x2) 0 (4x4) (4x4) (4x4) (4x4) 0 (1x2)

(1x2) 0 (2x1) (2x1) (2x1) (2x1) 0 (1x2)

(1x2) (1x2) (1x1) (1x2) (1x2) (1x1) (1x2) (1x2)

(1x1) (1x2) (1x1) (1x2) (1x2) (1x1) (1x2) (1x1)

布局1 布局2

可以发现,这两个布局是完全镜像对称的。如果能够从布局1找到解,就一定也能够从布局2找到解,因为华容道玩具本身就是左右对称的。换言之,如果从布局1出发,经过一系列移动得到了布局2,也可以认为是做了无用功。上面结论可以通过下面的不太严格的证明加以说明。假设华容道游戏的某个解可以叙述为这样的形式:

Block(i1).move(j1) ==> Block(i2).move(j2) ==> ... ==> Block(in).momve(jn)

其中,i1, i2, ... in表示某一步移动哪个棋子,而j1,j2, ... jn的取值范围是{, , , }。由于棋盘对称,如果将上述解中所有向左移动的步骤改为向右,将凡是向右移动的步骤改为向左,上下移动的保持不变。就可以得到一个新的解。

综上所述,在判断两个棋局是否重复时,必须使用下面两个条件:

  1. 使用棋子的形状而不是棋子代表的人物(值)来进行比较;
  2. 在比较棋局形状是否相同后,还要比较棋局是否是镜像相同。

针对第1条,可以在Klotski类中再添加一个表示形状的成员变量,然后在更新棋盘时,也同时更新棋盘形状。如下:

class Klotski{

//..

private:

char map[ROW][COL];

Size layoutMap[ROW][COL];

std::map<char, Block> blocks;

};

然后修改updateMapclearMap如下:

void Klotski::clearMap(){

for(int y=0; y<ROW; ++y)

for(int x=0; x<COL; ++x){

map[y][x]='0';

layoutMap[y][x]=Size(0,0);

}

}

void Klotski::clearMap(const Block& block){

for(int i=0; i<block.size().height(); ++i)

for(int j=0; j<block.size().width(); ++j){

map[block.topLeft().y+i][block.topLeft().x+j] = '0';

layoutMap[block.topLeft().y+i][block.topLeft().x+j]

= Size(0, 0);

}

}

void Klotski::updateMap(const Block& block){

for(int i=0; i<block.size().height(); ++i)

for(int j=0; j<block.size().width(); ++j){

map[block.topLeft().y+i][block.topLeft().x+j]

= block.value();

layoutMap[block.topLeft().y+i][block.topLeft().x+j]

= block.size();

}

}

针对第2条,需要为Klotski添加两个判断函数,一个判断layoutMap是否相同,一个判断layoutMap的镜像是否相同,下面是笔者给出的两个实现:

bool Klotski::isSameLayout(const Klotski& ref) const{

for(int y=0; y<ROW; ++y)

for(int x=0; x<COL; ++x)

if(layoutMap[y][x]!=ref.layoutMap[y][x])

return false;

return true;

}

bool Klotski::isMirrorLayout(const Klotski& ref) const{

for(int y=0; y<ROW; ++y)

for(int x=0; x<COL; ++x)

if(layoutMap[y][x]!=ref.layoutMap[y][COL-1-x])

return false;

return true;

}

使用上述比较工具,就可以考虑在核心算法中加入取出重复尝试的部分。为此必须保持一个已经尝试过布局的记录。这样就不能仅仅使用前面KlotskiSolver中的队列,在每次从队列头部取出一个棋局后也不能丢弃它,必须将其保存在某个历史记录中,以后每次尝试时,都去这个历史记录中比较,看看是否和以前尝试过的某个布局重复。

仅仅采取这样的措施还会忽略一部分棋局,这些棋局就是还在队列中等待检查,尚未取出存入历史记录的棋局。因此在尝试时,不仅要在历史记录中检查,还要在队列中检查。首先要在KlotskiSolver中加入一个历史记录:

class KlotskiSolver{

public:

typedef Step<Klotski> KlotskiStep;

typedef std::deque<KlotskiStep*> StepQueue;

typedef std::list<KlotskiStep*> StepList;

//..

private:

StepQueue steps;

StepList tried;

};

然后在核心算法中加入这些检查:

bool KlotskiSolver::run(const Klotski& layout){

steps.push_back(new KlotskiStep(layout));

while(!steps.empty()){

KlotskiStep* step = steps.front();

if(step->value().isSolved()){

printSteps(step);

return true;

}

else{

steps.pop_front();

tried.push_back(step);

std::list<Klotski> nextLayouts

= step->value().move(tried);

for(std::list<Klotski>::iterator it=nextLayouts.begin();

it!=nextLayouts.end(); ++it)

{

if(!KlotskiStep::findStep(steps, *it))

steps.push_back(new KlotskiStep(step, *it));

}

}

}

return false;

}

用黑体字表示的是代码的改动。其中在move(tried)中检查历史记录中是否有重复,在后面的for循环中,检查是否在队列中有重复。为此需要进一步增加一个Klotski::move函数。

template<class Container>

std::list<Klotski> Klotski::move(const Container& tried) const{

std::list<Klotski> res;

// left, right, up, down

const int dx[4] = {-1, 1, 0, 0 };

const int dy[4] = { 0, 0, -1, 1 };

for(std::map<char, Block>::const_iterator it = blocks.begin();

it!=blocks.end(); ++it)

{

for(int i=0; i<4; ++i){

Point delta(dx[i], dy[i]);

if(canMove(it->second, delta)){

Klotski newLayout(*this);

newLayout.moveBlock(it->second, delta);

if(!Step<Klotski>::findStep(tried, newLayout))

res.push_back(newLayout);

}

}

}

return res;

}

该函数接受一个棋盘布局和一个存有棋盘布局的历史记录容器,然后它依次尝试每个棋子,检查它可否在上下左右四个方向上移动。如果能够移动,程序就产生一个移动后的新布局,并检查它在历史记录中是否存在。如果不存在,则该新布局就作为一个候选方案被放入结果中。

该函数和上面的核心算法函数run都留下了一个待解决的问题:findStep,也就是在一个布局容器中寻找某重复布局。但是这里不能简单地利用std::find,原因有二:

  1. 布局容器中保存的不是Klotski,而是Step<Klotski>指针,直接对指针进行比较没有意义;
  2. Klotskioperator==运算符,不进行上面讨论过的镜像布局比较;

为此,作者在Step<>中增加了一个findStep方法,利用std::find_if来查找重复布局:

template<class StepPtrContainer>

static bool findStep(StepPtrContainer coll, const T& value){

struct TestEqual{

TestEqual(const T& x):ref(x){}

bool operator() (const Step* p) const{

return p->value().isSameLayout(ref) ||

p->value().isMirrorLayout(ref);

}

const T& ref;

};

return std::find_if(coll.begin(), coll.end(),

TestEqual(value))!=coll.end();

}

该示例代码在函数内部定义了一个内部类TestEqual,这种写法并非所有编译器都支持。具体讨论可以参见《交换青蛙》中兼容性一节。TestEqual是一个仿函数(或曰函数对象),其接受一个Step指针,然后会利用Klotski中定义的isSameLayoutisMirrorLayout来判断布局是否相同。函数的主题则利用std::find_if遍历历史记录来查找符合TestEqual的重复布局是否存在。

结果

前面的各个部分分别讨论了利用计算机解决华容道问题的几个主要方面。关于一些实现细节读者可以参考附录中的全部源代码。最后,为了揭示典型布局“横刀立马”的解,可以使用下面的测试代码:

Klotski createLayout(){

std::cout<<"=============[Heng Dao Li Ma]===========\n";

Klotski game;

game.addBlock(Block::ZhangFei);

game.addBlock(Block::CaoCao);

game.addBlock(Block::ZhaoYun);

game.addBlock(Block::MaChao);

game.addBlock(Block::GuanYu);

game.addBlock(Block::HuangZhong);

game.addBlock(Block::Solder1);

game.addBlock(Block::Solder2);

game.addBlock(Block::Solder3);

game.addBlock(Block::Solder4);

return game;

}

int main(int argc, char* argv[]){

KlotskiSolver solver;

solver.run(createLayout());

}

经过数分钟,程序输出“横刀立马”的最优解是:116步。这和传统的说法81步有些出入,仔细观察华容道的结果(该结果可以参见附录),可以发现存在下面的情况:

=============step:[21]==============

1 x x 2

1 x x 2

7 4 4 0

3 9 5 0

3 6 5 8

=============step:[22]==============

1 x x 0

1 x x 2

7 4 4 2

3 9 5 0

3 6 5 8

=============step:[23]==============

1 x x 0

1 x x 0

7 4 4 2

3 9 5 2

3 6 5 8

本来可以将棋子2一下子向下移动2格(这在81步解法中是允许的,并且算1步),但是该解法却分成2步,每次移动一格。因此这116步的解法,确切说是每次移动棋子1格情况下的最优解法。

本文给出了一种华容道的典型解法——深度优先搜索法。实现中尝试使用了现代C++的某些特点和OO的一些帮助。该算法不是解决华容道的最佳算法。但是至少能够让儿童时代曾经在华容道玩具上感到挫折的人知道,那并不说明孩子笨,而是这个难题的确超出了孩子的能力。

参考文献:

[1] WikiPedia, Klotski. http://en.wikipedia.org/wiki/Klotski

[2] WikiPedia, 华容道. http://zh.wikipedia.org/w/index.php?title=%E8%8F%AF%E5%AE%B9%E9%81%93&variant=zh-cn

[3] WikiPedia, 箱入り娘. http://ja.wikipedia.org/wiki/%E7%AE%B1%E5%85%A5%E3%82%8A%E5%A8%98

[4] 作者未查清, 《闯过华容道》. http://mathserver.sdu.edu.cn/html/sxjm/examples/ex5.htm

同济大学数学建模协会会刊,第6

[5] 魏仲良、林顺喜, 《利用电脑探讨中国古代益智游戏『华容道』之解法》. http://www2.kuas.edu.tw/prof/cjh/2003puzzle/subject/08.htm

国立台湾师范大学,资讯教育系

[6] Joshua Bloch. Effective Java Programming Language Guide (Paperback). Addison-Wesley Professional; 1st edition (June 5, 2001)

[7] WikiPedia, Bread-first search. http://en.wikipedia.org/wiki/Breadth-first_search

附录


[English][上一篇][目录][主页][联系我们: liuxinyu95@gmail.com]

ċ
Xinyu LIU,
Apr 9, 2012, 1:51 AM
ċ
klotski.h
(11k)
Xinyu LIU,
Apr 9, 2012, 1:51 AM
Comments