棋子可以跳过那
f枚棋子到空位置上。问：最少经过多少步，可以将棋盘状态变成
○○○○●●●分析：1、用2
1位三进制数表示状态，如初始状态为：222201111，目标状态为111102222。转化为十进制进行存储，另记录空格位置。2、产生式规则：将棋子移动转化为空格的移动。（1）空格向左移动（2）空格向右移动（3）空格向左跳动（4）空格向右跳动3、用一个132
1的哈希数组判重。例三：八数码问题。在一个３×３的九宫中有１－８这８个数及一个空格随机的摆放在其中的格子里，如图１所示。现在要求实现这个问题：将该九宫格调整为如图2所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。
1876234514725836
●
图一图二分析：1、字符串表达状态，另开一变量w记录空格位置。2、空格移动规则：（1）向下移动：w’w3。（2）向上移动：w’w3。（3）向左移动：w’w1。（4）向右移动：w’w1。3、用穷举法判重。（将来可以用排序二叉树判重）123深度优先搜索（dfs）深度优先搜索是从根结点出发，沿着树的深度遍历树的结点。如果当前新产生的结点还有以此为根的下一层结点，则沿此路继续下去，直到无法再深入访问时，回朔到上一层的结点，选另一条路继续深入访问。反复此过程，直到所有结点都被访问到为止。
算法过程：
f1、首先将根结点放入栈中。2、取出栈顶结点，按照产生式规则生成新的结点数据，每产生一个：检查是否是目标结点，如果是且比保存的数据更优，刷新所保存的数据。检查该结点是否已搜过，如果是且比已保存的数据更优，则刷新所保存的数据，然后该结点进栈；如没有搜过，则保存数据并进栈。3、转第二步。4、如果栈空，则算法结束。细化说明：1、一般用回朔法，利用递归使用系统栈。2、哈希数组不仅用于判断新结点是否出现过，还用于保存到达该结点时的中间数据。算法框架：proceduredfs结点数据varii
tegerbegi
fori产生式规则一to最大产生式规则dobegi
新结点数据creatiif新结点数据没有搜到过or新结点数据虽已搜过但本次搜索结果更优the
begi
更新新结点搜索结果dfs新结点数据e
de
d
proceduredfs结点数据varilo
gi
tbegi
fori1to最大产生式规则dobegi
新结点creatiif新结点是目标结点the
begi
传回新结点ttrueexite
dif新结点更优the

fbegi
更新新结点数据dfs新结点iftthe
exite
de
de
d空间复杂度：O最大状态数（主要用于r