最接近零的两种产品之间的差异:非强力解决方案？

Question

在挪威的一个科学博物馆,我遇到了以下数学游戏:

目标是将10位从0到9放置,使得两个乘积之间的差异最接近零.(246是目前的最低分).

回到家里,我写了以下蛮力代码:

import time
from itertools import permutations


def form_number(x, y, z, a, b):
    # not explicitly stated, but presume that leading zeroes are not allowed
    if x == 0 or a == 0:
        return 0
    return ((100 * x) + (10 * y) + z) * ((10 * a) + b)

def find_nearest_zero(*args):
    assert len(args) == 10
    return form_number(*args[:5]) - form_number(*args[5:])

if __name__ == '__main__':
    start = time.time()
    count = 0
    for p in permutations(range(10), 10):
        result = find_nearest_zero(*p)
        if result == 0:
            count += 1
            print '{}{}{} * {}{} = {n}'.format(*p[:5], n=form_number(*p[:5]))
            print '{}{}{} * {}{} = {n}'.format(*p[5:], n=form_number(*p[5:]))
            print
    print 'found {} solutions'.format(count)
    print time.time() - start

如果我们不允许前导零,那么这将在大约12秒内打印出128种可能的解决方案.

但我想知道,是否有一种算法或更好的方法以非暴力方式解决这个问题？

Answer 1

作为一种启发式方法，您可以计算 12345（大约 111）的平方根，然后从那里继续搜索最接近 123 和 45 的值，您可以使用剩余的数字创建这些值。我没有实现这个，但这可能是一种更智能的方法。

另一个例子：

sqrt(36189) -> 约 190

剩余数量：24570

尝试找到接近 190 的数字，您可以用这些数字创建它们。例如 70 和 245。但这应该更难实现。

361 * 89 和 245 * 70 之间的距离：14979