<p>除了输入错误,如果只在内部循环中测试所有10位数字是否不同,则此内部循环执行10次<sup>10</sup>=1000000000次。如果你每次通过考试,你“只”需要10分3628800次传递到此内部循环</p>
<p>您仍然可以更好地更改变量的顺序,因此方程<code>abc * d == hibj</code>可以在不需要其他3个变量的情况下进行测试,并且只有在它成立时才能进行更深入的测试。对于这7位数字,您在该循环中输入604800次,只需再输入45次,就可以到达最内部的循环270次</p>
<pre class="lang-py prettyprint-override"><code>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')
</code></pre>
<p>尽管它现在运行速度足够快,但仍可以考虑进行更具体的优化:</p>
<ul>
<li>将顺序更改为<code>a,b,c</code>和<code>h,i,j</code>,然后计算<code>hibj</code>是否是<code>abc</code>的倍数。只有在这种情况下,它才定义了<code>d</code>,它应该介于<code>0</code>和<code>9</code>之间,并且与其他部分不同</李>
<li>或者,相反:生成<code>a,b,c,d</code>,然后首先尝试所有倍数,看它们是否适合<code>b</code>,然后看相应的<code>h,i,j</code>是否彼此不同,是否与<code>a,b,c,d</code>不同</李>
<li><code>h</code>应小于<code>a</code>,否则<code>d</code>将大于<code>9</code>。这使得<code>a</code>至少<code>1</code></李>
<li>通常在这类问题中,每个数字的第一个数字都应该是非零的,这可以进一步减少检查的次数</李>
</ul>
<p>另一种方法是使用<a href="https://en.wikipedia.org/wiki/Satisfiability_modulo_theories" rel="nofollow noreferrer">SMT/SAT</a>解算器,如<a href="https://ericpony.github.io/z3py-tutorial/guide-examples.htm" rel="nofollow noreferrer">Z3</a>。有了这样一个解算器,所有的条件都被公式化,并且通过各种启发式方法来寻找解决方案。示例代码:<a href="https://ericpony.github.io/z3py-tutorial/advanced-examples.htm" rel="nofollow noreferrer">here</a>和<a href="https://yurichev.com/writings/SAT_SMT_by_example.pdf" rel="nofollow noreferrer">here</a></p>
<p>这就是代码的样子:</p>
<pre class="lang-py prettyprint-override"><code>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]))
</code></pre>
<p>这将输出<code>a=9, b=3, c=4, d=7, e=2, f=1, g=0, h=6, i=5, j=8</code>作为唯一的解决方案</p>