写在前面：
中秋假期，孤单一人，码码字，学学习，也挺好的。
本篇文章是对于 八数码是否有解的问题及其推广 进行一个讨论，借鉴了网上的几篇文章。如有错误，还望大佬指出。
八数码有解问题：
首先我们需要了解一下逆序数，因为八数码的有解问题与逆序数有关。
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个 逆序 。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中 所有逆序总数 叫做这个排列的 逆序数 。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。
逆序数为 偶数 的排列称为 偶排列；逆序数为 奇数 的排列称为奇排列。如 2431中，21，43，41，31是逆序，逆序数是4，为偶排列。
——参考：《百度百科：逆序数》
对于3*3的八数码问题：
- 当我们左右移动 空白格时，逆序数不变。
- 当我们上下移动 空白格时，相当于将一个数字X向前（向后）移动2格（3-1=2），那么跳过的这两个数，要么比数字X都要大（小），逆序数可能±2；要么一个比数字X大，一个比数字X小，逆序数不变（+1和-1正好抵消）。
通过上述的分析，我们发现，如果可以移动空白格（上下或者左右移动），那么空白格移动前后的逆序数奇偶性保持不变（相同）。
也就是说，对于八数码问题，如果两个状态的逆序数奇偶性相同，那么这两个状态可以相互到达，否则不能相互到达。因此，如果初始状态和目标状态的逆序数奇偶性不同，则该八数码问题无解，反之有解。
推广——从 3*3 到 N*N
上面是对3*3的棋盘进行分析，那么对于N*N的棋盘，有解的条件又是什么呢？
我们先看一下4*4的棋盘：
- 左右移动空白格，逆序数不变。
- 上下移动空白格，相当于将一个数字X向前（向后）移动3格（4-1=3），也就是这个数字X跳过了另外的三个格子，逆序数可能±3或者±1，逆序数的奇偶性必然发生改变。
可以看出，4*4棋盘的左右移动和上下移动，逆序数的奇偶性可能发生改变，而不像3*3棋盘那样。因此，我们还需要有另外的条件。
下面先给出结论，再举例进行验证。
对于N*N的棋盘，我们称空格位置所在的行到目标空格所在的行步数为空格的距离（不计左右距离），也就是空白格上下移动了多少次 。
- 当N为奇数 时，与八数码问题相同。
- 当N为偶数 时，空格每上下移动一次，奇偶性改变。若两个状态的可相互到达（有解），则有，两个状态的逆序奇偶性相同且空格距离为偶数，或者，逆序奇偶性不同且空格距离为奇数数。否则不能。
- 也就是说，当两个状态（状态1和状态2）可相互到达，需要满足表达式：（状态1的逆序数 + 空格距离）的奇偶性 == 状态2的奇偶性 。
同时：无论N是奇数还是偶数，空格上下移动，相当于跨过N-1个格子。那么逆序的改变可能为一下值±N-1，±N-3，±N-5 …… ±N-2k-1。当N为奇数数时N-1为偶数，逆序改变可能为0；当N为偶数时N-1为奇数，逆序的改变不能为0，只能是奇数，所以没上下移动一次奇偶性必然改变。
无解
有解
推广——从N*N 到 M*N（POJ 2893）
这里直接说结论吧。
真正需要讨论的是空白格上下移动的情况 ，而上下移动影响的只是 列数-1 个数字。所以，其实起作用的是 棋盘的列数 ，当棋盘的列数为奇数时，依据 3*3 棋盘的结论即可；当棋盘的列数为偶数时，依据4*4 棋盘的结论即可。
也就是说，不管是 N*N 棋盘 还是 M*N 棋盘 ，其实，只有列数N 需要讨论。
更多内容，可以看一下博客：poj 2893 M × N Puzzle (由逆序对求解8数码问题的推广)
推广——从 N*N 到 N*N*N（ZOJ：Commedia dell'arte）
其实，三维的结论和二维的结论是一样的。
考虑左右移动空格，逆序不变；同一层上下移动空格，跨过个格子；上下层移动空格，跨过
个格子。
- 当 N 为奇数时，
和
均为偶数，也就是任意移动空格 逆序奇偶性不变 。那么逆序奇偶性相同的两个状态 可相互到达 。
- 当 N 为偶数时，
方向的距离之和，称为 空格距离。若空格距离为偶数，两个逆序奇偶性相同的状态可相互到达；若空格距离为奇数，两个逆序奇偶性不同的状态可相互到达。
也就是说，当式子（空格距离 +初始状态逆序数）的奇偶性 == （目标状态逆序数）的奇偶性 成立时，两个状态可相互到达。
写在最后：
参考资料：
- 博客：八数码问题 BFS+A* 到N数码问题（代码来源）
- 博客：八数码问题有解的条件及其推广（文字来源）
- 博客：八数码问题及A*算法
看似简单的八数码，实则有趣而神奇。不仅了解到了BFS、双向BFS、启发式搜索A 这几种搜索策略，而且知晓了八数码的有解问题 ，以及八数码的推广 。
关于逆序数的求法，有好几种方法，网上也有很多文章有介绍。目前我还没太明白，就先不写出来了。如果有大佬好心，也可以在评论区指点一波。
学无止境，一点也不假。多思多学，不断拓宽，不断充实。
网友评论