请教拼图游戏的自动解题算法思路

Question

如图这样的拼图游戏，应该都玩过吧，最终要还原到按顺序排列的状态。
还有个问题是判断局面是否有解，随机生成的局面不一定能还原，但我觉得自动解题搞得定的话这个应该也一并解决掉了。。。

Answer 1

经典的八数码问题，可以用
搜索+康托展开排重

当然学AI的时候这题是经典的Astar算法练习题

当然还可以双向广搜

注：是否有解，可以通过判断逆序数的奇偶判断

Answer 2

基本思路就是递归搜索，搜索时标记状态，如果某个状态已经reach 过，就 pass。时间、空间复杂度都是 N! （N 是拼图的格子数量）, 增长很快。

3*3 的矩阵也就 9! = 40320 种不同状态，搜索速度很快。

更大的矩阵就慢了。

Answer 3

不要完全随机的生成一个局面,而是从拼好的局面去打乱它生成新的局面.完全随机生成能还原的局面的概率很小.我觉得这个问题完全随机生成局面(n个格子的矩阵,内有n-1个元素)有解的概率是 n*(n-1)/n! = 1/(n-2)!

Answer 4

其实， 这个游戏根本都不要搜索，先不管游戏无解的情况。有一种很简单的解题方法：
按照1 - 8 的顺序一个一个移过去就行了

代码也很好写

Answer 5

我用c#winform写了这个AI算法， [rar文件] 拼图AI(c#源码八勺)
你可以去csdn下载
http://download.csdn.net/detail/bashao4/5656001