KenKen 谜题加数：REDUX A（已修正）非递归算法

Question

这个问题与 KenKen 拉丁方谜题的那些部分有关，这些部分要求您找到 ncells 数字与 x 值的所有可能组合，使得 1 <= x <= maxval 且 x(1) + ... + x(ncells ) = 目标总和。 在测试了几个更有希望的答案后，我将把答案奖授予 Lennart Regebro，因为：

1. 他的例程和我的一样快 (+-5%)，并且

2. 他指出我原来的例程在某个地方有一个错误，这让我明白了它真正想要做什么。 谢谢，Lennart。

chrispy 贡献了一种算法，看起来与 Lennart 的算法相当，但 5 小时后，很快，第一个电线就得到了它。

备注：Alex Martelli 的基本递归算法是一个示例，它创建了所有可能的组合，然后将它们全部扔到筛子上，看看哪些可以穿过筛子。 这种方法比 Lennart 或我的方法花费的时间要长 20 倍以上。 （将输入提升到 max_val = 100、n_cells = 5、target_sum = 250，在我的盒子上，这是 18 秒 vs. 8 分钟以上。） 寓意：不生成所有可能的组合是好的。

另一条评论：Lennart 和我的例程以相同的顺序生成相同的答案。 从不同角度看它们实际上是同一个算法吗？ 我不知道。

我突然想到一些事情。 如果您对答案进行排序，例如，以 (8,8,2,1,1) 开始，以 (4,4,4,4,4) 结束（使用 max_val=8, n_cells=5, target_sum 得到的结果） =20)，该系列形成一种“最慢下降”，第一个是“热”，最后一个是“冷”，其间的阶段数尽可能多。 这与“信息熵”有关吗？ 衡量它的正确指标是什么？ 是否有一种算法可以按热量降序（或升序）产生组合？ （据我所知，这个没有，尽管在短时间内它很接近，看看标准化的标准差。）

这是Python例程：

#!/usr/bin/env python
#filename: makeAddCombos.07.py -- stripped for StackOverflow

def initialize_combo( max_val, n_cells, target_sum):
    """returns combo
    Starting from left, fills combo to max_val or an intermediate value from 1 up.  
    E.g.:  Given max_val = 5, n_cells=4, target_sum = 11, creates [5,4,1,1].
    """
    combo = []
    #Put 1 in each cell.
    combo += [1] * n_cells
    need = target_sum - sum(combo)
    #Fill as many cells as possible to max_val.
    n_full_cells = need //(max_val - 1)
    top_up = max_val - 1
    for i in range( n_full_cells): combo[i] += top_up
    need = target_sum - sum(combo)
    # Then add the rest to next item.
    if need > 0:
        combo[n_full_cells] += need
    return combo
#def initialize_combo()

def scrunch_left( combo):
    """returns (new_combo,done)
    done   Boolean; if True, ignore new_combo, all done;
            if Falso, new_combo is valid.

    Starts a new combo list.  Scanning from right to left, looks for first
    element at least 2 greater than right-end element.  
    If one is found, decrements it, then scrunches all available counts on its
    right up against its right-hand side.  Returns the modified combo.
    If none found, (that is, either no step or single step of 1), process
    done.
    """
    new_combo = []
    right_end = combo[-1]
    length = len(combo)
    c_range = range(length-1, -1, -1)
    found_step_gt_1 = False
    for index in c_range:
        value = combo[index]
        if (value - right_end) > 1:
            found_step_gt_1 = True
            break
    if not found_step_gt_1:
        return ( new_combo,True)

    if index > 0:
        new_combo += combo[:index]
    ceil = combo[index] - 1
    new_combo += [ceil]
    new_combo += [1] * ((length - 1) - index)
    need = sum(combo[index:]) - sum(new_combo[index:])
    fill_height = ceil - 1
    ndivf = need // fill_height
    nmodf = need % fill_height
    if ndivf > 0:
        for j in range(index + 1, index + ndivf + 1):
            new_combo[j] += fill_height
    if nmodf > 0:
        new_combo[index + ndivf + 1] += nmodf
    return (new_combo, False)
