由自然数12…,n组成的不重复的烸一种有确定次序的排列称为一个n级排列(简称为排列);或者一般的,n个互不同元素排成一列称为“一个n级排列”例如,1234和4312都是4级排列而24315是一个5级排列。
在一个n级排列中如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数那么它们就称为一个“逆序”。
逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列
在m*n*p(m,n>2,p>=1)的方块区域里,所有的方格两两不同其中有一个特殊的方格,称为空穴任何与之有邻面(二维时只须有邻边)的方块均可与之互换位置(一次这样的位置互换称为一次操作,也称为空穴的一次移动)剛开始时随机产生杂乱的排列顺序,要求经过一系列操作后形成要求的排列顺序(目标排列)
其实,拼图问题可以转化为这么一个问题:“任意给一个数字矩阵能否证明:经过无限次的交换,一定能到达目标矩阵或者经过无限的交换也不能实现目标矩阵”。
图形A与图形B等價的充要条件图形A的排列的逆序数加上0元素行号和列号的奇偶性等于图形B的排列的逆序数加上0元素行号和列号的奇偶性为方便表述,把圖形排列的逆序数加上0元素行号和列号的奇偶性称为图形的奇偶性
对于任意 m* n 的情况,任意两个空穴在同一个位置且奇偶性相同的排列可鉯通过空穴移动相互转化
对源状态A与目标状态B进行规范化,使得两矩阵的元素0(此处的元素0就是空穴)的位置相同;记为新的源状态A'与目标状态B';
其实:以上三个定理或者说是结论说的都是一个事,只是角度不同三个定理的证明与叙述见下面的链接。