如何判断数字华容道中随机排列的数字阵列是否有解

很多数字华容道游戏程序，用随机函数使NxN数字阵列中的数字随机排列。数学家已证明，在数字随机排列的数字阵列中，半数随机排列不能通过移动数字，使数字按顺序排列，称为“无解排列”。博文“看最强大脑的数字华容道，尝试理解与总结”一文介绍了一种能找到这些“无解排列”方法，使游戏程序可删除这些“无解排列”。该文网址如下：https://blog.csdn.net/lsblsb/article/details/89226970。具体判据如下： 数字阵列中每个数的逆序数之和加上空白方格行号和列号，称为数字阵列总逆序数。数字阵列总逆序数可为偶数或奇数。数字阵列A通过移动数字方格变成数字阵列B的充要条件是：数字阵列A和数字阵列B两者的总逆序数同为奇数或偶数。这是前边博文给出的定理，但进行了改写，意思相同。没给出证明，认为其正确。 这里数字阵列行列号从0开始，例如3x3数字华容道，行列数都为：0，1，2。在计算逆序数时，空白方格也要参加运算，认为是0。计算数字阵列中某数的逆序数方法是：找到某数前面比该数大的数为k个，某数的逆序数就是k。例如数字阵列：2 4 3 1，2前面没有数，逆序数是0；4前面是2没有它大，逆序数是0；3前面有1个比它大的4，是1；1前面有3个比它大的分别是2 4 3 ，是3。所以 2 4 3 1 逆序数之和为：0+0+1+3=4，为偶数。 NxN数字阵列中的数字如已按顺序排列，空白方格在右下角，则该数字阵列的所有非0数字的逆序数都为0，右下角空白方格也要参加逆序计算，其值为0，其前边所有数都比0大，其逆序数为(NxN-1),右下角空白方格的行数和列数相同，相加必为偶数。因此如果N为奇数，总逆序数是偶数，如果N为偶数，总逆序数是奇数。因此数字随机排列的数字矩阵，如其行列数为奇数，数字阵列总逆序数为偶数，如其行列数为偶数，数字阵列总逆序数为奇数，才能有解，即通过移动数字方格，使数字矩阵按顺序排列。这是数字华容道游戏判断有无解的判据。例如3x3数字阵列已按顺序排列,即为：1 2 3 4 5 6 7 8 0，1前边无数字，其逆序数=0；2比1大，2的逆序数为0，…,0比前边的数字都小，其逆序数为8，逆序数和=0+0+0+0+0+0+0+0+8=8，为偶数，0在2行2列，其和=4，为偶数，总逆序数为偶数，因此3x3数字阵列随机排列的总逆序数必须为偶数，才有解。 该判据也可描述为：数字华容道NxN数字随机排列的阵列有解的充要条件是：N为奇数，总逆序数为偶数，N为偶数，总逆序数为奇数。 下边用实际4x4方格矩阵进一步来说明用法，初始排列如图： 其数字排列：3 1 7 2 11 8 15 10 5 9 0 6 13 12 14 4。注意空位为0。逆序数计算得到是：45，计算过程是：0+1+0+2+0+1+0+2+5+3+10+6+1+2+1+11。其总逆序数为(45) + 2(0的行号) + 2(0的列号)=奇数，能通过移动数字，使数字按顺序排列。自己也用3x3数字华容道验证了多次，判据都是正确的。 有了判断数字华容道是否有解的判据，用程序就就很容易删除无解的随机排列。用随机函数生成一个随机排列数字，如判断无解，再重新生成一个随机排列，直到找到一个有解的随机排列。由于所有随机排列中，有解和无解的随机排列各占一半，即出现有解概率为1/2，通过几次循环就能找到有解的排列。 网上有一种找有解数字排列的方法，先将阵列数字按顺序排列，空在右下角，然后随机移动带数字的方块到空处，随机移动若干步，将移动后的排列提供给玩家。这的确能保证有解。但每次要移动多少步，才能看起来是随机的，能不能保证所有有解的排列能够随机出现。实现这些还是有些问题的。 上边提到的那篇文章还指出，这些“无解排列”，通过移动数字，能做到只有最后两个数顺序不正确，例如3x3数字华容道无解，第1，2行数字按顺序排列，最后一行数据是：8、7，空，称为“镜像解”。是否也可以变通一下，认为“镜像解”也算玩家完成任务。