在KenKen谜题'乘法'域中找到所有可能的因子

Question

KenKen谜题是一种拉丁方格，它被分成一些相连的区域：可以是一个单独的格子，或者是同一行或同一列中相邻的两个格子，或者是三个格子排成一行或呈L形等等。每个区域都有一个标签，标签上有一个目标数字和一个算术运算符（加、减、乘、除），这个运算符需要应用到区域内格子的数字上，以得到目标数字。（如果区域只有一个格子，就没有运算符，只有目标数字——这个格子就已经给你解好了。如果运算符是减法或除法，那么这个区域里只有两个格子。）这个谜题的目标是（重新）构建一个符合区域边界和标签的拉丁方格。（我觉得我只见过一次有不唯一解的谜题。）

格子里的数字可以从1到谜题的宽度（高度）变化；通常，谜题的边长是4或6个格子，但也可以考虑任何大小的谜题。已发布的谜题（4x4或6x6）中的区域通常不超过5个格子，但这似乎并不是一个严格的限制。（不过，如果谜题只有一个区域，那么解的数量就和该维度的拉丁方格数量一样多……）

编写KenKen解题程序的第一步是要有一些程序，可以生成任何区域内数字的可能组合，最开始可以忽略区域的形状。（像三格一行这样的线性区域，在解出的谜题中不能有重复的数字，但我们暂时不考虑这个问题。）我已经写了一个Python函数，可以逐个处理加法标签：给它谜题的宽度、区域内的格子数量和目标和，它会返回一个有效数字的元组列表，这些数字加起来等于目标和。

乘法的情况让我感到困惑。我可以得到一个字典，字典的键是某个大小的区域在某个大小的谜题中可以得到的乘积，值是包含能得到该乘积的因子的元组列表，但我无法逐个处理这个情况，甚至连一个不好的方法都想不出来。

将给定的乘积分解成质因数似乎很简单，但将质因数列表分成所需数量的因子让我感到困惑。（我曾经研究过Knuth的《计算机程序设计艺术》第四卷第三册，但我还没有学会如何“理解”他的算法描述，所以我不知道他的集合划分算法是否可以作为一个起点。理解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]