如何优化所有4x4“幻方”的递归置换算法

Question

“幻方”由一个n x n矩阵组成，其中行、列和对角线都等于一个常数。对于4 x 4的幻方，这个常数是34。我正在尝试优化我的置换算法，它目前列出了所有可能的4x4矩阵，使用的数字范围从1到16，如果当前矩阵不符合幻方标准，则跳过某些排列。

我已经有了用来置换所有组合的递归算法。此函数接受长度为16的数组，该数组代表正方形，并打印符合“魔术”标准的所有可能组合。不过，我不确定如何在递归调用中实现检查来优化它。例如，我希望它是这样的:如果矩阵的第一行的总和不是34，则跳过该排列并继续下一个排列(对于前面的行，依此类推)。

def permute(a, lo, hi):
    if(lo == hi) and (isMagic(a)):
        print(a)
    else:
        for i in range(lo, hi):
            # this is where I imagine the exceptions would be made
            a[lo], a[i] = a[i], a[lo]
            permute4(a, lo + 1, hi, count, n)
            a[lo], a[i] = a[i], a[lo]

当删除"isMagic“检查时，它只是打印所有的组合，包括那些不是”魔法“的组合，函数打印正方形需要很长的时间。我最终想通过排除不必要的排列来加速这一过程。我该如何实现这个检查？

Answer 1

诀窍是依赖于已经生成的单元格。例如，您永远不需要生成4个元素的排列，因为您知道它们的总和是34，因此即使是第一行中的第四个元素也必须是34-sum(first 3 elements)。如果这样元素从来不存在(如1,2,3,28)，或已在使用(如1,3,15,15)，则尝试将不起作用，您可以继续下一个元素，而不生成表的其余部分。实际上，前两个元素已经可以为剩下的元素创建一个上限/下限，例如，1,2意味着剩下的两个元素将是15和16。可以预先生成/过滤所有具有34之和的各个排列，并基于方块中已有的排列来选择候选排列。

另一个技巧与此相关:如果你总是生成行，你总是尝试很多东西，3+1全新的元素。但是，如果您在有一行之后生成一个列，那么您将只处理两个元素的排列(因为第一个元素是已知的，而最后一个元素是计算出来的)。

示例实现(无预生成)：

import itertools,time

def check(attempt):
  for i in range(0,4):
    if sum(attempt[i*4:i*4+4]) != 34:
      return False
    if sum(attempt[i+j*4] for j in range(0,4)) != 34:
      return False
  if sum(attempt[i+i*4] for i in range(0,4)) != 34:
    return False
  if sum(attempt[3-i+i*4] for i in range(0,4)) != 34:
    return False
  return True

def row(pos,field,rest):
  base=34-sum(field[pos*4:pos*4+pos])
  for p in itertools.permutations(rest,3-pos):
    r=base-sum(p)
    s=rest-set(p)
    if r in s:
      for i in range(pos,3):
        field[pos*4+i]=p[i-pos]
      field[pos*4+3]=r
      column(pos,field,s-{r})

count = 0

def column(pos,field,rest):
  if len(rest) == 0:
    if check(field):
      global count
      count+=1
      print("{} {}".format(count,field))
    return
  base=34-sum([field[pos+4*i] for i in range(0,pos+1)])
  for p in itertools.permutations(rest,2-pos):
    r=base-sum(p)
    s=rest-set(p)
    if r in s:
      for i in range(pos+1,3):
        field[pos+i*4]=p[i-pos-1]
      field[pos+4*3]=r
      row(pos+1,field,s-{r})

start=time.time()

row(0,[0]*16,set(range(1,17)))

print(time.time()-start)

它在1-2分钟内生成7040个解决方案(在我的机器上是61秒，但这是一个相对较新的解决方案)。这可能是正确的，因为880期望唯一的解决方案，但这段代码也会生成旋转和镜像的正方形(7040=8*880)。

实际上，check()的实现过于谨慎:由于生成方法的原因，检查对角线就足够了(可以删除具有两个if-s的for循环)。