本文分web版游戏的实现和启发式搜索算法两部分；

先看dome，直接鼠标点击要移动的方块开始游戏，点击 提示 开始最佳路径搜索（启发式）直到最后一步；

（如果提示无解，则表示没有找到最佳路点击重置重新试一次，可通过console查看全部搜索的每一步节点状态，或在js/main.js中打断点看每一步结果，详细内容见下文）

项目地址：https://github.com/pangyongsheng/puzzle

dome演示：http://pangyongsheng.github.io/puzzle/

 一、游戏的实现方法

　　首先我们考虑如何用数据表示拼图游戏的状态，即将拼图游戏视图与数据绑定；

　　如下图所示：

　　（1）以左上角为原点，建立坐标系，蓝色数字表示位置序号，

　　　　  则该位置div(拼图块）的left和right（向左和向下的偏移距离）等于为其左上角绿点的坐标(x,y)，即：

　　　　　　left    =  x * 小方块边长

　　　　　　right =   y* 小方块边长

　　（2）这样的话，我们就可以用一个长度为9数组表示当前拼图的状态空间，

　　　　  如 [2,0,1,5,4,6,7,8,3] 可表示 一号方块在2号位置，二号方块在0号位置...    如下图所示：

　　　　　　自此我们就实现了视图与数据的对应关系，把拼图问题转化成为一个数组排列组合问题；

　　（3）对于任意号位置a的坐标c我们可通过建立一个如下二维数组来获取，　

　　　　　　var place= [ 
[0, 0],[1, 0],[2, 0],

　　　　　　　　[0, 1],[1, 1],[2, 1],　　　

　　　　　　　　[0, 2],[1, 2],[2, 2]

　　　　　　]

　　　　位置序号与坐标则有如下关系

　　　　　　c=place[a]

　　　  由以上可知获取a坐标方法

　　　初始化每一个小方块位置方法（block为全部小方块dom,这里借用数组方法forEach遍历div）

　　　（4）对于任意两个坐标的距离我们可以表示为

　　　　　　d=| x1 - x2 | +  | y1-y2 |

　　　　　代码如下

 　　（5）那么我们可以求得当前状态和目标状态的全部距离为，（每个小方块距离目标的距离求和）,f(x)第x方块距离目标位置的距离

　　　　代码如下

 　　（6）如何判断点击的方块是否能移动，首先我们将最后一个方块隐藏，如果点击的方块距离最后（8号）方块距离为1则表示可以移动，及两个状态可以转化，

　　　　　这个方法也可以看做两个状态的数组能否相互转化，可作为后面启发式搜索判断节点扩展的方法；

　　　　以上代码为每个方块添加点击事件

 　　　　至此游戏的基本实现方式介绍完毕，详细看代码

 二、启发式搜索

　　启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 

它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n) 

　　简单的说就是扩展当前状态节点的所有可能下一步节点，通过一个方式来估算那个节点最快能到到目标，不断重复知道实现达到目标状态；

　　我们这里的估计方法为 当前状态的全部距离+走的步数；

　　搜索过程可能描述如下：