【讨论】xsokoban共90题

jinyou

我知道的都贴出来了，请大家帮我补充吧。
懂外文的朋友也帮着找找吧。
谢谢！请回贴。

最小步数统计
前50关
http://sokobano.de/results/table.php?set=original
后40关
http://sokobano.de/results/table.php?set=extra

他们应该知道答案，可惜不分享给我。

[ 本帖最后由 jinyou 于 2009-7-23 12:56 编辑 ]

juventus66

真厉害,一口气发了九十一帖,不过我看不懂

｛獨｝

同意楼上的，我也看不懂
嘿嘿

kaylmu

一不小心就本周热闷了...

sdicky

看不懂啊。。。。。。

kexin_xiao

"搬运工"是一个十分流行的单人智力游戏，玩家的任务是在一个仓库中操纵一个搬运工人,将N个相同的箱子推到N个相同的目的地。
一   状态空间搜索基本知识   
  1.状态空间(state   space)   
  对于一个实际的问题，我们可以把它进行一定的抽象。通俗的说，状态(state)是对问题在   
  某一时刻的进展情况的数学描述，状态转移(state-transition)就是问题从一种状态转移   
  到另一种（或几种）状态的操作。如果只有一个智能体(Agent)可以实施这种状态转移，则   
  我们的目的是单一的，也就是从确定的起始状态(start   state)经过一系列状态转移而到达   
  一个（或多个）目标状态(goal   state)。   
  如果不止一个智能体可以操纵状态转移(例如下棋)，那么它们可能会朝不同的，甚至是对   
  立的目标进行状态转移。这样的题目不在本文讨论范围之内。   
  我们知道，搜索的过程实际是在遍历一个隐式图，它的结点是所有的状态，有向边对应于   
  状态转移。一个可行解就是一条从起始结点出发到目标状态集中任意一个结点的路径。这   
  个图称为状态空间(state   space)，这样的搜索就是状态空间搜索(Single-Agent   Search)   
  2.盲目搜索(Uninformed   Search)   
  盲目搜索主要包括以下几种：   
  纯随机搜索(Random   Generation   and   Random   Walk)   
  听起来比较"傻"，但是当深度很大，可行解比较多，解的深度又不重要的时候还是有用的   
  ，而且改进后的随机搜索可以对付解分布比较有规律（相对密集或平均，或按黄金分割比   
  例分布等）的题目。一个典型的例子是：你在慌乱中找东西的时候，往往都是进行随机搜   
  索。   
  广度优先搜索(BFS)和深度优先搜索(DFS)   
  大家都很熟悉它们的时间效率，空间效率和特点了吧。广度优先搜索的例子是你的眼镜掉   
  在地上以后，你趴在地板上找：）-   你总是先摸最接近你的地方，如果没有，在摸远一点   
  的地方…深度优先搜索的典型例子是走迷宫。它们还有逆向和双向的搜索方式，但是不再   
  本文讨论范围之内。   
  重复式搜索   
  这些搜索通过对搜索树扩展式做一些限制，用逐步放宽条件的方式进行重复搜索。这些方   
  法包括：   
  重复式深度优先(Iterative   Deepening)   
  限制搜索树的最大深度Dmax,然后进行搜索。如果没有解就加大Dmax再搜索。虽然这样进行   
  了很多重复工作，但是因为搜索的工作量与深度成指数关系，因此上一次（重复的）工作   
  量比起当前的搜索量来是比较小的。这种方法适合搜索树总的来说又宽又深，但是可行解   
  却不是很深的题目（一般的深度优先可能陷入很深的又没有解的地方，广度优先的话空间   
  又不够）   
  重复式广度优先(Iterative   Broadening)   
  它限制的是从一个结点扩展出来的子节点的最大值Bmax,但是因为优点不是很明显，应用并   
  不多，研究得也比较少。   
  柱型搜索(Beam   Search)   
  它限制的是每层搜索树节点总数的最大值Wmax。显然这样搜索树大小与深度成正比，但是   
  可能错过很接近起点的解，而增加Wmax的时候保留哪些节点，Wmax增加多少是当前正在研   
  究的问题。   
  3.启发式搜索(Informed   Search)   
  我们觉得一些问题很有"想头"，主要是因为启发信息比较多，思考起来容易入手，但是却   
  不容易找到解。我们不愿意手工一个一个盲目的试验，同样也不愿意我们的程序机械的搜   
  索。也就是说，我们希望尽可能的挖掘题目自身的特点，让搜索智能化。下面介绍的启发   
  式搜索就是这样的一种智能化搜索方法。   
  在刚才的那些算法中，我们没有利用状态本身的信息，只是利用了状态转移来进行搜索。   
  事实上，我们自己在解决问题的时候常常会估计状态离目标到底有多接近，进而对多种方   
  案进行选择。把这种方法用到搜索中来，我们可以用一个状态的估价函数来估计它到目标   
  状态的距离。这个估价函数是和问题息息相关的，体现了一定的智能。为了以后叙述方便   
  ，我们先介绍一些记号：   
  S   问题的任何一种状态   
  H*(s)   s到目标的实际（最短）距离   -   可惜事先不知道：）   
  H(s)   s的启发函数   -   s到目标距离的下界，也就是h(s)<=h*(s),如果h函数对任意状态s1和   
  s2,还满足h(s1)<=h(s2)+c(s1,s2)（其中c(s1,s2)代表状态s1转移到s2的代价）,也就是状   
  态转移时，下界h的减少值最多等于状态转移的实际代价，我们说h函数是相容(consisten   
  t)的。(其实就是要求h不能减少得太快)   
  G(s)   到达s状态之前的代价，一般就采用s在搜索树中的深度。   
  F(s)   s的估价函数，也就是到达目标的总代价的估计。直观上，应该   
  有f(s)=g(s)+h(s)，即已经付出的和将要付出的代价之和。如果g   
  是相容的，对于s1和它的后辈节点，有h(s1)<=h(s2)+c(s1,s2)   
  两边同时加上g(s1),有h(s1)+g(s1)<=h(s2)+g(s1)+c(s1,s2),也就是   
  f(s1)<=f(s2)。因此f函数单调递增。   
  表1       启发式搜索用到的符号   
  贪心搜索(Best-First   Search)   
  象广度优先搜索一样用一个队列储存待扩展，但是按照h函数值从小到大排序(其实就是优   
  先队列)。显然由于h估计的不精确性，贪心搜索不能保证得到的第一个解最优，而且可能   
  很久都找不到一个解。   
  A*算法   
  和贪心搜索很类似，不过是按照f函数值进行排序。但是这样会多出一个问题：新生成的状   
  态可能已经遇到过了的。为什么会这样呢？由于贪心搜索是按照h函数值排序，而h只与状   
  态有关，因此不会出现重复，而f值不仅状态有关，还与状态转移到s的方式有关，因此可   
  能出现同一个状态有不同的f值。解决方式也很简单，如果新状态s1与已经遇到的状态s2相   
  同，保留f值比较小的一个就可以了。(如果s2是待扩展结点，是有可能出现f(s2)>f(s1)的   
  情况的，只有已扩展结点才保证f值递增)。A*算法保证得到最优解，但是所用的空间是很   
  大的，难以适应我们的搬运工问题。   
  IDA*算法   
        既然A*算法存在空间问题，那么我们能不能借用深度优先搜索的空间优势，用重复式搜   
  索的方式来缓解危机呢？经过研究，Korf于1985年提出了一个Iternative   Deepening   A*(   
  IDA*)算法，比较好的解决了这一问题。一开始，我们把深度最大值Dmax设为起始结点的h   
  值，开始进行深度优先搜索，忽略所有f值大于Dmax的结点，减少了很多搜索量。如果没有   
  解，再加大Dmax的值，直到找到一个解。容易证明这个解一定是最优的。由于改成了深度   
  优先的方式，与A*比较起来，IDA*更加实用：   
  1.   不需要判重，不需要排序，只用栈就可以了。操作简单。   
  2.   空间需求大大减少，与搜索树大小成对数关系。   
  其他的启发式搜索   
  这些方法包括深度优先+最优剪枝式的A*，双向A*,但是由于很不成熟或者用处并不大，这   
   
  里就不介绍了。A*算法有一个加权的形式，由于在搬运工问题中效果不明显，这里从略。

