algorithm - 生成求和矩阵游戏的算法

Question

我试着生成一个矩阵，就像一个交叉和游戏，在一个随机数矩阵中，对于每一行和每一列的给定和（或一个乘积，取决于一个选择的操作），只有一种方法可以“去激活”（意思是从最终和或乘积中排除数字）正确的数字，以便每一行和每一列最后将活动数字相加为正确的和。
为了说明这一点，假设我有一个3x3矩阵，并且选择和（在*旁边的数字表示和）：

   *12* *5*  *3*
4*  1    2    3  *4

9*  4    5    6  *9

7*  7    8    9  *7

为了解决这个问题，我需要停用数字2，6，9和8。
一种生成矩阵所需和的方法，它只生成数字，然后随机选择要排除的数字。但是，缺点是，对于更大的矩阵，如7x7、8x8，很可能会有多个解决方案。
我正在考虑的另一个解决方案是排除每一行/列可以相加的数字。例如，如果所需的和是5，那么4 2 1 3将是无效的，因为（4+1和3+2），但这看起来相当复杂和低效。
如果有人指点我，我会非常感激。这似乎是个解决了的问题，但我不知道该找什么。

Answer 1

使用解算器检查随机网格
对于一个有限大小的矩阵，高达10×10左右，一个简单的求解器可以快速找到解。如果只有一个，即使是我在javaScript中编写的快速“脏”解算器通常也会在不到一秒钟的时间内找到。
我使用了一个简单的递归逐行求解器，其工作原理如下：
对于每一列，遍历每一个可能的数字选择，并检查排除它们是否给列正确的和然后检查是否有任何数字是所有有效选择的一部分，或不是所有有效选择的一部分；这些数字必须包含在所有选择中并避免出现。
对于每一行，遍历每一个可能的数字选择，并检查排除它们是否使该行得到正确的和，以及它们是否包含在上一步中标识的所有要包括的数字和所有要避免的数字。存储每行的所有有效选择。
在这些准备之后，算法的递归部分被调用：
接收包含数字的矩阵、每行和的列表以及每列和的列表。
对于顶行，检查是否不能排除任何数字（因为下面的数字加起来小于该列的总和）
遍历顶行中所有有效的数字选择（在准备阶段确定）。对于每一个选择，检查删除它是否给行正确的和。如果是，则在删除了顶行的矩阵副本、删除了第一项的每行和列表以及减去了顶行中未排除的数字的每列和列表的情况下递归。
从这样的模式开始，其中X表示要排除的单元格：

 -  -  -  X  -  -  -  X  -  -
 -  -  -  -  X  -  X  -  -  -
 X  -  -  -  -  X  -  -  -  -
 -  X  -  -  -  -  -  -  -  X
 -  -  X  -  -  -  -  -  X  -
 -  X  -  -  -  -  -  X  -  -
 X  -  -  -  -  -  -  -  X  -
 -  -  -  -  X  -  -  -  -  X
 -  -  -  X  -  X  -  -  -  -
 -  -  X  -  -  -  X  -  -  -

我让矩阵填充从1到9的随机数，然后在矩阵上运行解算器，大约十分之一的尝试会产生这样的网格，它只有一个解：

 4  1  3  8  1  3  4  1  1  8    25
 9  9  7  8  1  1  3  2  1  7    44
 9  8  8  1  5  5  9  2  2  6    41
 4  6  8  1  9  2  1  7  1  5    33
 9  4  2  4  4  5  8  6  3  8    48
 8  5  6  9  6  6  6  4  1  8    50
 4  3  2  4  8  7  6  7  9  1    38
 6  7  8  1  9  9  9  4  6  7    50
 7  7  1  7  9  6  2  7  1  2    36
 3  3  8  8  9  2  4  9  6  8    48

50 42 43 36 51 35 45 44 19 48

当只使用1到9之间的数字时，对于较小的网格（8×8网格中有一半以上的网格只有一个解）很容易找到只有一个解的网格，但对于大于10×10的网格，则很难找到。大多数较大的网格都有许多解决方案，比如这个有16个：

 4  1  5  7  2  2  5  6  5  8    32
 5  1  1  6  4  6  5  2  2  9    32
 9  2  3  8  7  7  4  8  3  6    41
 4  8  1  8  4  3  1  9  7  2    37
 4  6  9  8  8  5  8  6  6  5    50
 1  5  5  5  1  3  5  7  7  1    28
 5  5  1  7  2  9  2  6  3  8    40
 9  8  9  2  8  3  1  9  6  8    47
 5  1  3  7  1  2  6  1  8  9    34
 1  5  1  2  1  1  1  6  4  3    23

33 29 28 46 26 32 32 47 42 49