#def scrunch_left()

def make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum):
    """
    Build combos, list of tuples of 2 or more addends.
    """
    combo = initialize_combo( max_val, n_cells, target_sum)
    combos.append( tuple( combo))
    while True:
        (combo, done) = scrunch_left( combo)
        if done:
            break
        else:
            combos.append( tuple( combo))
    return combos
#def make_combos_n_cells_ge_two()

if __name__ == '__main__':

    combos = []
    max_val     = 8
    n_cells     = 5
    target_sum  = 20
    if n_cells == 1: combos.append( (target_sum,))
    else:
        combos = make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum)
    import pprint
    pprint.pprint( combos)

Answer 1

抱歉，您的代码有点长，而且可读性不是很好。 如果你可以尝试以某种方式总结它，也许有人可以帮助你写得更清楚。

至于问题本身，我的第一个想法是使用递归。 （据我所知，您已经这样做了。再次抱歉，我无法阅读您的代码。）想出一种方法，可以将问题简化为同一问题的更小更简单的版本，反复进行，直到您有一个一个简单的案例，一个非常简单的答案。

更具体一点，您有这三个参数：max_val、target_sum 和 n_cells。 您能否将其中一个数字设置为某个特定值，以便为您提供一个根本不需要思考的极其简单的问题？ 一旦你有了这个，你能将问题的稍微困难的版本减少到已经解决的版本吗？

编辑：这是我的代码。 我不喜欢它重复数据删除的方式。 我确信还有一种更 Pythonic 的方式。 此外，它不允许在一个组合中两次使用相同的数字。 要撤消此行为，只需删除 if n not in numlist: 行即可。 我不确定这是否完全正确，但它似乎有效并且（恕我直言）更具可读性。 您可以轻松地添加记忆，这可能会大大加快速度。

def get_combos(max_val, target, n_cells):
    if target <= 0:
        return []
    if n_cells is 1:
        if target > max_val:
            return []
        else:
            return [[target]]
    else:
        combos = []
        for n in range(1, max_val+1, 1):
            for numlist in get_combos(max_val, target-n, n_cells-1):
                if n not in numlist:
                    combos.append(numlist + [n])
        return combos

def deduplicate(combos):
    for numlist in combos:
        numlist.sort()
    answer = [tuple(numlist) for numlist in combos]
    return set(answer)

def kenken(max_val, target, n_cells):
    return deduplicate(get_combos(max_val, target, n_cells))

Answer 2

首先，我自己正在学习Python，所以这个解决方案不会很好，但这只是解决这个问题的尝试。 我尝试以递归方式解决它，我认为递归解决方案对于此类问题来说是理想的选择，尽管该递归解决方案可能不是这个：

def GetFactors(maxVal, noOfCells, targetSum):
    l = []
    while(maxVal != 0):
        remCells = noOfCells - 1
        if(remCells > 2):
            retList = GetFactors(maxVal, remCells, targetSum - maxVal)
            #Append the returned List to the original List
            #But first, add the maxVal to the start of every elem of returned list.
            for i in retList:
                i.insert(0, maxVal)
            l.extend(retList)

        else:
            remTotal = targetSum - maxVal
            for i in range(1, remTotal/2 + 1):
                itemToInsert = remTotal - i;
                if (i > maxVal or itemToInsert > maxVal):
                    continue
                l.append([maxVal, i, remTotal - i])
        maxVal -= 1
    return l



if __name__ == "__main__":
    l = GetFactors(5, 5, 15)
    print l

Answer 3

这是 C/C++ 中的简单解决方案：

const int max = 6;
int sol[N_CELLS];

