找出 KenKen 谜题“乘法”中所有可能的因素 领域

Question

KenKen 谜题是一个拉丁方格，分为边连接的域：单个单元格、同一行或同一列中的两个相邻单元格、排成一行或一个单元的三个单元格等。每个域都有一个标签，给出一个目标数字和单个算术运算（+-*/），该算术运算将应用于域单元中的数字以产生目标数字。 （如果域只有一个单元格，则没有给出运算符，只是一个目标 --- 平方已为您解出。如果运算符是 - 或 /，则域中只有两个单元格。）难题是（重新）构建与域的边界和标签一致的拉丁方。 （我认为我只见过一次具有非唯一解决方案的谜题。）

单元格中的数字范围可以从 1 到谜题的宽度（高度）； 通常，拼图的一侧有 4 或 6 个单元格，但也可以考虑任何大小的拼图。 已发布的谜题（4x4 或 6x6）中的域通常不超过 5 个单元格，但是，这似乎并不是硬性限制。 （但是，如果谜题只有一个域，那么该维度的拉丁方就有多少个解……）

编写 KenKen 求解器的第一步是拥有可以生成可能的数字组合的例程在任何域中，首先忽略域的几何形状。 （线性域，如一行三个单元格，在已解决的谜题中不能有重复的数字，但我们暂时忽略这一点。）我已经能够编写一个 Python 函数来逐个处理添加标签：给它拼图的宽度、域中的单元格数量以及目标总和，并且它返回与目标相加的有效数字的元组列表。

乘法的情况让我困惑。 我可以获得一本字典，其键等于给定大小的拼图中给定大小的域中可达到的乘积，其值是包含给出乘积的因素的元组列表，但我无法解决问题例行公事，甚至不是坏例行公事。

将给定的乘积分解为素数似乎很容易，但是将素数列表划分为所需数量的因子却让我感到困惑。 （我沉思过 Knuth 的 TAOCP 第 4 卷第 3 卷，但我还没有学会如何“理解”他的算法描述，所以我不知道他的集合划分算法是否是一个起点。理解 Knuth 的描述可能是另一个问题！）

我很高兴预先计算公共域和谜题大小的“乘法”字典，并将加载时间记入开销，但这种方法似乎不是处理 100 个单元格谜题的有效方法一侧有 2 到 50 个单元格。

Answer 1

简化的目标：需要枚举所有相乘形成某个乘积的整数组合，其中整数的数量是固定的。

为了解决这个问题，您所需要的只是对目标数进行素因式分解，然后使用组合方法从这些因子中形成所有可能的子产品。 （一旦您拥有所有可能的子产品，拼图的其他一些约束就很容易包含在内，例如没有任何条目可以大于 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=2106

max_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]