如何暴力破解算术题？

Question

朋友分享了这个谜题：

How to make 21 from the numbers 1, 5, 6, 7?

You can use the operations of addition, subtraction, multiplication and division, as well as brackets. You must use each number once.

我最终在纸上解决了——两天后。毫无疑问，计算机可以在一秒钟内暴力破解所有解决方案。

不过呢？我尝试生成所有字符串 a.b.c.d 插入字母的数字和点的操作，但它错过了我的解决方案。

奖金谜题：

如何将 1,5,6,7 变成 11？
如何将 1,5,6,7 变成 16？

Answer 1

一个明显的方法是：

您从一个包含四个数字的向量 S 开始：S = ( 1, 5, 6, 7 )
从S中选择任意两个a和b，从S
对a和b应用任意算术运算，从而得到一个新数c（注意避免被零除并验证精确除法，如果问题需要它)
将c包含在S中，得到S'
从第 1 步继续，现在使用 S' 代替 S

在第2步（选择两个数字）和第3步（选择操作）进行暴力分支。应该重复该循环，直到 S 减少到只有 1 个元素，这是该特定蛮力分支的结果。

括号未明确使用，但隐含存在。

如果 S 中的一个分支以 21 结束，则您有一个解决方案，此时您可以终止，或继续分支以搜索其他解决方案。

Answer 2

这是 AnT 建议的 "pop two, combine, recurse" 算法，编码在 Python 中。最难的部分是在递归之后组装表达式。我使用了查找和替换。

#!python
import operator
import itertools
from fractions import Fraction

operations = dict()
operations['+'] = operator.add
operations['-'] = operator.sub
operations['/'] = operator.truediv
operations['*'] = operator.mul

def solve(target, numbers):
    """List ways to make target from numbers."""
    numbers = [Fraction(x) for x in numbers]
    return solve_inner(target, numbers)

def solve_inner(target, numbers):
    if len(numbers) == 1:
        if numbers[0] == target:
            yield str(target)
        return

    # combine a pair of numbers with an operation, then recurse
    for a,b in itertools.permutations(numbers, 2):
        for symbol, operation in operations.items():
            try:
                product = operation(a,b)
            except ZeroDivisionError:
                continue

            subnumbers = list(numbers)
            subnumbers.remove(a)
            subnumbers.remove(b)
            subnumbers.append(product)

            for solution in solve_inner(target, subnumbers):
                # expand product (but only once)
                yield solution.replace(str(product), "({0}{1}{2})".format(a, symbol, b), 1)

if __name__ == "__main__":
    numbers = [1, 5, 6, 7]
    target = 21
    solutions = solve(target, numbers)
    for solution in solutions:
        print("{0}={1}".format(target, solution))

三个谜题的解法：

>>> solve(21,[1,5,6,7])
6/(1-(5/7))
>>> solve(11,[1,5,6,7])
(6*(7-5))-1
((7-5)*6)-1
>>> solve(16,[1,5,6,7])
[]

(第三题不可能)

如何暴力破解算术题？

How to brute force arithmetic puzzle?

algorithm

math