二   搬运工问题及其特点   
  在对状态空间搜索算法有一定了解之后，我们来看看我们的搬运工问题。究竟用什么方法   
  比较好呢？让我们先来看看该问题的特点。   
  1.   搬运工问题   
  我们在前面已经介绍过搬运工问题，这里我只是想提一些和解题有关的注意事项。首先，   
  我们考虑的搬运工问题的地图规模最大是20*20，这已经可以满足大部分关卡了。为了以后   
  讨论方便，我们把地图加以编号。从左往右各列称为A，B，C…，而从上往下各行叫a,b,c   
  …。而由于不推箱子时的走路并不重要，我们   
  在记录解的时候忽略了人的位置和移动，只记录箱子的移动。人的动作很容易根据箱子的   
  动作推出来。下面是包含解答的标准关卡第一关。   
   
  呵呵，怎么样，第一关都要那么多步啊…以后的各关，可是越来越难。   
  2.   搬运工问题的特点   
  我在前言里吹了这么半天，我想你即使以前没有玩，现在也已经玩过了吧：）。   
  有什么感觉呢？是不是变化太多了，不好把握？不仅人不好把握，连编程序也变得困难了   
  很多。我们不妨拿它与经典的8数码问题作一个比较。   
  1.死锁！   
  初学者很快就会学到什么是死锁   -   一旦他（她）把一个箱子推到角上。显然，这样的布局   
  再继续玩下去是没戏了，不管以后怎么推都不可能把这个箱子推离那个角。不少玩家都总   
  结了不少死锁的经验，但是要比较系统的解决这个问题并不是一件容易的事。我们将用整   
  整一章（其实也不长啦）的篇幅来分析这个问题。   
   
  典型的死锁。想一想，为什么：）我们再看一下8数码问题。它没有死锁，因为每一步都是   
  可逆的。在这一点上，搬运工问题要令人头疼得多了。   
  容易看出，这样的状态空间不是无向图，而是有向图。   
  2.状态空间。   
  8数码问题每次最多有4中移动方法，最多的步数也只有几十步。而搬运工问题呢？困难一   
  点的关卡可以是一步有100多种选择，整个解答包括600多次推箱子动作。分支因子和解答   
  树深度都这么大，状态空间自然就非同小可了。   
  3.下界估计   
  在启发式搜索中，我们需要计算h值，也就是需要对下界进行估计。8数码问题有很多不错   
  的下界函数（如"离家"距离和），但是搬运工问题又怎么样呢？我们不能直接计算"离家"   
  距离，因为谁的家是哪儿都不清楚。很自然，我们可以做一个二分图的最佳匹配，但是这   
  个下界怎么样呢？   
  a.准确性   
  对于A*及其变种来说，下界与实际代价越接近，一般来说算法效率就越高。我们这个最佳   
  匹配只是"理想情况"，但是事实上，在很多情况下箱子相互制约，不得已离开目标路线来   
  为其他箱子腾位置的事情是非常普遍的。例如我们的标准关卡第50关，有的箱子需要从目   
  标格子穿过并离开它来为其它箱子让路。我们的下界函数返回值是100，但是目前的最好结   
  果是370。多么大的差别！   
  b.效率   
  由于下界函数是一个调用非常频繁的函数，其效率不容忽视。最佳匹配的时间渐进复杂度   
  大约是O(N^3),比8数码的下界函数不知大了多少…我们将会在后面给出一些改进方法，但   
  是其本质不会改变。   
  3.   如何解决搬运工问题   
  已经有人证明了搬运工问题是NP-Hard，看来我们还是考虑搜索吧。回想一下上一节提到过   
  的状态空间搜索，用哪一种比较好呢？   
  既然是智力游戏，可用的启发式信息是非常丰富了，我们不仅是要用，而且要用得尽量充   
  分,所以应该用启发式搜索。而前面已经提到了，搬运工问题的状态空间是非常大的，A*是   
  没有办法了，因此我们选择了IDA*算法：实现简单，空间需求也少。   
  既然搬运工问题这么难，为什么有那么多人都解决了相当数量的关卡呢（标准的90N年以前   
  就被人们模透了）。因为人聪明嘛。他们会预测，会安排，会学习，有直觉的帮助，还有   
  一定的冒险精神。他们（也包括我啦，呵呵）常用的是一些"高层次"的解题策略，既有效   
  ，又灵活。(Srbga:想学吗?   Readers:当然想!!)可惜这些策略不是那么简单易学，也不是   
  很有规律的。在后面的章节中，我将尽力模仿人的思维方式给我们的程序加入尽量多的智   
  能。

