Summel 介绍
Summel 是一个规则很简单的数字游戏，官网即有规则/玩法介绍。简单来说，就是给定 6 个已知数字和 1 个目标数字，要在有限（最多 5 次）的初等数学运算（加减乘除，且计算后不能出现非正整数）中，通过计算得到目标数字。
基本思路
虽然这是一个数字游戏，可能也有一些比较深的数学知识能够解决或者辅助解决，但是使用计算机来解决这个问题的思路其实还是一个力大砖飞：
由于给出的已知数字只有 6 个，所以实际上全部的排列组合是非常有限的。因此完全可以暴力穷举所有的组合，然后找出满足条件的组合。
优化
单纯的穷举虽然肯定可以得到结果，但是实际上仍然会比较慢，因此需要考虑优化。
首先可以注意到，我们可以将排列组合和计算同时进行，这样当计算到一些不符合要求的运算时（出现非正整数），可以直接跳过（类似于机器学习的剪枝操作）。在这种优化思路下，能够大大减少各种排列情况，因为减法 A-B 和 B-A 两者能够排除一种（A=B 时例外），而除法更是在大部分情况下均会出现非正整数。
因此，考虑使用递归方式来进行穷举，以实现在穷举过程中的剪枝操作。
具体实现
代码及注释见下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
# Summel Solver
# 给定的数字
numbers = [4, 5, 25, 50, 75, 100]
# 目标数字
target = 459
# 可用的运算符
operators = ["+", "-", "*", "/"]
# 最终的结果
results = []
# 递归函数，根据当前的数字/计算式列表进行组合，生成所有可能的表达式
def generate_expressions(nums):
"""
递归函数，生成所有可能的表达式
:param nums: 当前的数字/计算式列表（字符串），可能为数字（"4")，也可能为表达式（"(4+5)")
:return: None
"""
# 根据经验，一般的 summel 问题最少在 4 次运算时就可以得到目标值，此时列表可能为“1 个数字”+“5 个数字组成的计算式”
# 所以在列表长度小于等于 2 时进行运算判断是否满足目标值，以覆盖 4 次运算的情况和 5 次运算的情况
if len(nums) <= 2:
# 计算当前列表中的计算式是否满足目标值
for num in nums:
# todo：此处其实还有优化空间，列表长度小于等于 2 时我们实际仅需要“1 个数字”+“5 个数字组成的计算式”这种情况
# 而 2+4、3+3 的情况下，获取到目标值的概率很小（正常难度下），可以不用进行运算直接跳过
# 当然为了兼容一些比较简单的难度，还是保持现状，目前的执行时间大部分情况下能够接受
try:
if eval(num) == target:
# 满足目标值，将结果添加到答案列表中
results.append(num)
except ZeroDivisionError:
# 除法出现除数为 0 的情况，跳过
# 理论上不会出现，因为仅有减法操作后会出现 0 ，而下面在减法操作时已将得出 0 的结果跳过
pass
# 列表中有 2 个以上的数字/表达式时，通过循环遍历所有“取出两个数字/表达式”并进行计算的操作
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
for op in operators:
# 除法的特殊处理
if op == "/":
try:
# 判断计算结果是否为自然数，若为自然数则将取出的两个数字/计算式组成一个新的计算式
# 修改列表：移除这两个数字/表达式，将新的计算式添加到列表中
# 进行进一步的递归
# todo: 此处可以优化，因为 A!=B 的情况下 A/B 和 B/A 不可能都为正整数，而 A==B 的情况下也不需要交换顺序计算
if eval(f"({nums[i]} {op} {nums[j]})") % 1 == 0:
new_nums = nums[:i] + nums[i + 1 : j] + nums[j + 1 :]
new_nums.append(f"({nums[i]} {op} {nums[j]})")
generate_expressions(new_nums)
if eval(f"({nums[j]} {op} {nums[i]})") % 1 == 0:
new_nums = nums[:i] + nums[i + 1 : j] + nums[j + 1 :]
new_nums.append(f"({nums[j]} {op} {nums[i]})")
generate_expressions(new_nums)
except ZeroDivisionError:
# 除法出现除数为 0 的情况，跳过
# 同上
continue
# 减法特殊处理
elif op == "-":
# 判断计算结果是否大于 0，若大于 0 则将取出的两个数字/表达式组成一个新的计算式
# 修改列表：移除这两个数字/表达式，将新的计算式添加到列表中
# 进行进一步的递归
# todo: 此处可以优化，同样可以仅判断一个分支
if eval(f"({nums[i]} {op} {nums[j]})") > 0:
new_nums = nums[:i] + nums[i + 1 : j] + nums[j + 1 :]
new_nums.append(f"({nums[i]} {op} {nums[j]})")
generate_expressions(new_nums)
if eval(f"({nums[j]} {op} {nums[i]})") > 0:
new_nums = nums[:i] + nums[i + 1 : j] + nums[j + 1 :]
new_nums.append(f"({nums[j]} {op} {nums[i]})")
generate_expressions(new_nums)
# 加法和乘法不会得到非正整数且考虑满足交换律，无须特殊处理或交换顺序
else:
new_nums = nums[:i] + nums[i + 1 : j] + nums[j + 1 :]
new_nums.append(f"({nums[i]} {op} {nums[j]})")
generate_expressions(new_nums)
# 初始化，将数字列表转换为字符串列表，作为初始的计算式列表
initial_exprs = list(map(str, numbers))
# 开始递归
generate_expressions(initial_exprs)
# 输出结果
if results:
for result in results:
# 将全部结果输出，便于找到运算次数最少的结果
print(f"Found solution: {result} = {target}")
else:
print("No solution found")
|
执行下来基本上一分钟之内能够出结果，并且能够兼容特殊模式（比如目标数字为 10，给出 5 个数字，要求使用到全部数字）