用Python解决问题

Question

我目前有以下两个条件，这两个条件都必须成立：

A B C D+A E F=E F G H和

I C J*E=A B C D

每个字母代表一个从0到9的唯一数字，两个方程都必须为真。 我需要编写一个输出正确答案的Python解决方案，以下是我的代码：

import numpy as np

def solve():
    for a in range(0,10):
        for b in range(0,10):
            for c in range(0,10):
                for d in range(0,10):
                    for e in range(0,10):
                        for f in range(0,10):
                            for g in range(0,10):
                                for h in range(0,10):
                                    for i in range(0,10):
                                        for j in range(0,10):
                                            if len(set([a, b, c, d, e, f, g, h, i, j])) == 10:
                                                icj = 100*i + 10*c + j
                                                e = e
                                                abcd = 1000*a + 100*b + 10*c + d
                                                aef = 100*a + 10*e + f
                                                efgh = 1000*e + 100*f + 10*g + h
                                                if icj * e == abcd and abcd + aef == efgh:
                                                    print(icj, e, abcd, aef, efgh)
print(solve())                                               

然而，当我运行它时，它不仅需要运行一段时间，而且还输出“无”。你知道我错在哪里吗

Answer 1

您应该尝试for x in range(0, 10)而不是for x in range(0,9)，因为您正在从0循环到8

如果希望以更有效的方式循环，可以使用permutations：

from itertools import permutations
for a, b, c, d, e, f, g, h, i, j in permutations(range(0, 10), 10):
    print(a, b, c, d, e, f, g, h, i, j)

结果:

0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 9 8
...
9 8 7 6 5 4 3 2 0 1
9 8 7 6 5 4 3 2 1 0

这是最后的代码：

import numpy as np
from itertools import permutations

def solve():
    for a, b, c, d, e, f, g, h, i, j in permutations(range(0, 10), 10):
        icj = 100*i + 10*c + j
        e = e
        abcd = 1000*a + 100*b + 10*c + d
        aef = 100*a + 10*e + f
        efgh = 1000*e + 100*f + 10*g + h
        if icj * e == abcd and abcd + aef == efgh:
            print(icj, e, abcd, aef, efgh)
            print(a, b, c, d, e, f, g, h, i, j)

solve()

输出：

934 7 6538 672 7210
6 5 3 8 7 2 1 0 9 4

Answer 2

除了输入错误，如果只在内部循环中测试所有10位数字是否不同，则此内部循环执行10次¹⁰=1000000000次。如果你每次通过考试，你“只”需要10分3628800次传递到此内部循环

您仍然可以更好地更改变量的顺序，因此方程abc * d == hibj可以在不需要其他3个变量的情况下进行测试，并且只有在它成立时才能进行更深入的测试。对于这7位数字，您在该循环中输入604800次，只需再输入45次，就可以到达最内部的循环270次

def solve():
    for a in range(0, 10):
        for b in range(0, 10):
            if a != b:
                for c in range(0, 10):
                    if not c in [a, b]:
                        for d in range(0, 10):
                            if not d in [a, b, c]:
                                for h in range(0, 10):
                                    if not h in [a, b, c, d]:
                                        for i in range(0, 10):
                                            if not i in [a, b, c, d, h]:
                                                for j in range(0, 10):
                                                    if not j in [a, b, c, d, h, i]:
                                                        abc = 100 * a + 10 * b + c
                                                        hibj = 1000 * h + 100 * i + 10 * b + j
                                                        if abc * d == hibj:
                                                            print(abc, '*', d, '=', hibj)
                                                            for e in range(0, 10):
                                                                if not e in [a, b, c, d, h, i, j]:
                                                                    for f in range(0, 10):
                                                                        if not f in [a, b, c, d, h, i, j, e]:
                                                                            for g in range(0, 10):
                                                                                if not g in [a, b, c, d, h, i, j, e, f]:
                                                                                    hde = 100 * h + 10 * d + e
                                                                                    defg = 1000 * d + 100 * e + 10 * f + g
                                                                                    if hibj + hde == defg:
                                                                                        print(abc, d, hibj, hde, defg)

solve()
print('done')

尽管它现在运行速度足够快，但仍可以考虑进行更具体的优化：

• 将顺序更改为a,b,c和h,i,j，然后计算hibj是否是abc的倍数。只有在这种情况下，它才定义了d，它应该介于0和9之间，并且与其他部分不同
• 或者，相反：生成a,b,c,d，然后首先尝试所有倍数，看它们是否适合b，然后看相应的h,i,j是否彼此不同，是否与a,b,c,d不同
• h应小于a，否则d将大于9。这使得a至少1
• 通常在这类问题中，每个数字的第一个数字都应该是非零的，这可以进一步减少检查的次数

另一种方法是使用SMT/SAT解算器，如Z3。有了这样一个解算器，所有的条件都被公式化，并且通过各种启发式方法来寻找解决方案。示例代码：here和here

这就是代码的样子：

from z3 import Int, And, Or, Distinct, Solver, sat

D = [Int(f'{c}') for c in "abcdefghij"]
a, b, c, d, e, f, g, h, i, j = D
vals_0_to_9 = [And(Di >= 0, Di <= 9) for Di in D]
all_different = [Distinct(D)]

abc = 100 * a + 10 * b + c
hibj = 1000 * h + 100 * i + 10 * b + j
hde = 100 * h + 10 * d + e
defg = 1000 * d + 100 * e + 10 * f + g
equations = [abc * d == hibj, hibj + hde == defg]

s = Solver()
s.add(vals_0_to_9 + all_different + equations)
while s.check() == sat:
    m = s.model()
    print(", ".join([f'{Di}={m[Di]}' for Di in D]))
    s.add(Or([Di != m[Di] for Di in D]))

这将输出a=9, b=3, c=4, d=7, e=2, f=1, g=0, h=6, i=5, j=8作为唯一的解决方案