其典型算法是广度优先搜索，具体算法是：struct 类名 m_ar[可能结点数];int h,rmain(){ h=0;r=1; while ((h<r)&&(r<可能结点数)) { if (判断每一种可能性，如果某一种操作符合要求) { 将m_ar[h]操作后记录于m_ar[r]; 如果和目标一样，输出结果并中止程序; r=r+1; } h=h+1; } 表示没有结果。}
***********************************是否可解的判断我知道什么样的情况有解,什么情况没解.函数f(s)表示s前比s小的数字的数目.例如:|1 3 4||2 8 6||5 7 |表示成:|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4,f(6)=4,f(8)=4,f(2)=1,f(4)=2,f(3)=1,f(1)=0当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成所以嘛,上面那个有解的.下面我就来证明一下.
设任意一种情况:|a1 a2 a3||a4 a5 a6||a7 a8 X | (X表示空格)
将之放在一行上: |a1 a2 a3|a4 a5 a6|a7 a8 X |数字的上下移动可以相对于是空格的上下移动.所以我们只要讨论X的移动了:
假设函数f(s)表示s前比s小的数字的数目.例如:|1 3 4|2 8 6|5 7 X| 则f(7)=6, f(5)=4, f(8)=4,……
对于X在同一行中的移动，f(a8)+f(a7)+……+f(a1)大小不变(*1)如：|a1 a2 a3|a4 a5 a6|a7 a8 X |=>|a1 a2 a3|a4 a5 a6|a7 X a8|
对于X在列中移动是，我们不妨设X与a6对换(即a6下移一格)则数列变为|a1 a2 a3|a4 a5 X|a7 a8 a6|,可能引起变化的f(s)只有f(a6),f(a7),f(a8)讨论：有4种情况1) a6<a7, a6<a8f(a8) 减小1 f(a7) 减小1 f(a6) 不变所以f(a8)+f(a7)+……+f(a1)奇偶性不变.2) a6<a7, a6>a8f(a8) 不变 f(a7) 减小1 f(a6) 增大1所以f(a8)+f(a7)+……+f(a1)奇偶性不变.3) a6>a7, a6>a8f(a8) 不变 f(a7) 不变 f(a6) 增大2所以f(a8)+f(a7)+……+f(a1)奇偶性不变.3) a6>a7, a6<a8f(a8) 减小1 f(a7) 不变 f(a6) 增大1所以f(a8)+f(a7)+……+f(a1)奇偶性不变.
这样，再将a3下移一格则|a1 a2 a3|a4 a5 X|a7 a8 a6|=>|a1 a2 X|a4 a5 a3|a7 a8 a6|则同样，对可能变化的f(a3),f(a4),f(a5)讨论，情况一上面完全一样。
其它情况都如此:如：|a1 X a3|a4 a5 a6|a7 a8 a2|=>|a1 a5 a3|a4 X a6|a7 a8 a2|就f(a3),f(a4),f(a5)变化.
结论：因为对于|1 2 3|4 5 6| 7 8 X|, f(8)+f(7)+……+f(1)=28, 是偶数，所以当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成|1 2 3|4 5 6| 7 8 X|成功.
