算法-24数码问题求解算法

Question

情景：5*5阶的二维拼图游戏，将一方形图片分割成24个方块外加一个空格，打乱后按规则经过有限次移动后还原成原图，每次移动，只可能是空格相邻的上下左右方块移动到空格处。
问题转换：0~24个数字按5*5排列成5阶矩阵，其中“0”在最后一排最后一列的位置上(表示空格)，如图所示：

现将他们按游戏规则进行打乱（即保证打乱后的排列的逆序数与原排列的逆序数一致方可解），现在是想通过一定算法，求解出任意一组解，达到还原矩阵到上边的目标状态，当然能是最优解更佳。
下面是打乱后的一个例子：

问题追加：忘记说明一个重要的限制了，就是要控制时间成本，即要在限时2分钟内找出一组可行解(暂不要求最优解)。

Answer 1

BFS 宽度优先搜索
我以前用这个算法做过3*3的 这个是用来求最优解的 但是空间耗费较大。
另一种叫做 ＤＦＳ深度优先搜索　　类似于回溯　空间占用较小
但是如果不进行适当的剪枝　时间耗费就会较大　而且不一定是最优解
不过两分钟的话　时间上应该还是可以满足的。