问在KenKen拼图“乘法”域中查找所有可能的因素
EN

Stack Overflow用户

提问于 2009-06-05 16:42:40

回答 1查看 3.1K关注 0票数 3

KenKen拼图是一个拉丁正方形，分为多个边连接的域:一个单元格，同一行或列中的两个相邻单元格，一行或单元格中排列的三个单元格，等等。每个域都有一个标签，它给出一个目标数字和一个算术运算(+-*/)，该运算应用于该域的单元格中的数字，以产生目标数字。(如果域只有一个单元格，则没有给定的运算符，只有一个目标-平方已为您解决。如果运算符是-或/，则该域中只有两个单元。)拼图的目的是(重建)与域的边界和标签一致的拉丁方。(我想我只看过一次具有非唯一解的拼图。)

单元格中的数字可以从1到拼图的宽度(高度)；通常，拼图的边上有4到6个单元格，但可以考虑任意大小的拼图。在已发布的拼图(4x4或6x6)中，域通常不超过5个单元，但同样，这似乎不是一个硬限制。(然而，如果拼图只有一个域，那么这个维度的拉丁方块就会有很多解……)

编写KenKen求解器的第一步是具有可以在任何域中生成可能的数字组合的例程，首先忽略域的几何形状。(线性域，如三个单元格的行，在已解决的拼图中不能有重复的数字，但我们暂时忽略这一点。)我已经能够编写一个Python函数来逐个处理加法标签:给它提供拼图的宽度、域中的单元格数量和目标和，它将返回一个有效数字加起来的元组列表。

乘法的例子让我难以理解。我可以得到一个字典，其关键字等于给定大小的拼图中在给定大小的域中可获得的产品，值是包含给定产品的因子的元组列表，但我无法计算出一个逐个案例的例程，甚至不是一个糟糕的例程。

将给定的乘积分解为质数似乎很容易，但将质数列表划分为所需的因数会让我感到困惑。(我已经思考了Knuth的TAOCP卷4的分册3，但我还没有学会如何‘摸索’他的算法描述，所以我不知道他的集合划分算法是否会是一个起点。理解Knuth的描述可能是另一个问题！)

我很乐意预先计算常见域名和拼图大小的“乘法”字典，并将加载时间加到开销上，但这种方法似乎不是处理拼图的有效方法，比如说，一边有100个单元格，而域名大小从2到50个单元。

prime-factoring

python

algorithm

partitioning

TDSQL-CMySQL免费体验

云原生数据库TDSQL-C MySQL 2核4G 免费体验15天

回答 1

Stack Overflow用户

回答已采纳

发布于 2009-06-05 22:35:34

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

要解决这个问题，您只需要对目标数进行素数分解，然后使用组合方法从这些因子中形成所有可能的子积。(当您拥有所有可能的子产品时，还有一些其他约束很容易包含进来，比如没有条目可以比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]