华容道游戏解法图,华容道经典版游戏

这是《算法的乐趣》读书笔记。 在JavaScript(es6 )中重新实现算法。

华容道游戏看似简单，但求解需要设计的数据结构却很复杂，还涉及棋类游戏的棋局判断，整个过程很辛苦。 我尽量用面向对象的思想封装。 把整个过程分成几个部分记录下来。 今天是第一部分，数据结构的定义和初始化。 华容道游戏介绍华容道游戏来源于三国故事《虚拟香水为华容，关云长为ggdbg》。 在54的棋盘上安排多名蜀国大将和军士作为棋子，将ggdbg包围在中间，滑动各棋子，帮助ggdbg移动到出口位置逃跑。

算法原理——华容道的数学原理还不清楚，没有数学方法能一举解决这一点。 因此，我们只能用计算机网罗所有可能的解，找到最佳解。

代码和构想棋局包括棋盘状态和棋子状态两部分，我们用计算机对棋局进行进化和探索。 对于一个方面，如果有移动一个或多个ggdxf的方法，这个方面可以演化为一个或多个新的方面，每个新的方面可以通过移动ggdxf的方法演化为更多的方面。

常量定义const MAX_WARRIOR_TYPE=5； //光栅被ggdxf占据的状态，空或ggdxf编号，1 4const HRD_GAME_ROW=5； //柜的实际行数const HRD_GAME_COL=4； //柜的实际列数const HRD_BOARD_WIDTH=6； //柜定义宽度const HRD_BOARD_HEIGHT=7； //柜定义高度const BOARD_CELL_EMPTY=0； //网格空闲码const BOARD_CELL_BORDER=-1； //哨兵代码const DIRECTION=[ [0，-1]，[ 1，0 ]，[ 0，1 ]//移动方向定义移动操作定义classmoveaction { constructor (hero idid diridx (this.hero idx=hero idx||0/} } ggDXF编号this.diridx||0//移动方向) gg DXF类型定义const warrior _ type={ ht //1x2 HT_HBAR : 3，//2x1 HT_BOX : 4 //2x2} ggdxf定义classWarrior{constructor(type，top ) ) this.type=type/type 棋盘上各点为零表示天空，数字表示ggdxf的号码。

classhrdgamestate { constructor (} { this.board=[ ]//盘for ) letI=0； iHRD_BOARD_HEIGHT； I ) )//盘初始化，哨兵this.board.push([]for(letj=0； jHRD_BOARD_WIDTH； j ) this.board[I].push([] ) if (I==0||j==0||I==HRD _ board _ height-1|| j==HRD _ board ) //进化树的“父亲”this.step=0； //进化计数this.move=new MoveAction (

//演化方式（ggdxf移动方式） this.heroes = [] //ggdxf列表 } initState(heroes){ //ggdxf列表初始化 for(let i = 0; i < heroes.length; i++) { if(!addGameStateHero(this, i, heroes[i])) //将ggdxf放置到棋盘上 { return false; } } return true; }} ggdxf放置函数 function addGameStateHero(gameState, heroIdx, hero){ if(isPositionAvailable(gameState, hero.type, hero.left, hero.top)) //检测给定位置是否能放置该ggdxf { takePosition(gameState, heroIdx, hero.type, hero.left, hero.top); //放置ggdxf到棋盘上 gameState.heroes.push(hero); //将ggdxf存入列表中 return true; } return false;} 检测能否放置ggdxf函数 function isPositionAvailable(gameState, type, left, top){ let isOK = false; switch(type) { case WARRIOR_TYPE.HT_BLOCK: isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY); break; case WARRIOR_TYPE.HT_VBAR: isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY) && (gameState.board[top + 2][left + 1] == BOARD_CELL_EMPTY); break; case WARRIOR_TYPE.HT_HBAR: isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY) && (gameState.board[top + 1][left + 2] == BOARD_CELL_EMPTY); break; case WARRIOR_TYPE.HT_BOX: isOK = (gameState.board[top + 1][left + 1] == BOARD_CELL_EMPTY) && (gameState.board[top + 1][left + 2] == BOARD_CELL_EMPTY) && (gameState.board[top + 2][left + 1] == BOARD_CELL_EMPTY) && (gameState.board[top + 2][left + 2] == BOARD_CELL_EMPTY); break; default: isOK = false; break; } return isOK;} 放置ggdxf函数 function takePosition(gameState, heroIdx, type, left, top){ switch(type) { case WARRIOR_TYPE.HT_BLOCK: gameState.board[top + 1][left + 1] = heroIdx + 1; break; case WARRIOR_TYPE.HT_VBAR: gameState.board[top + 1][left + 1] = heroIdx + 1; gameState.board[top + 2][left + 1] = heroIdx + 1; break; case WARRIOR_TYPE.HT_HBAR: gameState.board[top + 1][left + 1] = heroIdx + 1; gameState.board[top + 1][left + 2] = heroIdx + 1; break; case WARRIOR_TYPE.HT_BOX: gameState.board[top + 1][left + 1] = heroIdx + 1; gameState.board[top + 1][left + 2] = heroIdx + 1; gameState.board[top + 2][left + 1] = heroIdx + 1; gameState.board[top + 2][left + 2] = heroIdx + 1; break; default: break; }} 棋局对象测试

测试代码

var hs = [new Warrior(WARRIOR_TYPE.HT_VBAR,0,0), //构建ggdxf列表，初始棋局 new Warrior(WARRIOR_TYPE.HT_BOX,1,0), new Warrior(WARRIOR_TYPE.HT_VBAR,3,0), new Warrior(WARRIOR_TYPE.HT_VBAR,0,2), new Warrior(WARRIOR_TYPE.HT_HBAR,1,2), new Warrior(WARRIOR_TYPE.HT_VBAR,3,2), new Warrior(WARRIOR_TYPE.HT_BLOCK,0,4), new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3), new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3), new Warrior(WARRIOR_TYPE.HT_BLOCK,3,4)]var gameState = new HrdGameState() //新建棋局对象gameState.initState(hs) //初始化棋局，往空棋盘上摆开局console.dir(gameState.board) //输出棋局 测试结果

结果符合预期

[ [ -1, -1, -1, -1, -1, -1 ], [ -1, 1, 2, 2, 3, -1 ], [ -1, 1, 2, 2, 3, -1 ], [ -1, 4, 5, 5, 6, -1 ], [ -1, 4, 8, 9, 6, -1 ], [ -1, 7, 0, 0, 10, -1 ], [ -1, -1, -1, -1, -1, -1 ] ] 完整代码

代码托管在开源中国，其中的hyd.js即华容道解法。

https://gitee.com/zhoutk/test 小结

尽量使用面向对象的思想来解决问题，让数据和操作绑定在一起，努力使代码容易看懂。