前言

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不一样。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。

如何证明八数码问题无解

用一个一位数组取代二维的3*3棋盘，用0取代空白格，即
1 2 3 4 5 6 7 8 0
还可以写成
2 1 3 4 5 6 7 8 0
在上面两个例子中，第一个是有解的，第二个无解。

每个数字前面比它大的数字的个数的和称为这个状态的逆序数。
目前来看两个例子中，除去数字0之外的逆序数：
在第一个例子1 2 3 4 5 6 7 8 0中，它的逆序数为偶数（0个）；
在第二个例子2 1 3 4 5 6 7 8 0中，它的逆序数为奇数（1个）。

在棋盘中，每个数字只能横着或竖着和空格交换：
如果是横着交换，在一维数组中体现为0和数字的交换，逆序数不会产生变化；
如果是竖着交换，在一维数组中体现为0和选择的数字相隔两位数字的交换，逆序数会加2或减2，但是逆序数的奇偶不变。

所以不论怎么交换，一维数组中的逆序数的奇偶不变，所以第一个例子的情况不会转化为第二个例子的情况。

八数码的状态也会由于奇偶分为两部分，一部分有解，一部分无解。