kexin_xiao

三   用IDA*算法解搬运工问题   
  实现与改进   
  在上一节中，我们知道了IDA*算法是我们解决搬运工问题的核心算法。在这一节里，我们   
  将用IDA*算法来做一个解决搬运工问题的程序   -   虽然是我们的最初版本(我们称做S4-Bab   
  y)，但是不要小看它哦！   
  1   IDA*算法框架   
  由前所述，IDA*算法是基于重复式深度优先的A*算法，忽略所有f值大于深度限制的结点。   
  那么，我们不难写出IDA*算法框架的伪代码   
  伪代码1   -   IDA*算法框架   
  procedure   IDA_STAR(StartState)   
  begin   
      PathLimit   :=   H(   StartState   )   -   1;   
      Success   :=   False;   
  repeat   
  inc(PathLimit);   
  StartState.g:=   0;   
  Push(OpenStack,StartState);   
  repeat   
      CurrentState:=Pop(OpenStack);   
      If   Solution(CurrentState)   then   
          Success   =   True   
      Else   if   PathLimit   >=   CurrentState.g   +   H(CurrentState)   then   
          Foreach   Child(CurrentState)   do   
              Push(OpenStack,   Child(CurrentState));   
  until   Success   or   empty(OpenStack);   
  until   Success   or   ResourceLimitsReached;   
  end;   
  这只是一个很粗略的框架，什么事情都不能做。不过我想大家可能比较急于试验一下IDA*   
  的威力，因此我们不妨就做一个最最基本的程序。   
  2.   第一个程序   
  要从框架做一个程序需要填充一些东西。在这里我们就展开一些讨论。   
  输入输出文件格式   
  输入文件是一个文本文件，它由N行构成，每行是一些字符。   
  各种字符的含义是：   
  SPACE       空地   
  .               目标格子   
  $               箱子   
  *               目标格子中的箱子   
  @               搬运工   
  +               目标格子中的搬运工   
  #               墙   
  表2   输入文件格式   
  这种格式和Xsokoban,   SokoMind和Rolling   Stone的格式是一致的，因此会比较方便一些。   
  输出文件第一行是推箱子的次数M，以下M行，每行的格式是：x   y   direction,代表把第x行   
  第y列的箱子往direction的方向推一步。Direction可以是left,right,up,down之中的一个   
  ,1<=x,y<=20   
  数据结构   
  由于是最初的版本，我们不必考虑这么多：只需要可行，编程方便就可以了，暂时不管它   
  的效率和其他东西。优化是以后的事。   
  我们定义新的数据类型BitString,MazeType,MoveType,StateType和IDAType。请大家看附   
  录中的程序，不难猜出它们的含义和用途。唯一需要说明的BitString类型。记录状态时，   
  我们把地图看成一个大数，一个格子是一个bit。那么所有箱子构成一个BitString,检查某   
  一个是否有箱子（或者目标，墙）时只需要检测对应位置上的bit是否为1。这样虽然会浪   
  费一些空间，但是判断会比较快，操作也比较简单。   
  我们把x,y坐标合并成一个"position"变量。其中Position=(x-1)*width+(y-1)。   
  我们用常量数组DeltaPos:array[0..3]表示上，下，左，右的Position增量。   
  算法   
  为了简单起见，我们连最佳匹配也不做了，用所有箱子离最近目标的距离和作为下界函数   
  。不过，这里的"距离"是指推的次数，计算的时候（MinPush函数），只要忽略其它所有箱   
  子，然后用一次BFS就可以了。