void enum_solutions(int target, int n, int min) {
  if (target == 0 && n == 0)
    report_solution(); /* sol[0]..sol[N_CELLS-1] is a solution */
  if (target <= 0 || n == 0) return; /* nothing further to explore */
  sol[n - 1] = min; /* remember */
  for (int i = min; i <= max; i++)
    enum_solutions(target - i, n - 1, i);
}

enum_solutions(12, 4, 1);

Answer 4

有点离题，但仍然可能对 kenken 编程有所帮助。

我使用 DLX 算法求解 Killer Sudoku 得到了很好的结果（与 KenKen 非常相似，它有笼子，但只有求和）。 大多数问题的处理时间不到一秒，并且是用 MATLAB 语言实现的。

参考这个论坛
http://www.setbb.com/ phpbb/viewtopic.php?t=1274&highlight=&mforum=sudoku

杀手数独
“看看维基百科，不能发布超链接”该死的垃圾邮件发送者

Answer 5

这是一个使用生成器的简单但简洁的解决方案：

def descending(v):
  """Decide if a square contains values in descending order"""
  return list(reversed(v)) == sorted(v)

def latinSquares(max_val, target_sum, n_cells):
  """Return all descending n_cells-dimensional squares,
     no cell larger than max_val, sum equal to target_sum."""
  possibilities = itertools.product(range(1,max_val+1),repeat=n_cells)
  for square in possibilities:
    if descending(square) and sum(square) == target_sum:
      yield square

我可以通过直接枚举降序网格列表来优化此代码，但我发现 itertools.product 对于首次解决方案来说更加清晰。 最后，调用该函数：

for m in latinSquares(6, 12, 4):
  print m

Answer 6

这是另一个基于生成器的递归解决方案，但这次使用一些简单的数学来计算每一步的范围，避免不必要的递归：

def latinSquares(max_val, target_sum, n_cells):
  if n_cells == 1:
    assert(max_val >= target_sum >= 1)
    return ((target_sum,),)
  else:
    lower_bound = max(-(-target_sum / n_cells), 1)
    upper_bound = min(max_val, target_sum - n_cells + 1)
    assert(lower_bound <= upper_bound)
    return ((v,) + w for v in xrange(upper_bound, lower_bound - 1, -1)
                     for w in latinSquares(v, target_sum - v, n_cells - 1))

如果您提供无法满足的参数，此代码将失败并出现断言错误； 这是我的“正确性标准”的副作用，即我们从不进行不必要的递归。 如果您不希望出现这种副作用，请删除断言。

请注意除法后使用 -(-x/y) 进行舍入。 可能有一种更Pythonic的方式来编写它。 另请注意，我正在使用 生成器表达式的产量。

for m in latinSquares(6,12,4):
  print m

Answer 7

你的算法乍一看似乎相当不错，而且我不认为面向对象或其他语言会改进代码。 我不能说递归是否有帮助，但我很欣赏非递归方法。 我敢打赌，它更难工作，也更难阅读，但它可能更高效，而且绝对非常聪明。 老实说，我没有详细分析该算法，但它看起来确实需要很长时间才能正常工作。 我敢打赌，你必须考虑很多 1 误差和奇怪的边缘情况，是吗？

考虑到所有这些，基本上我想做的就是通过用更惯用的 Python 主义替换大量的 C 主义来尽我所能地美化你的代码。 很多时候，在 C 中需要循环的事情可以在 Python 中用一行完成。 我还尝试重命名一些东西以更好地遵循 Python 命名约定，并清理了一些注释。 希望我的任何改变不会冒犯您。 你可以拿走你想要的，留下其余的。 :-)

以下是我工作时所做的笔记：

