对于一个n*m的拼图游戏我们将按照从左到右,从上到下的顺序给每个分格标注可得一个二维矩阵。以3*3为例标注结果如:
我们假设最大值为空白。即游戏时的样子是这樣的:
这里说下规律设两个矩阵A和B。将矩阵从左到右从上到下排成一个一维数组,设其逆序对的个数加上空白格在原矩阵所在的行列號之和P若P(A)与P(B)的奇偶性相同,则两个矩阵可以通过拼图游戏进行转换因此只要计算当前矩阵和正确矩阵的P值判断一下即可。
生成随机可解拼图游戏:
由于奇数+奇数=偶数奇数+偶数=奇数,偶数+偶数=偶数我们知道n+m的奇偶性,因此只要保证con的奇偶性即可
所以交换data[n*m-2]和data[n*m-3]会改变整個数据的逆序对个数的奇偶性。
因此只要根据随机生成的data适当交换data[n*m-2]和data[n*m-3]的位置即可。从这个规律也可以看出,随机的矩阵中只有一半是鈳解的。