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: 
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.
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