如图这样的拼图游戏，应该都玩过吧，最终要还原到按顺序排列的状态。

Question

还有个问题是判断局面是否有解，随机生成的局面不一定能还原，但我觉得自动解题搞得定的话这个应该也一并解决掉了。

Answer 1

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

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

更大的矩阵就慢了。

Answer 2

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