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

很多数字华容道游戏程序&＃xff0c;用随机函数使NxN数字阵列中的数字随机排列。数学家已证明&＃xff0c;在数字随机排列的数字阵列中&＃xff0c;半数随机排列不能通过移动数字&＃xff0c;使数字按顺序排列&＃xff0c;称为“无解排列”。博文“看最强大脑的数字华容道&＃xff0c;尝试理解与总结”一文介绍了一种能找到这些“无解排列”方法&＃xff0c;使游戏程序可删除这些“无解排列”。该文网址如下&＃xff1a;https://blog.csdn.net/lsblsb/article/details/89226970。具体判据如下&＃xff1a;
数字阵列中每个数的逆序数之和加上空白方格行号和列号&＃xff0c;称为数字阵列总逆序数。数字阵列总逆序数可为偶数或奇数。数字阵列A通过移动数字方格变成数字阵列B的充要条件是&＃xff1a;数字阵列A和数字阵列B两者的总逆序数同为奇数或偶数。这是前边博文给出的定理&＃xff0c;但进行了改写&＃xff0c;意思相同。没给出证明&＃xff0c;认为其正确。
这里数字阵列行列号从0开始&＃xff0c;例如3x3数字华容道&＃xff0c;行列数都为&＃xff1a;0&＃xff0c;1&＃xff0c;2。在计算逆序数时&＃xff0c;空白方格也要参加运算&＃xff0c;认为是0。计算数字阵列中某数的逆序数方法是&＃xff1a;找到某数前面比该数大的数为k个&＃xff0c;某数的逆序数就是k。例如数字阵列&＃xff1a;2 4 3 1&＃xff0c;2前面没有数&＃xff0c;逆序数是0&＃xff1b;4前面是2没有它大&＃xff0c;逆序数是0&＃xff1b;3前面有1个比它大的4&＃xff0c;是1&＃xff1b;1前面有3个比它大的分别是2 4 3 &＃xff0c;是3。所以 2 4 3 1 逆序数之和为&＃xff1a;0&＃43;0&＃43;1&＃43;3&＃61;4&＃xff0c;为偶数。
NxN数字阵列中的数字如已按顺序排列&＃xff0c;空白方格在右下角&＃xff0c;则该数字阵列的所有非0数字的逆序数都为0&＃xff0c;右下角空白方格也要参加逆序计算&＃xff0c;其值为0&＃xff0c;其前边所有数都比0大&＃xff0c;其逆序数为(NxN-1),右下角空白方格的行数和列数相同&＃xff0c;相加必为偶数。因此如果N为奇数&＃xff0c;总逆序数是偶数&＃xff0c;如果N为偶数&＃xff0c;总逆序数是奇数。因此数字随机排列的数字矩阵&＃xff0c;如其行列数为奇数&＃xff0c;数字阵列总逆序数为偶数&＃xff0c;如其行列数为偶数&＃xff0c;数字阵列总逆序数为奇数&＃xff0c;才能有解&＃xff0c;即通过移动数字方格&＃xff0c;使数字矩阵按顺序排列。这是数字华容道游戏判断有无解的判据。例如3x3数字阵列已按顺序排列,即为&＃xff1a;1 2 3 4 5 6 7 8 0&＃xff0c;1前边无数字&＃xff0c;其逆序数&＃61;0&＃xff1b;2比1大&＃xff0c;2的逆序数为0&＃xff0c;…,0比前边的数字都小&＃xff0c;其逆序数为8&＃xff0c;逆序数和&＃61;0&＃43;0&＃43;0&＃43;0&＃43;0&＃43;0&＃43;0&＃43;0&＃43;8&＃61;8&＃xff0c;为偶数&＃xff0c;0在2行2列&＃xff0c;其和&＃61;4&＃xff0c;为偶数&＃xff0c;总逆序数为偶数&＃xff0c;因此3x3数字阵列随机排列的总逆序数必须为偶数&＃xff0c;才有解。
该判据也可描述为&＃xff1a;数字华容道NxN数字随机排列的阵列有解的充要条件是&＃xff1a;N为奇数&＃xff0c;总逆序数为偶数&＃xff0c;N为偶数&＃xff0c;总逆序数为奇数。
下边用实际4x4方格矩阵进一步来说明用法&＃xff0c;初始排列如图&＃xff1a;

其数字排列&＃xff1a;3 1 7 2 11 8 15 10 5 9 0 6 13 12 14 4。注意空位为0。逆序数计算得到是&＃xff1a;45&＃xff0c;计算过程是&＃xff1a;0&＃43;1&＃43;0&＃43;2&＃43;0&＃43;1&＃43;0&＃43;2&＃43;5&＃43;3&＃43;10&＃43;6&＃43;1&＃43;2&＃43;1&＃43;11。其总逆序数为(45) &＃43; 2(0的行号) &＃43; 2(0的列号)&＃61;奇数&＃xff0c;能通过移动数字&＃xff0c;使数字按顺序排列。自己也用3x3数字华容道验证了多次&＃xff0c;判据都是正确的。
有了判断数字华容道是否有解的判据&＃xff0c;用程序就就很容易删除无解的随机排列。用随机函数生成一个随机排列数字&＃xff0c;如判断无解&＃xff0c;再重新生成一个随机排列&＃xff0c;直到找到一个有解的随机排列。由于所有随机排列中&＃xff0c;有解和无解的随机排列各占一半&＃xff0c;即出现有解概率为1/2&＃xff0c;通过几次循环就能找到有解的排列。
网上有一种找有解数字排列的方法&＃xff0c;先将阵列数字按顺序排列&＃xff0c;空在右下角&＃xff0c;然后随机移动带数字的方块到空处&＃xff0c;随机移动若干步&＃xff0c;将移动后的排列提供给玩家。这的确能保证有解。但每次要移动多少步&＃xff0c;才能看起来是随机的&＃xff0c;能不能保证所有有解的排列能够随机出现。实现这些还是有些问题的。
上边提到的那篇文章还指出&＃xff0c;这些“无解排列”&＃xff0c;通过移动数字&＃xff0c;能做到只有最后两个数顺序不正确&＃xff0c;例如3x3数字华容道无解&＃xff0c;第1&＃xff0c;2行数字按顺序排列&＃xff0c;最后一行数据是&＃xff1a;8、7&＃xff0c;空&＃xff0c;称为“镜像解”。是否也可以变通一下&＃xff0c;认为“镜像解”也算玩家完成任务。