解决方案的数量还取决于每行和每列排除的数量上面显示的结果特别适用于每行和每列包含两个排除数字的模式。排除的数字越多，解决方案的平均数量就越大（我假设峰值为50%排除的数字）。
当然，您可以使用要排除的单元格的随机模式，或者手动选择数字，或者使用特定分布选择随机数字，或者为矩阵提供您认为将增强其作为拼图的实用性的任何其他属性。对于较小的网格，多个解决方案似乎不是一个大问题，但当然最好检查它们；我首先在手工创建的网格上运行解算器，结果发现有三个解决方案。
选择排除的值
由于排除数的值可以自由选择，这显然是提高矩阵只有一个解的机会的方法。如果选择行和列中其他地方不出现的数字，或者只出现一次，则只有一个解决方案的10×10网格的百分比将从10%上升到50%。
（这个简单的方法显然提供了应该排除哪些数字的线索，而不是一行或一列中出现几次的数字，因此最好使用每个数字在整个网格中出现多少次，而不仅仅是在它自己的行和列中。）
当然，您可以选择排除的值，这些值加起来是一个数字，不能与行或列中的任何其他值组合在一起，这将保证只有一个解决方案当然，这个问题是这样一个网格并不是真正的拼图；只有一种方法可以排除值并为每一行和每一列获得正确的和一个变量是选择排除的值，这样行或列的总和可以精确地为2、3或…方式。这也会给你一个选择拼图难度的方法。
数独-避免重复值
更大的网格有更高的机会拥有多个解决方案，这当然与只使用1到9的值有关。10×10及以上的网格保证在每行和每列中都有重复的值。
要检查每行或每列没有重复值的网格是否更可能只导致一个解决方案，最明显的测试数据是数独。
当使用每行和每列1到3个单元格的随机模式排除时，大约90%的基于数独的交叉和矩阵游戏只有一个解决方案，而使用随机值时，这一比例约为60%。
（当然，创建既可以作为数独又可以作为交叉和矩阵拼图的拼图可能会很有趣。对于每一个数独游戏来说，应该很容易找到一个视觉上令人满意的排除单元模式，只有一个解决方案。）
实例
对于那些喜欢挑战（或想测试解算器）的人，这里有一个交叉和数独和一个只有一个解的11×11、12×12和13×13交叉和矩阵拼图：

 .  3  .   4  .  .   .  .  .    36
 .  6  .   .  9  .   .  4  5    35
 4  .  .   .  .  .   9  .  .    33

 .  .  3   .  .  1   .  .  .    39
 .  .  .   .  .  8   2  .  3    29
 .  7  .   .  .  2   6  .  9    40

 .  2  .   .  .  .   .  .  .    33
 3  .  8   .  .  .   .  .  .    31
 .  .  7   .  5  .   .  6  4    36

33 34 35  37 27 42  34 32 38

 6  6  5  2  9  4  4  6  7  1  8    44
 1  8  1  1  4  7  3  3  3  1  2    25
 5  8  7  7  5  5  6  1  7  6  5    43
 8  9  6  2  9  1  6  2  9  8  3    59
 8  8  2  3  6  3  7  7  5  9  8    53
 8  2  7  2  6  2  9  4  7  1  2    47
 3  9  2  8  8  4  2  9  3  6  6    50
 3  1  8  2  6  4  1  7  9  4  6    42
 8  3  6  7  8  5  4  4  2  8  4    46
 8  3  8  6  5  7  9  8  6  9  2    59
 9  6  8  4  6  2  4  8  5  6  2    49

52 50 47 40 58 34 46 50 54 48 38

 1  5  8  6  6  5  4  9  9  7  7  8    66
 5  6  2  5  5  4  8  5  7  7  3  6    54
 8  2  8  2  8  6  9  4  9  5  9  9    67
 1  2  8  2  3  4  5  8  8  7  6  2    48
 8  9  4  8  7  2  8  2  2  3  7  7    57
 2  2  1  9  4  1  1  1  5  6  1  5    36
 2  1  4  2  9  1  2  8  1  6  9  7    49
 3  6  5  7  5  5  7  9  4  7  7  5    59
 8  2  3  4  8  2  2  3  3  1  6  1    35
 4  2  1  7  7  1  7  9  6  7  9  7    51
 7  4  3  2  8  3  6  7  8  3  1  8    54
 3  8  9  8  7  6  5  7  1  1  7  3    59

48 45 51 47 62 38 61 59 57 50 60 57

 4  3  9  3  7  6  6  9  7  7  5  9  1    71
 2  7  4  7  1  1  9  8  8  3  3  5  4    52
 6  9  6  5  6  4  6  7  3  6  6  8  8    68
 5  7  8  8  1  5  3  4  5  7  2  9  6    60
 5  3  1  3  3  5  4  5  9  1  8  2  7    50
 3  8  3  1  8  4  8  2  2  9  7  3  6    58
 6  6  9  8  3  5  9  1  4  6  9  8  2    69
 8  1  8  2  9  7  1  3  8  5  2  1  5    50
 9  9  4  5  4  9  7  1  8  8  1  2  6    60
 9  2  4  8  4  5  3  3  7  9  6  1  6    58
 5  2  7  6  8  5  6  6  1  3  4  7  2    47
 8  3  5  2  7  2  4  5  8  1  2  6  2    49
 7  1  7  4  9  2  9  8  9  3  5  2  3    59

66 50 69 50 58 49 64 57 65 66 56 47 54