• 将初始化 tmp 为一堆 1 的代码更改为更惯用的 tmp = [1] * n_cells。
• 将对 tmp_sum 求和的 for 循环更改为惯用的 sum(tmp)。
• 然后将所有循环替换为 tmp =; + 一行。
• 将 raise didException 移至 init_tmp_new_ceiling 并删除了 succeeded 标志。
• init_tmp_new_ceiling 中的检查实际上似乎没有必要。 删除它后，剩下的唯一的 raise 位于 make_combos_n_cells 中，所以我只是将它们更改为常规返回，并完全删除 doneException 。
• 用于缩进的 4 个空格和 8 个空格的标准化混合。
• 删除了 if 条件周围不必要的括号。
• tmp[p2] - tmp[p1] == 0 与 tmp[p2] == tmp[p1] 相同。
• 将 while True: if new_ceiling_flag: break 更改为 while not new_ceiling_flag。
• 您不需要在函数顶部将变量初始化为 0。
• 删除了组合列表并更改了函数以在生成元组时生成其元组。
• 将 tmp 重命名为 combo。
• 已将 new_ceiling_flag 重命名为 ceiling_changed。

这是供您细读的代码：

def initial_combo(ceiling=5, target_sum=13, num_cells=4):
    """
    Returns a list of possible addends, probably to be modified further.
    Starts a new combo list, then, starting from left, fills items to ceiling
    or intermediate between 1 and ceiling or just 1.  E.g.:
    Given ceiling = 5, target_sum = 13, num_cells = 4: creates [5,5,2,1].
    """
    num_full_cells = (target_sum - num_cells) // (ceiling - 1)

    combo = [ceiling] * num_full_cells \
          + [1]       * (num_cells - num_full_cells)

    if num_cells > num_full_cells:
        combo[num_full_cells] += target_sum - sum(combo)

    return combo

def all_combos(ceiling, target_sum, num_cells):
    # p0   points at the rightmost item and moves left under some conditions
    # p1   starts out at rightmost items and steps left
    # p2   starts out immediately to the left of p1 and steps left as p1 does
    #      So, combo[p2] and combo[p1] always point at a pair of adjacent items.
    # d    combo[p2] - combo[p1]; immediate difference
    # cd   combo[p2] - combo[p0]; cumulative difference

    # The ceiling decreases by 1 each iteration.
    while True:
        combo = initial_combo(ceiling, target_sum, num_cells)
        yield tuple(combo)

        ceiling_changed = False

        # Generate all of the remaining combos with this ceiling.
        while not ceiling_changed:
            p2, p1, p0 = -2, -1, -1

            while combo[p2] == combo[p1] and abs(p2) <= num_cells:
                # 3,3,3,3
                if abs(p2) == num_cells:
                    return

                p2 -= 1
                p1 -= 1
                p0 -= 1

            cd = 0

            # slide_ptrs_left loop
            while abs(p2) <= num_cells:
                d   = combo[p2] - combo[p1]
                cd += d

                # 5,5,3,3 or 5,5,4,3
                if cd > 1:
                    if abs(p2) < num_cells:
                        # 5,5,3,3 --> 5,4,4,3
                        if d > 1:
                            combo[p2] -= 1
                            combo[p1] += 1
                        # d == 1; 5,5,4,3 --> 5,4,4,4
                        else:
                            combo[p2] -= 1
                            combo[p0] += 1

                        yield tuple(combo)

                    # abs(p2) == num_cells; 5,4,4,3
                    else:
                        ceiling -= 1
                        ceiling_changed = True

                    # Resume at make_combo_same_ceiling while
                    # and follow branch.
                    break

                # 4,3,3,3 or 4,4,3,3
                elif cd == 1:
                    if abs(p2) == num_cells:
                        return

                    p1 -= 1
                    p2 -= 1

if __name__ == '__main__':
    print list(all_combos(ceiling=6, target_sum=12, num_cells=4))

Answer 8

首先，我会使用有意义的变量名，以便代码易于理解。 然后，在我理解这个问题之后，这显然是一个递归问题，因为一旦你选择了一个数字，找到其余平方的可能值的问题是完全相同的问题，但具有不同的值。

