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.
12 seconds is too much for my taste. My C++ brute force attack took ~430ms without any heuristics or deep optimizations. Anyway you need to add some heuristics for example:

**Bitwidth of multiplication result is around the sum of bitwidth of the operands.**

So you need to test only the same bit width combinations of the results. for example if `a*b` are like this:

```
1xx * 9x dec = 1 xxxx xxxx * 1001 xxxx bin -> 17 bit

```

so test only `c*d` combinations that lead to 17 bit results too for example

```
4xx * 2x dec = 100 xxxx xxxx * 10 xxxx bin -> 17 bit

```

to make it more clear:

```
dec  bin bits
 0  0000  0
 1  0001  1
 2  0010  2
 3  0011  2
 4  0100  3
 5  0101  3
 6  0110  3
 7  0111  3
 8  1000  4
 9  1001  4

```

If highest digit of `a,b,c,d` is `a0,b0,c0,d0` then:

```
bits(a0)+bits(b0) = bits(c0)+bits(d0)

```

This will eliminate a lot of iterations. It is similar to subset sum problem. The speed up is from `2177280` iterations to `420480` iterations but also adds some overhead.