找出肯肯拼图“乘法”域中所有可能的因素

Question

KenKen拼图是一个拉丁方，分成边连接域：一个单元，同一行或列中的两个相邻单元，一行或一个单元中排列的三个单元，每个域都有一个给出目标数的标签和一个单独的算术运算（+-*/），该运算将应用于域单元中的数字以生成目标数。（如果域只有一个单元，则没有给定运算符，只有一个目标-平方为您求解。如果运算符是-或/，那么域中只有两个单元。）这个难题的目的是（重新）构造与域的边界和标签一致的拉丁方。（我想我只见过一个有非唯一解的谜题。）

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

编写kenkenken解算器的第一步是拥有可以在任何域中生成可能的数字组合的例程，首先忽略域的几何结构。（一个线性域，比如一行三个单元格，在已解决的谜题中不能有重复的数字，但我们暂时忽略了这个问题。）我已经能够编写一个Python函数，它可以逐个处理加法标签：给出谜题的宽度、域中单元格的数量以及目标和，它返回一个有效数的元组列表，这些元组加起来就是目标值。在

乘法的情况我不知道。我可以得到一个字典，其中的键等于给定大小的谜题中给定大小的域中可获得的乘积，其值是元组列表，其中包含给出乘积的因子，但我无法逐项计算例程，甚至连一个糟糕的例程都算不上。在

把一个给定的乘积分解成素数看起来很容易，但是把素数列表分解成所需的因子数让我很为难。如果不是他的第三卷的算法，我就不知道他的算法了。理解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

我将留给你来生成基本因子，但这似乎对

^{pr2}$

对于更难的情况，比如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]