上周人工智能课上老师要求证明如下两个关于八数码问题的结论：
- 8数码问题的状态空间是两张独立的连通图;
- 8数码问题的状态可以划分为两个不相交的集合,每个集合中的状态经过任意多步移动操作都不能转化成另一个集合中的状态。
在结合一些资料进行思考后，我给出的详细证明如下。
如果发现不严谨或是逻辑错误还望留言指正。
证明：
设八数码的解集如下：(1)
1 2 3
4 5 6
7 8 n
其中n = 0（即不影响数码的逆序数(见附录1条目1））。
假设可看做从左到右从上至下排列的字符串：a[7]=1 2 3 4 5 6 7 8。
∴a[7]的逆序数 t = 0，即t为偶数;
∵八数码的位移规则为：空格上移，空格下移，空格左移，空格右移。
∵空格n为0
∴空格的左移和右移不会改变t的值，既不改变逆序数的奇偶性。 （2）
设移动的数码为a[i] = x;
当空格上移或下移时，在此假设上移，
∵上下两位数码相差2位
∴ a[7] = a[1] … x a[i+1]…a[8]
=> a[1]a[2] …a[i+1]a[i+2] x …a[8];
这一过程可以简单的看做x与a[i+1]和a[i+2]的简单交换，即只移动2次，
由附录1推论2、3可知，数列经过n次相邻数码交换后，若n为偶数则逆序数的奇偶性不变。 （3）
∴由（2）（3）可知，棋子在既定的规则中移动不会改变逆序数的奇偶性。
易知：8数码的解集是（1）中状态经过空格任意上移、下移、左移、右移后的所有状态的集合。
又∵空格的上移、下移、左移、右移并不会改变逆序数的奇偶性
∴当a[7]的逆序数t为偶数时，一定有解
又∵在有解状态下,t不可能为奇数
∴当a[7]的逆序数t为奇数时，一定无解
即8数码问题中每个集合中的状态经过任意多步移动操作都不能转化成另一个集合中的状态。
但是不能证明8数码问题的状态空间是两张独立的连通图或者8数码问题的状态可以划分为两个不相交的集合。
又∵八数码的所有可能性为9!，其中偶排列==奇排列
可证八数码问题的解共有9!/2=181440。
下面证明8数码问题的状态空间是两张独立的连通图
这里我参考了下面参考(3)提供的思路，但是参考(3)的最后的证明可能会有一些没有解释清楚的小问题。
下面给出我的证明：
要想证明8数码问题的状态空间是两张独立的连通图，只要证明8数码的奇排列和偶排列的内部分别可互达，即各个有解的状态可已经过若干步相互转换，无解的状态同样如此。
可知：
0 1 2 3 4 5 6 7 8 是八数码问题的一个有解情况，是偶排列；
0 2 1 3 4 5 6 7 8 是八数码问题的一个无解情况，是奇排列。
这两个数列是我从有解和无解情况中选出的特例，如果再有解情况下都可以转化为0 1 2 3 4 5 6 7 8，无解情况下都可以转化为0 2 1 3 4 5 6 7 8，那么即可证明8数码问题的状态空间是两张独立的连通图（数学归纳法）且连通图内部可互达。
x表示任意不同数字，为方便说明，所以用同一字母表示
a b c (L1)
0 x x (L2)
x x x (L3)
如果可以证明 a b c 0可以在第（L1）、（L2）层经过若干次移动使得每一位都能移动到a b c 0中的最后一位同时不影响其他数码的位置，即可利用递推的原理，证明每一层都可以经过若干步排列整齐，即可证明8数码问题的状态空间是两张独立的连通图，进而证明8数码问题的状态可以划分为两个不相交的集合。
再进一步考虑，只要a b c 0都可以移动到这四个位置的某一位，就可以的推论出上面的假设。
这里我们选择末尾，可以很清楚的看出来 a b c 0, 0 b c a,b 0 c a, b c 0 a, 0 c a b很容易在不影响其他数码的位置经过简单几步移动得到，要说明的是，b c 0 a ==> b c a 0是需要多几步才能得到（可能是我比较笨，开始的时候不知道怎么移动花了挺多时间才搞定，所以现在记下来便于理解）；
步骤如下(j,k ∈ Z，0 < j < 9, 0 < k < 9,且 j != k != a != b != c)：
a b c b c 0 c 0 k c a k c a 0 b c a
0 j k => a j k => b a j => b 0 j => b j k => 0 j k
x x x x x x x x x x x x x x x x x x
可以看到，在a b c 0移动至b c a 0的过程j k的位置同样没有发生改变，所以可证明在第一层可以在不影响其他数码位置的情况下经过若干步排列整齐。
通过递归，可以推论每一层都可以经过若干步排列整齐，即该问题的图是连通图，处处可达。
∴当a b c分别为1 2 3时，该排列是偶排列，有解；
当a b c分别为2 1 3时，该排列是奇排列，无解。
结合上面证毕的奇排列和偶排列相互不可达，可以得出结论：
8数码问题的状态可以划分为两个不相交的集合且状态空间是两张独立的连通图。
证毕。
附录1：概念解释及推论证明
1.逆序数：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。
2.如果交换任何两个相邻的棋子，那么棋子数列的逆序数将发生奇偶性互变（奇偶性互变是指由奇数变为偶数，或由偶数变为奇数）。
证明：假设交换的是a[i]和a[i+1]，那么对于a[j]（1≤j≤i-1或i+2≤j≤8）的逆序数并不改变。若交换之前 a[i]a[i+1]，那么交换之后，a[i]的逆序数不变，而a[i+1]的逆序数加1（因为a[i]成了它的一个逆序）；同理，若交换之前 a[i]>a[i+1]，那么交换之后，a[i]的逆序数减1，而c[i+1]的逆序数不变。所以上述推论成立。
3.如果棋子数列经过n次相邻棋子交换后，若n为偶数，则数列逆序数奇偶性不变；若n为奇数，则数列逆序数将发生奇偶性互变。其证明可以由推论2简单推出。
附录2：参考资料：
(1)百度百科，逆序数的概念：http://baike.baidu.com/link?url=0Wo8I_20Wz7hW8lgJlB--uzkNuis7HPuh-DbcGxYM7LBuwkpFVC9ZfZGnIESKo8kqwc_NhLKyrq2KBmnJoi4uK
(2)八数码问题的可解性讨论：http://bbs.chinaunix.net/thread-1281258-1-1.html
(3)再论八数码：http://blog.csdn.net/ju136/article/details/6876647