kexin_xiao

5.结点扩展顺序的优化   
  在这一节中，我们的最后一个改进是优化结点扩展的顺序，不是想修剪搜索树，而是希望   
  早一点得到解。具体的改进方法是这样的：   
  1.优先推刚刚推过的箱子   
  2.然后试所有的能够减少下界的方案，减少得越多越先试。如果减少得一样多，就先推离   
  目标最近的。   
  3.最后试其他的，也象2一样按顺序考虑。   
  可以预料，这样处理以后，"比较容易"先找到解，但是因为下界估计不准所花费的代价是   
  无法减小的（也就是说只能减少顶层结点数）。不过作为IDA*的标准改进方法之一，我们   
  有必要把它加入我们的程序中试试。   
  (需要注意的是，我们使用的是栈，应该把比较差的方案先压栈)   
  实际测试结果，1的效果比较好，2和3的效果不佳，甚至产生了更多的结点。可能主要是我   
  们的下界估计不准确，而2和3用到了下界函数的缘故。这一个版本Baby-4中，我们屏蔽了   
  第2，3项措施。   
  好了，写了四个Baby版程序，想不想比较一下呢？不过我只对几个困难一点的数据感兴趣   
  。   
  关卡   实际步数   Baby-1   Baby-2   Baby-3   Baby-4   
  Kid   1   11   186476   60   52   38   
  Kid   16   7   3947   304   189   149   
  Kid   18   10   5108   46   41   31   
  Kid   35   16   11118   6504   704   462   
  Kid   50   11   14451   98   96   152   
  Kid   51   13   Too   many   Too   many   629   54   
  Kid   52   18   Too   many   Too   many   39841   97   
  Kid   54   16   24270   273   258   140   
  Kid   55   14   Too   many   Too   many   4886   3390   
  Kid   56   14   3318   2225   1518   1069   
  Kid   60   15   Too   many   Too   many   6916   5022   
  Wqx   4   26   97855   33923   33916   24251   
  Wqx   9   12   116927   4806   968   350   
  从上表可以看出，我们的优化总的来说是有效的，而且直观的看，那些改进不明显的很多   
  是因为下界估计比较差，这一点我们以后会继续讨论。不管怎样，这61关"幼儿关"过了58   
  关倒是挺不错的，至少可以说明我们程序的Baby版已经具有普通儿童的"智力"了^_^。不过   
  这只是个开头，好戏还在后头！

