[中文][English][日本語

Klotski puzzle

200611

1、“插板”玩具

2、“华容道”玩具

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

## 建模

### 静态模型

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

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

class Block{

public:

//..

private:

Point _topLeft;

Size _size;

char _value;

};

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;

// ..

};

//

// "横刀立马"

//

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');

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

class Klotski{

public:

static const int COL=4;

static const int ROW=5;

private:

char map[ROW][COL];

std::map<char, Block> blocks;

};

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也有两个版本，一个将某个棋子所在的位置对应的棋盘数组中的值设置为该棋子所代表的值，另一个将全部棋盘中的值根据所有的棋子都更新一遍。

### 动态模型

blocks[block.value()] = block;

updateMap(block);

}

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;

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

• 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;

}

## 算法

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

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

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;

};

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

template<class T> class Step{

public:

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

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

private:

Step* _prev;

T _value;

};

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";

}

}

## 解决重复尝试造成的问题

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

(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)

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

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

class Klotski{

//..

private:

char map[ROW][COL];

Size layoutMap[ROW][COL];

std::map<char, Block> blocks;

};

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();

}

}

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;

}

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;

}

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;

}

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

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();

}

## 结果

Klotski createLayout(){

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

Klotski game;

return game;

}

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

KlotskiSolver solver;

solver.run(createLayout());

}

=============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

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

[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

[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)

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

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