Question: In a [science museum in Norway](https://nordnorsk.vitensenter.no/) I came across the following mathematical game:

[![enter image description here](https://i.stack.imgur.com/aBECB.jpg)](https://i.stack.imgur.com/aBECB.jpg)

The goal is to place the 10 digits from 0 to 9 such that the difference between the two products is nearest to zero. (The 246 is the current lowest score).

Back home I wrote the following brute-force code:

```
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

```

If we don't allow leading zeroes, then this prints 128 possible solutions in about 12 seconds.

But I'm left wondering, is there an algorithm or a better way to solve this in a non-brute force way?

Answer: 
If you assume there is a solution with difference 0, you can do via prime factors.

If a*b - c*d = 0, then the prime factors of a*b and c*d must be the same. You can start the search by going through all 3-digit primes (there are only 143) and see whether they have a multiple that only contains disjunctive digits. If this is the case you have your 2 three-digit numbers and only have to check the 2-digit ones.

If you don't find a solution, continue with the 2-digit primes and look for 2-or-3-digit multiples with disjunct digits. Then you only have to do the permutations for the remaining 2 numbers, which is a lot less.
As a heuristic you could compute the square root of 12345 (about 111) and go on from there, searching for the nearest values to 123 and 45 which you can create with the remaining numbers. I did not implement this but it could be a more intelligent approach.

Another example:

sqrt(36189) -> About 190

Remaining numbers: 24570

Try to find numbers close to 190 which you can create with these numbers. Such as 70 and 245. This should however be harder to implement.

Distance between 361 \* 89 and 245 \* 70: 14979