python - 是否可以使用python解决难题?
问题描述
谜题
我试图用下面的程序解决难题。这是一个 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)
解决方案
以下代码使用回溯算法在 i7 CPU 920 @ 2.67 MHz 的 Windows 10 PC 上大约 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
解释
尝试所有长度为 16 的数字的 multiset_permutations 是不可行的,因为数量太多(即 16^16 = 2^64 ~ 18e18)。
想法是创建大小增加的数组(即长度为 0 到 16),但如果数组不满足条件(即回溯),则提前中止。
为了能够提前中止(即回溯),我们:
- 拆分条件,以便我们可以根据数组的大小应用(即条件函数)
- 我们添加了一个数字可以被另一个数字整除的条件(即,如果我们有 x/y,那么我们需要 x % y == 0)
- 我们始终使用整数除法(即 x // y)
推荐阅读
- apache-kafka - Kafka Connect JDBC 在 JsonConverter 上失败
- java - Java while 函数仅每 1 秒
- ios - 如何快速将字符串“One”的字符转换为整数“1”
- cognos - 在 Cognos 10.2.1 中动态更改报表名称的 pdf 导出
- android - 使用 Dagger2、Espresso 和 Mockito 对 MVVM 架构进行 Android UI 测试
- angular - 以角度 7 显示异步数据
- python-3.x - 根据另一列的数据计算 csv 文件中某一列的值
- c# - C#:为列表框项创建第二个标识符
- module - SystemVerilog 接口 - 模块声明后传递参数
- javascript - 为什么不调用带有 { query: true } 的 mongoose 中间件“pre”remove?