kexin_xiao

6.Baby-4源程序   
  程序S4BABY4.PAS在附件中，这里只是加了少量的注释。大家可以试试它的效果，但是没有   
  必要看得太仔细，因为在以后的章节中，我会改动很多东西，甚至连IDA*主程序框架都会   
  变得不一样。   
  常量定义：   
  const   
      {Version}   
      VerStr='S4   -   SRbGa   Super   Sokoban   Solver   (Baby   Version   4)';   
      Author='Written   by   Liu   Rujia(SrbGa),   2001.2,   Chongqing,   China';   
      {Files}   
      InFile='soko.in';   
      OutFile='soko.out';   
      {Charactors}   
      Char_Soko='@';   
      Char_SokoInTarget='+';   
      Char_Box='$';   
      Char_BoxInTarget='*';   
      Char_Target='.';   
      Char_Wall='#';   
      Char_Empty='   ';   
      {Dimentions}   
      Maxx=21;   
      Maxy=21;   
      MaxBox=50;   
      {Directions}   
      Up=0;   
      Down=1;   
      Left=2;   
      Right=3;   
      DirectionWords:array[0..3]   of   string=('UP','DOWN','LEFT','RIGHT');   
      {Movement}   
      MaxPosition:integer=Maxx*Maxy;   
      Opposite:array[0..3]   of   integer=(1,0,3,2);   
      DeltaPos:array[0..3]   of   integer=(-Maxy,Maxy,-1,1);   
  我们把x,y坐标合成一个值position，其中position=(x-1)*maxy+(y-1)。这里用类型常量   
  是因为以后会根据地图的尺寸改变MaxPosition的值。Opposite就是相反方向例如Opposit   
  e[UP]:=DOWN;DeltaPos也是会重新设定的。我们在进行移动的时候只需要用：NewPos:=Ol   
  dPos+DeltaPos[Direction]就可以了，很方便。   
      {IDA   Related}   
      MaxNode=1000000;   
      MaxDepth=100;   
      MaxStack=150;   
      DispNode=1000;   
  每生成多少个结点报告一次。   
      {HashTable}   
      MaxHashEntry=10000;   
      HashMask=10000;   
      MaxSubEntry=100;   
      {BitString}   
      BitMask:array[0..7]   of   byte=(1,2,4,8,16,32,64,128);   
      Infinite=Maxint;   
   
  类型定义：   
  type   
      PositionType=integer;   
      BitString=array[0..Maxx*Maxy   div   8-1]   of   byte;   
  整个地图就是一个BitString。第position位为1当且仅当position位置有东西（如箱子，   
  目标，墙）。   
      MapType=array[1..Maxx]   of   string[Maxy];   
      BiGraph=array[1..MaxBox,1..MaxBox]   of   integer;   
      MazeType=   
      record   
          X,Y:integer;   
          Map:MapType;   
          GoalPosition:array[1..MaxBox]   of   integer;   
          BoxCount:integer;   
          Goals:BitString;   
          Walls:BitString;   
      end;   
  尺寸，原始数据（用来显示状态的），目标的BitString，箱子总数，目标位置（BitStri   
  ng和位置数组都用是为了加快速度）和Walls的BitString。   
      MoveType=   
      record   
          Position:integer;   
          Direction:0..3;   
      end;   
  Direction是箱子被推向的方向。   
      StateType=   
      record   
          Boxes:BitString;   
          ManPositionositionType;   
          MoveCount:integer;   
          Move:array[1..MaxDepth]   of   MoveType;   
          g,h:integer;   
      end;   
      IDAType=   
      record   
          TopLevelNodeCount:longint;   
          NodeCount:longint;   
          StartState:StateType;   
          PathLimit:integer;   
          Top:integer;   
          Stack:array[1..MaxStack]   of   StateType;   
      end;   
  Top是栈顶指针。   
      PHashTableEntry=^HashTableEntry;   
      HashTableEntry=   
      record   
          NextHashTableEntry;   
          State:StateType;   
      end;   
      PHashTableType=^HashTableType;   
      HashTableType=   
      record   
          FirstEntry:array[0..MaxHashEntry]   of   PHashTableEntry;   
          Count:array[0..MaxHashEntry]   of   byte;   
      end;

