KenKen 拼图是一个拉丁方格，分为边连接域:单个单元格、同一行或列中的两个相邻单元格、排列在一行或一个单元格中的三个单元格等。每个域都有一个标签，给出了一个目标number 和单个算术运算 (+-*/)，该运算将应用于域单元格中的数字以产生目标数字。 (如果域只有一个单元格，则没有给出运算符，只有一个目标 --- 为您求解正方形。如果运算符是 - 或/，则域中只有两个单元格。)难题是(重新)构建与域的边界和标签一致的拉丁方格。 (我想我只见过一次具有非唯一解决方案的谜题。)
单元格中的数字可以从 1 到拼图的宽度(高度)；通常，拼图的一侧有 4 或 6 个单元格，但可以考虑任何大小的拼图。已发布谜题(4x4 或 6x6)中的域通常不超过 5 个单元格，但同样，这似乎不是硬性限制。 (但是，如果这个谜题只有一个域，那么解的数量就会与该维度的拉丁方格数一样多……)
编写 KenKen 求解器的第一步是拥有可以生成任何域中可能的数字组合的例程，首先忽略域的几何。 (线性域，就像一行三个单元格，在解决的谜题中不能有重复的数字，但我们暂时忽略了这一点。)我已经能够编写一个 Python 函数来逐个处理加法标签:给它拼图的宽度、域中的单元格数和目标总和，它返回一个由有效数字组成的元组列表，这些数字与目标相加。
乘法的情况让我望而却步。我可以得到一个字典，其键等于在给定大小的谜题中给定大小的域中可获得的产品，值是包含给出产品的因素的元组列表，但我无法解决一个案例逐案例行，甚至不是一个糟糕的例程。
将给定的乘积分解为素数似乎很容易，但是将素数列表划分为所需的因子数让我感到难堪。 (我已经沉思了 Knuth 的 TAOCP 第 4 卷的 Fascicle 3，但我还没有学会如何“理解”他的算法描述，所以我不知道他的集合分区算法是否是一个起点。了解 Knuth 的描述可能是另一个问题!)
我很高兴预先计算常见域和拼图大小的“乘法”字典，并将加载时间计入开销，但这种方法似乎不是处理例如一边拼图 100 个单元格的有效方法，域大小从 2 到 50 个单元格。
最佳答案
简化目标:您需要枚举所有相乘以形成某个乘积的整数组合，其中整数的数量是固定的。
要解决这个问题，您只需要对目标数进行质因数分解，然后使用组合方法从这些因数中形成所有可能的子产品。 (还有一些其他的拼图限制，一旦您拥有所有可能的子产品，就很容易包含这些限制，例如没有比 max_entry 更好的条目，并且您可以使用固定数量的整数 n_boxes_in_domain 。)
例如，如果 max_entry=6 、 n_boxes_in_domain=3 和 target_number=20 : 20 产生 (2, 2, 5);它转到 (2, 2, 5) 和 (1, 4, 5)。
诀窍是形成所有可能的子产品，下面的代码就是这样做的。它的工作原理是遍历形成所有可能的单对的因素，然后递归地执行此操作，以给出所有单对或多对的所有可能集合。 (这是低效的，但即使是大数也有一个小的素数分解):
def xgroup(items):
L = len(items)
for i in range(L-1):
for j in range(1, L):
temp = list(items)
a = temp.pop(j)
b = temp.pop(i)
temp.insert(0, a*b)
yield temp
for x in xgroup(temp):
yield x
def product_combos(max_entry, n_boxes, items):
r = set()
if len(items)<=n_boxes:
r.add(tuple(items))
for i in xgroup(items):
x = i[:]
x.sort()
if x[-1]<=max_entry and len(x)<=n_boxes:
r.add(tuple(x))
r = [list(i) for i in r]
r.sort()
for i in r:
while len(i)<n_boxes:
i.insert(0, 1)
return r
我会把它留给你来产生主要因素，但这似乎适用于
max_entry=6, n_boxes=3, items=(2,2,5)
[2, 2, 5]
[1, 4, 5]
对于更难的情况，比如
target_number=2106max_entry=50, n_boxes=6, items=(2,3,3,3,3,13)
[2, 3, 3, 3, 3, 13]
[1, 2, 3, 3, 3, 39]
[1, 2, 3, 3, 9, 13]
[1, 1, 2, 3, 9, 39]
[1, 1, 2, 3, 13, 27]
[1, 1, 2, 9, 9, 13]
[1, 1, 1, 2, 27, 39]
[1, 3, 3, 3, 3, 26]
[1, 3, 3, 3, 6, 13]
[1, 1, 3, 3, 6, 39]
[1, 1, 3, 3, 9, 26]
[1, 1, 3, 3, 13, 18]
[1, 1, 3, 6, 9, 13]
[1, 1, 1, 3, 18, 39]
[1, 1, 1, 3, 26, 27]
[1, 1, 1, 6, 9, 39]
[1, 1, 1, 6, 13, 27]
[1, 1, 1, 9, 9, 26]
[1, 1, 1, 9, 13, 18]
关于python - 在 KenKen 拼图 'multiply' 域中找到所有可能的因素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/958678/