algorithm - Kakuro 和 Subset Sum，其中超集包含连续的正整数，子集的大小固定为 k

Question

我正在用 Java 开发数谜游戏。数谜是一种类似于数独的游戏。

Kakuro 的目标是用 1 到 9 的整数填充那些空白 block ，使得每个“区域”中没有重复的数字，并且该区域中空白 block 中的所有数字总和为该区域中的数字该地区的“提示 block ”。区域示例在上图中标记为红色。

现在我想做的是编写一个可以自动解决给定数谜的 AI。这首先要求您需要从整数范围 (1,9) 中找到 K 个元素的所有可能组合，使得这些 K 个元素的总和等于该区域中“提示 block ”中指示的数字。 (在这种情况下，K 是该区域中空白 block 的数量)这是“子集问题”的变体，除了超集更加均匀(1-9 的连续整数)并且子集具有固定大小K. 更棒的是，超集的范围可以提前缩小。例如，请参见图片右侧的 block 。这种情况下的总和为 24，K 为 3。通过在该区域中选择一个任意 block 并假设所有其他 block 都处于其可能的最大值，我们可以推断任意 block 必须大于或等于 (24-( 9+8))=7。我们可以通过计算 (24-(1+2))=21 来计算最大值，这并不重要，因为 21>9。因此，超集变为 {7,8,9}。

这个区域很简单，因为 K = 超集大小。但是，如果 K 比超集大小小得多，检查所有组合将(我不确定)导致计算 (SuperSize-K)!时间。这是低效的。我现在的问题是，是否有任何最适合这种情况的子集和问题的解决方案变体？我使用 Java 编写代码，但欢迎使用任何编程语言，包括 SPL 和 BrainF*ck。

Answer 1

从 1 到 9 的整数集有 2⁹=512 个子集。(据我所知，实际上只有 502 个是有趣的，因为大小为 0 和 1 的集合永远不会出现。)这很漂亮很容易预先计算这些并按总和(3 到 45 之间，包括在内)和大小来组织它们。然后它只是一个简单的查找来获取目标集。

对于标准的 9 整数 Kakuro，没有 setsize/sum 组合有超过 12 个可能的解决方案；有 12 个解的两个组合是 k=5/sum=25 和 k=4/sum=20。 (这种二元性并非偶然，结果是您可以存储一半的预计算集。对于给定的 n——在本例中为 9——，k 的任何解决方案 求和为 s 的数字可以转换为 n-k 求和为 n*(n+1)/2 - s 的解决方案> 通过简单地取每个子集的补集。)

但是，随着 n 的增加，子集的最大数量呈指数增长。我使用这个 Python3“单行”计算了最多 30 个:

for j in range(9,31):
  print(j, Counter((len(k),sum(k))
                   for k in combinations(range(1,j+1), j//2)
                  ).most_common(1))

最后两个值需要几秒钟的时间来计算，因此这绝对不是枚举可能性的最有效策略。为了便于阅读，我稍微清理了输出。

 N       k      sum       count
--      --      ---       -----
 9       4       20          12
10       5       28          20
11       5       31          32
12       6       39          58
13       6       42          94
14       7       52         169
15       7       56         289
16       8       68         526
17       8       72         910
18       9       86        1667
19       9       90        2934
20      10      105        5448
21      10      110        9686
22      11      126       18084
23      11      132       32540
24      12      150       61108
25      12      156      110780
26      13      175      208960
27      13      182      381676
28      14      203      723354
29      14      210     1328980
30      15      233     2527074

在我看来，大量的可能性使得生成具有完整解决方案的数谜变得更加困难。当然，您可以避免大多数可能的 k/sum 组合，但谜题本身似乎仍然具有内在的不可扩展性。

(注意:这是整数序列在线百科全书中的Sequence A277218；它与Sequence A055606有关，与Magic Carpets有关。)