重排九宫：

启发式搜索：（利用全局择优搜索）

估价函数：f(x)=d(x)+h(x)

其中：d(x)表示节点的深度，h(x)=p(x)+s(x),p(x)表示节点x的棋局与目标节点棋局位置不相同的棋子数，s(x)表示节点x与目标节点位置不相同的棋子到达目标节点棋局位置的最短距离之和。

每次总是从OPEN表的全体节点中选择一个估价值最小的节点，其搜索过程如下：

（1） 把初始节点s0放入OPEN表，计算f（s0）

（2） 如果OPEN表为空，则搜索失败，退出

（3） 把OPEN表中的第一个节点（记为节点n）从表中移出放入CLOSED表

（4） 考察节点n是否为目标节点。若是，则求得了问题的解，退出

（5） 若节点n为不可扩展，则转到第二步

（6） 扩展节点n（空格进行先左，再上，再右，后下的顺序进行移动，进而得到节点n的扩展子节点）用估价函数f（x）计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都放入OPEN表中，然后对OPEN表中的全部节点按估价值从大小到大的顺序进行排序

（7） 转到第二步

例子：先给重排九宫分别设初始状态值和目标状态值（给八个格分别输入0—9中数字），然后根据以上的估计函数和启发函数以及步骤找出从初始状态到目标状态的最短路径

例如：初始状态： 目标状态：