kexin_xiao

这些是Hash表相关类型。我们采用的是拉链法，这样可以利用指针申请到堆空间，结合保   
  护模式使用，效果更好。   
  var   
      HashTableHashTableType;   
      SokoMaze:MazeType;   
      IDA:IDAType;   
  procedure   SetBit(var   BS:BitString;   p:integer);   
  begin   
      BS[p   div   8]:=BS[p   div   8]   or   BitMask[p   mod   8];   
  end;   
  procedure   ClearBit(var   BS:BitString;   p:integer);   
  begin   
      BS[p   div   8]:=BS[p   div   8]   xor   BitMask[p   mod   8];   
  end;   
  function   GetBit(var   BS:BitString;   p:integer):byte;   
  begin   
      if   BS[p   div   8]   and   BitMask[p   mod   8]>0   then   GetBit:=1   else   GetBit:=0;   
  end;   
  这些是位操作，设置，清除和得到一个BitString的某一项。   
  procedure   Init;   
  var   
      Lines:MapType;   
      procedure   ReadInputFile;   
      var   
          f:text;   
          s:string;   
      begin   
          SokoMaze.X:=0;   
          SokoMaze.Y:=0;   
          SokoMaze.BoxCount:=0;   
          assign(f,infile);   
          reset(f);   
          while   not   eof(f)   do   
          begin   
              readln(f,s);   
              if   length(s)>SokoMaze.Y   then   
                  SokoMaze.Y:=length(s);   
              inc(SokoMaze.X);   
              Lines[SokoMaze.X]:=s;   
          end;   
          close(f);   
      end;   
  procedure   AdjustData;   
      var   
          i,j:integer;   
      begin   
          for   i:=1   to   SokoMaze.X   do   
              while   length(Lines)<SokoMaze.Y   do   
                  Lines:=Lines+'   ';   
          SokoMaze.Map:=Lines;   
          for   i:=1   to   SokoMaze.X   do   
              for   j:=1   to   SokoMaze.Y   do   
                  if   SokoMaze.Map[i,j]   in   [Char_BoxInTarget,Char_SokoInTarget,Char_Targe   
  t]   then   
                      SokoMaze.Map[i,j]:=Char_Target   
                  else   if   SokoMaze.Map[i,j]<>Char_Wall   then   
                      SokoMaze.Map[i,j]:=Char_Empty;   
  调整Map数组，把箱子和搬运工去掉。   
          for   i:=1   to   SokoMaze.X   do   
              for   j:=1   to   SokoMaze.Y   do   
                  if   Lines[i,j]   in   [Char_Target,Char_BoxInTarget,Char_SokoInTarget]   then   
                  begin   
                      inc(SokoMaze.BoxCount);   
                      SokoMaze.GoalPosition[SokoMaze.BoxCount]:=(i-1)*SokoMaze.Y+j-1;   
                  end;   
  统计Goal的个数和GoalPosition。   
          DeltaPos[Up]:=-SokoMaze.Y;   
          DeltaPos[Down]:=SokoMaze.Y;   
          MaxPosition:=SokoMaze.X*SokoMaze.Y;   
  根据地图尺寸调整DeltaPos和MaxPosition   
      end;   
      procedure   ConstructMaze;   
      var   
          i,j:integer;   
      begin   
          fillchar(SokoMaze.Goals,sizeof(SokoMaze.Goals),0);   
          fillchar(SokoMaze.Walls,sizeof(SokoMaze.Walls),0);   
          for   i:=1   to   SokoMaze.X   do   
              for   j:=1   to   SokoMaze.Y   do   
                  case   Lines[i,j]   of   
                      Char_SokoInTarget,   Char_BoxInTarget,   Char_Target:   
                          SetBit(SokoMaze.Goals,(i-1)*SokoMaze.Y+j-1);   
                      Char_Wall:   
                          SetBit(SokoMaze.Walls,(i-1)*SokoMaze.Y+j-1);   
                  end;   
      end;   
      procedure   InitIDA;   
      var   
          i,j:integer;   
          StartState:StateType;   
      begin   
          IDA.NodeCount:=0;   
          IDA.TopLevelNodeCount:=0;   
          fillchar(StartState,sizeof(StartState),0);   
          for   i:=1   to   SokoMaze.X   do   
              for   j:=1   to   SokoMaze.Y   do   
                  case   Lines[i,j]   of   
                      Char_Soko,   Char_SokoInTarget:   
                          StartState.ManPosition:=(i-1)*SokoMaze.Y+j-1;   
                      Char_Box,   Char_BoxInTarget:   
                          SetBit(StartState.Boxes,(i-1)*SokoMaze.Y+j-1);   
                  end;   
          StartState.g:=0;   
          IDA.StartState:=StartState;   
          new(HashTable);   
          for   i:=1   to   MaxHashEntry   do   
          begin   
              HashTable^.FirstEntry:=nil;   
              HashTable^.Count:=0;   
          end;   
      end;   
  begin   
      ReadInputFile;   
      AdjustData;   
      ConstructMaze;   
      InitIDA;   
  end;   
  procedure   PrintState(State:StateType);   
  var   
      i,x,y:integer;   
      Map:MapType;   
  begin   
      Map:=SokoMaze.Map;   
      x:=State.ManPosition   div   SokoMaze.Y+1;   
      y:=State.ManPosition   mod   SokoMaze.Y+1;   
      if   Map[x,y]=Char_Target   then   
          Map[x,y]:=Char_SokoInTarget   
      else   
          Map[x,y]:=Char_Soko;   
      for   i:=1   to   MaxPosition   do   
          if   GetBit(State.Boxes,i)>0   th