Блог

Головоломка

Я попытался решить головоломку с помощью приведенной ниже программы. Это математическая головоломка 4×4. Есть ли какой-нибудь способ быстро решить

 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)
  

Следующий код использует алгоритм обратного отслеживания, чтобы найти решение за ~ 3 минуты на ПК с Windows 10 с процессором i7 920 @ 2,67 МГц

Код

 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)