是否可以使用 python 来解决这个难题？

Question

拼图

我试着用下面的程序来解决这个难题。这是一个 4x4 交叉数学拼图。有什么办法可以快速解决

def puzzleTwo (a):   
 if(a[0] + a[1] - a[2] + a[3] == 19):
  #print ("1 equation Success")
  if(a[4] - a[5] - a[6] - a[7] == -31):
   #print ("2 equation Success")
   if(a[8] - a[9] / a[10] + a[11] == 8):
    #print ("3 equation Success")
    if(a[12] - a[13] / a[14] + a[15] == 1):
     #print ("4 equation Success")
     if(a[0] + a[4] + a[8] + a[12] == 23):
      #print ("5 equation Success")
      if(a[1] - a[5] + a[9] - a[13] == -3):
       #print ("6 equation Success")
       if(a[2] - a[6] / a[10] + a[14] == 5):
        #print ("7 equation Success")
        if(a[3] + a[7] - a[11] + a[15] == 22):
         print (a)
 return
 
from sympy.utilities.iterables import multiset_permutations
import numpy as np
a = np.array([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16])
for p in multiset_permutations(a):
    puzzleTwo(p)

Answer 1

以下代码使用 backtracking algorithm 在 Windows 10 PC with i7 CPU 920 @ 2.67 MHz

上约 3 分钟内找到解决方案

代码

def condition(a):
    ' Apply conditions individually to allow immediate backtracking when a condition is not met '
    if len(a)==4:
        return (a[0] + a[1] - a[2] + a[3]) == 19
    elif len(a) == 8:
        return (a[4] - a[5] - a[6] - a[7]) == -31
    elif len(a) == 11:
        return (a[6] % a[10]) == 0 and (a[9] % a[10]) == 0
    elif len(a)==12:
        return (a[8] - a[9] // a[10] + a[11]) == 8
    elif len(a) == 13:
        return (a[0] + a[4] + a[8] + a[12]) == 23
    elif len(a) == 14:
        return (a[1] - a[5] + a[9] - a[13]) == -3
    elif len(a) == 15:
        return (a[2] - a[6] // a[10] + a[14]) == 5 and (a[13] % a[14]) == 0
    elif len(a) == 16:
        return (a[3] + a[7] - a[11] + a[15]) == 22 and (a[12] - a[13] // a[14] + a[15]) == 1
    
    elif len(a) > 16:
        return False  # array exceeds max length
    else:
        return True   # not one of the lengths to try conditions

def solve(answer = None):
    ' Uses backtracking to find solve 4x4 math grid problem '
    if answer is None:
        answer = ()
        
    if condition(answer):
        # satisfies conditions so far
        if len(answer) == 16:
            # satisfies all conditions
            yield answer
        else:
            # Expand on solution since satisfies conditions so far
            for i in range(1, 17):
                # Try adding one of the numbers 1 to 17 to current answer
                yield from solve(answer + (i,))
        
from time import time

tstart = time()
print(f'Solution: {next(solve(), None))}') # get first solution
                                           # use list(solve()) to get all solutions
print(f'Elapsed time {time()-tstart}')

输出

Solution: (1, 6, 1, 13, 6, 14, 14, 9, 15, 16, 2, 1, 1, 11, 11, 1)
Elapsed time 189.32917761802673

说明

尝试所有 multiset_permutations 个长度为 16 的数字是不可行的，因为数量太多（即 16^16 = 2^64 ~ 18e18）。

想法是创建大小不断增加的数组（即 0 到 16 长度），但如果数组不满足条件（即回溯）则提前中止。

为了能够提前中止（即回溯），我们：

拆分条件，以便我们可以根据数组的大小（即条件函数）应用
我们添加一个条件，即一个数字可以被另一个数字整除（即如果我们有 x/y 那么我们需要 x % y == 0）
我们始终使用整数除法（即 x // y）

是否可以使用 python 来解决这个难题？

Is it possible to solve the puzzle using python?

python

puzzle

amazon-sagemaker