所以我会这样做：

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    combos = []
    # The highest possible value of the next cell is whatever is 
    # largest of the max_val, or the target_sum minus the number 
    # of remaining cells (as you can't enter 0).
    highest = min(max_val, target_sum - n_cells + 1)
    # The lowest is the lowest number you can have that will add upp to 
    # target_sum if you multiply it with n_cells.
    lowest = int(ceil(target_sum/n_cells))
    for x in range(highest, lowest-1, -1):
        if n_cells == 1: # This is the last cell, no more recursion.
            combos.append((x,))
            break
        # Recurse to get the next cell:
        # Set the max to x (or we'll get duplicates like
        # (6,3,2,1) and (6,2,3,1), which is pointless.
        # Reduce the target_sum with x to keep the sum correct.
        # Reduce the number of cells with 1.
        for combo in make_combos(x, target_sum-x, n_cells-1):
            combos.append((x,)+combo)
    return combos

if __name__ == '__main__':
    import pprint
    # And by using pprint the output gets easier to read
    pprint.pprint(make_combos( 6,12,4))

我还注意到你的解决方案似乎仍然有问题。 对于值 max_val=8、target_sum=20 和 n_cells=5，您的代码找不到解决方案 (8,6,4,1,1,)，如下一个例子。 我不确定这是否意味着我错过了这方面的规则，但据我了解，这应该是一个有效的选项。

这是一个使用生成器的版本，如果值确实很大，它可以节省几行和内存，但作为递归，生成器可能很难“获取”。

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    highest = min(max_val, target_sum - n_cells + 1)
    lowest = int(ceil(target_sum/n_cells))
    for x in xrange(highest, lowest-1, -1):
        if n_cells == 1:
            yield (x,)
            break
        for combo in make_combos(x, target_sum-x, n_cells-1):
            yield (x,)+combo

if __name__ == '__main__':
    import pprint
    pprint.pprint(list(make_combos( 6,12,4)))

Answer 9

这是我能想到的最简单的递归解决方案，“找到 n 个数字与 x 值的所有可能组合，使得 1 <= x <= max_val 且 x(1) + ... + x(n) = target” 。 我正在从头开始开发它。 这是一个根本没有任何优化的版本，只是为了简单起见：

def apcnx(n, max_val, target, xsofar=(), sumsofar=0):
  if n==0:
    if sumsofar==target:
      yield xsofar
    return

  if xsofar:
    minx = xsofar[-1] - 1
  else:
    minx = 0

  for x in xrange(minx, max_val):
    for xposs in apcnx(n-1, max_val, target, xsofar + (x+1,), sumsofar+x+1):
      yield xposs

for xs in apcnx(4, 6, 12):
  print xs

基本情况 n==0 （我们无法产生更多数字）如果满足条件，则产生到目前为止的元组，或什么都不做，然后完成（返回）。

如果我们应该生成比迄今为止构建的更长的元组，则 if/else 确保我们只生成非递减元组，以避免重复（您确实说的是“组合”而不是“排列”）。

for 尝试“this”项的所有可能性，并循环遍历下一个较低级别的递归仍然能够产生的结果。

我看到的输出是：

(1, 1, 4, 6)
(1, 1, 5, 5)
(1, 2, 3, 6)
(1, 2, 4, 5)
(1, 3, 3, 5)
(1, 3, 4, 4)
(2, 2, 2, 6)
(2, 2, 3, 5)
(2, 2, 4, 4)
(2, 3, 3, 4)
(3, 3, 3, 3)

这似乎是正确的。

有无数种可能的优化，但是请记住：

首先使其正常工作，然后使其快速

我与 Kent Beck 通信，在“Python in a Nutshell”中正确地引用了这句话，他告诉我这是从他父亲那里得到的，他的工作实际上与编程无关;-)。

在这种情况下，在我看来，关键问题是理解正在发生的事情，任何优化都可能会产生干扰，所以我会全力以赴“简单易懂”； 如果需要的话，一旦OP确认他们可以理解这个纯粹的、未经优化的版本中发生了什么，我们就可以对其进行优化！