Solving problems in Python

Question

I currently have the following, both of which must hold true:

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

I C J * E = A B C D

Each letter represents a unique digit from 0 to 9 and both equations must hold true. I need to write a Python solution which outputs the correct answer, here is my code:

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())

However, when I run this, not only does it take a while to run, it outputs "None". Any ideas as to where I am going wrong?

Note that you have written defg = 1000 * d + 100 * e + 10 * f + g wrong. You wrote 100 + e — JohanC
– JohanC, Commented Jul 15, 2020 at 10:59

Phoenixo · Accepted Answer · 2020-07-15 12:36:39Z

You should try for x in range(0, 10) instead of for x in range(0,9) because you were looping from 0 to 8

If you want to loop in a more efficient way, you can use 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)

Result :

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

Here is the final code :

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()

Output :

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

JohanC · Accepted Answer · 2020-07-15 15:26:15Z

Apart from the typos, if you only test in the very inner loop whether all 10 digits are different, this inner loop is executed 10¹⁰ = 10,000,000,000 times. If you test at every pass, you "only" need 10! = 3,628,800 passes to this inner loop.

You still can do better changing the order of variables, so the equation abc * d == hibj can be tested without needing the other 3 variables, and only go deeper when it holds. For these 7 digits, you enter 604,800 times in that loop, and only 45 times you need to go deeper to reach the most inner loop only 270 times.

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')

Although it now runs fast enough, still more specific optimizations can be thought of:

Change the order to a,b,c and h,i,j then calculate whether hibj is a multiple of abc. Only in case it is, this defines d which should be between 0 and 9, and different from the rest.
Or, the reverse: generate a,b,c,d and then try all the multiples first whether they fit b and then whether the corresponding h,i,j are different from each other and different from a,b,c,d.
h should be smaller than a, otherwise d will be larger than 9. This makes a at least 1.
Usually in this kind of problems, the first digit of every number is supposed to be non-zero, which can further reduce the number of checks.

An alternative approach, is to use an SMT/SAT solver such as Z3. With such a solver, all the conditions are formulated, and via all kind of heuristics a solution is searched for. Example codes: here and here.

This is how the code could look like:

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]))

This prints out a=9, b=3, c=4, d=7, e=2, f=1, g=0, h=6, i=5, j=8 as unique solution.

Thank you very much, definitely helped and has given me a few things to focus on

Collectives™ on Stack Overflow

Solving problems in Python

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related