怎么样判断一个八数码问题有解还是无解啊?

利用奇偶性判断所给出的初始状态有无解.

判别方法是：

以数组为一维的举例子.

将八数码的一个结点表示成一个数组a[9]，空格用0表示，设临时函数p(x)定义为：x数所在位置前面的数比x小的数的个数，

其中0空格不算在之内，那设目标状态为b[9]，那r=sigma(p(x)) sigma()表示取所有的x:1-8并求和，

那对于初始状态a[9]，t=sigma(p(x))，如果r和t同为奇数或者同为偶数，那么该状态有解，否则无解。

考虑到四种移动方法对sigma(p(x))的影响，左移和右移是不会影响它的值的，

更不会影响奇偶性，如果是上移或者下移就会影响：

上移:一次上移会使一个元素向前跳两个数字的位置，设这两个数字为a1,a2，

不妨设a1a2，移的这个数字设为a0，那无非只有以下三次情况：

1，a0a1a2，考虑它们三者的p(x)值，p(a0)不变，p(a1)++，p(a2)++，总体增加了2

2，a1a0a2，p(a0)--,p(a1)不变,p(a2)++，总体不变

3，a1a2a0，p(a0)-=2,p(a1),p(a2)不变，总体减小了2

综合起来的结论就是不会影响sigma(p(x))的奇偶性。

八数码问题的问题，有解条件以及求解算法(宽度优先搜索)

八数码问题：

取一个 3*3 的矩阵，将1-8(或者任意从小到大的八个数字)，随机分布在矩阵中，留下一个空格(可以用0代替)，作为初始状态；再去一个3*3的矩阵，将1-8(或者任意从小到大的八个数字，其取值必须与初始状态相同)，随机分布在矩阵中，留下一个空格(可以用0代替)，作为目标状态；对初始状态进行操作，其允许的操作是：将空格向上，下，左，右移动(即将空格与周边的数字进行交换)，操作初始状态的矩阵，在若干步后达目标状态。求解其过程为八数码问题。如图：

八数码问题的有解条件：

将矩阵从上到下从左到右的顺序分布成一个数列，并去掉空格，例如：

2 8 3 (0为空格) 分布成数列后：

1 0 4     2 8 3 1 4 7 6 5

7 6 5

如果此 初始状态的数列(矩阵) 的 逆序数 与 目标状态的数列(矩阵) 的 逆序数 的 奇偶性一样 ，则此问题有解。

逆序数 的定义：

有一个数列，在这个数列中任意取一对数字(两个数字)，其两个数字在数列中的(从前到后)顺序与数字数值的大小相反，称其为一个逆序。这个数列中所有的逆序的和为逆序数。

证明 ：

空格向左右移动时，不改变逆序数的大小；空格向上下移动时，会改变逆序数，改变的幅度为±2或者0 (1)。所以±2或者0的改变幅度不会对逆序数造成奇偶性的改变。所以如果两个矩阵状态如果能互相到达，则必须有其逆序数的奇偶性一样。

(1) 在矩阵中操作空格上下移动时，在数列中的表现是将被交换的数字提前到他前面两个数字之前或者推后到他后面两个数字之后；例如，被交换的数字的下标是 Z 的话，空格向下移动(即被交换数向上移动)后，被交换数在数列中的位置是 Z-2 ；空格向上移动(即被交换数向下移动)后，则被交换数在数列中的位置是 Z+2。这种交换不会影响到被交换数与被它跨过的两个数以外的数字的顺序。比如说：被交换数的位置 Z ，如果空格向上移动，被交换数位置变成 Z+2，但是Z-1处的数字 与 Z 的顺序没有因为 Z 变成 Z+2 而失去了Z-1 在 Z 的前面的顺序，Z-1在Z前面，也在Z+2前面，同样的，Z变成Z+2也不会改变Z与Z+3的顺序。并且，如果有顺序 2 3 4 ，这个顺序的逆序数为0，如果我把4放到2 3前面，变成4 2 3，其逆序数就变成了+2，逆序数就增长了2；如果有顺序 4 2 3，其逆序数为+2，如果我把4放到2 3后面，变成2 3 4，其逆序数就变成了0，逆序数减少了2；如果有6 4 5，其逆序数为+2，如果我把5放在6 4 的前面，变成5 6 4，其逆序数为2，逆序数改变为0。所以改变的幅度为±2，或者0。

八数码问题的解法以及算法(宽度优先)：

解法：

空格可以上下左右移动，则父状态可以衍生出若干个子状态(考虑其空格不能越3*3的界以及其不返回到父状态或者父父状态等等之类的情况的话，***的子状态数量为4 最小为0)，这种思路的话实际上这个问题就是一个树的搜索问题，所以用搜索的算法可以解决。

算法(宽度优先)：

(1)判断初始状态与目标状态的逆序数的奇偶性来判断是否有解

(2)建立一个OPEN表(队列)，用于存放待展开子节点(状态)的父节点

(3)建立一个CLOSED表(队列)，用于存放已经展开了子节点的父节点

(4)将初始状态放到OPEN表中，作为***个

(5)将OPEN表中***个节点取出(并在OPEN表中删除这个节点)，放到CLOSED表中，排在CLOSED表中最后一个，整理好OPEN表

(6)把CLOSED表最后一个节点按照条件(不越界，不返回到父节点)展开其子节点，并且将可能的子节点按照顺序存入OPEN表中

(7)判断此父节点是否为目标状态：

 ①是，退出，打印答案

 ②不是，回到步骤(4)

问题：

(1)如果不用数字，而是用毫无关系的符号来填充矩阵，怎么判断是否有解呢？

想法：将初始状态作为参考，将其不同的符号的顺序作为其符号的值的大小，计算出初始状态的逆序数为0，按照初始状态的值大小来判断目标状态的逆序数，然后判断奇偶性进而判断是否有解。

八数码问题，逆序数判定是否有解，需要考虑0吗？

求逆序数的时候不要算0的。如果算上零的逆序数，对换之后奇偶性可能改变。

八数码问题的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于请用A*算法求解下图所示的八数码问题、八数码问题的信息别忘了在本站进行查找喔。