Zero sum game 16 bit version

Question

1. Preface

A common brainteaser is to fill in the spaces below using 0..9exactly once, in such a way that the sum is minimized.

  xxx*xx
- xxx*xx
= 

One solution is 408 x 37 - 296 x 51 = 0. However this problem can easilly be bruteforced since there are only 10! = 3.6*10^6 permutations of numbers. I have written a simple code to solve this problem posted below.

2. The 16byte problem

A similar but much harder problem is to do the same as above with the hexidecimal number system. Use the numbers 0...F exactly once such that

  xxxx * xxx
- xxxx * xxx
= 

is minimized. I have only found two solutions here.

   FD906 x 5A1
 - 7EC83 x B42
 =  0

   FD906 x 15A
 - 7EC83 x 2B4
 = 0

3. Question

Does there exists a more clever way to shuffle through the permutations and find the zero solution? The problem is that there are too many permutations to bruteforce now.

4. Attempt

For the 16bit number system there exists 3.5 * 10^14 in comparison to only 3.6 * 10^6 for the base 10 version. So a plain bruteforce solution would takes ages upon ages. My first attempt was to split the list of numbers into two groups

[14, 13, 10, 9, 6, 5, 2, 1] [15, 12, 11, 8, 7, 4, 3, 0]

The first group is the first product and the second is the second product. The way those lists were created was using a greedy sort and both sum to 60. This should give a higher theoretical chance of being equal. Number of permutations to iterate through is now 8! * 8! = 1.6*10^9. A lot better but still about 150 times larger than the base 10 version.

Any tips of a faster way is much appreaciated.

Base10 version

from itertools import permutations

def find_sum_equal_n():
    n = 0
    num = range(10)
    solutions = set()
    for perm in permutations(num):
        tple = product_sum(perm)
        if product_num(tple) == n:
            tple = well_ordered(tple)
            solutions.add(tple)
    return list(solutions)

def product_num(tple):
    total = tple[0]*tple[1] - tple[2]*tple[3]
    return total

def product_sum(perm):
    num1 = 100*perm[0] + 10*perm[1] + perm[2]
    num2 = 10*perm[3] + perm[4]
    num3 = 100*perm[5] + 10*perm[6] + perm[7]
    num4 = 10*perm[8] + perm[9]
    return (num1, num2, num3, num4)

def well_ordered(tple):
    a = max(tple[0], tple[1])
    b = min(tple[0], tple[1])

    c = max(tple[2], tple[3])
    d = min(tple[2], tple[3])

    if a > c:
        tple = (a,b,c,d)
    else:
        tple = (c,d,a,b)
    return tple


def display_solutions(lst):
    print '============================================'
    for solution in lst:
        display_sum(solution)
        print '============================================'


def display_sum(tple):
    print '   ' + str_num(tple[0], 3) + ' x ' + str_num(tple[1], 2)
    print ' - ' + str_num(tple[2], 3) + ' x ' + str_num(tple[3], 2)
    print ' = ', product_num(tple) 


def str_num(num, length):
    str_num = str(num)
    diff = max(length - len(str_num), 0)
    string = ' '*diff
    string += str_num
    return string

if __name__ == '__main__':

    lst = find_sum_equal_n()
    display_solutions(lst)
    print len(lst)

Base16 version

from itertools import permutations

def find_sum_equal_n_16bit():
    solutions = set()

    key1 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    key = key1 + ['A', 'B', 'C', 'D', 'E', 'F']

    best = 10**6
    num1, num2 = split_list(16)
    list_perm2 = list(permutations(num2))
    for perm1 in permutations(num1):
        for perm2 in list_perm2:
            perm = perm1 + perm2
            tple = product_sum(perm)
            temp_best = abs(product_num(tple))
            if temp_best <= best:
                print perm
                display_tuple(tuple_2_16bit(perm))
                best = temp_best
                if temp_best == 0:
                    solutions.add(perm)
    return list(solutions)


def split_list(n):
    num = range(1, n)
    high = [num.pop()]
    low = []
    while len(num) > 0:
        while sum(high) >= sum(low) and len(num) > 0:
            low.append(num.pop())
        temp_high = high
        high = low
        low = temp_high
    if len(high) > len(low):
        low.append(0)
    else:
        high.append(0)
    return high, low


def product_sum(tple):
    lst = list(tple)
    num1 = sum(k*16**(4-i) for i, k in enumerate(lst[0:5]))
    num2 = sum(k*16**(2-i) for i, k in enumerate(lst[5:8]))
    num3 = sum(k*16**(4-i) for i, k in enumerate(lst[8:13]))
    num4 = sum(k*16**(2-i) for i, k in enumerate(lst[13:16]))
    return (num1, num2, num3, num4)


def product_num(tple):
    total = tple[0]*tple[1] - tple[2]*tple[3]
    return total


def tuple_2_16bit(tple):
    key1 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
    key = key1 + ['A', 'B', 'C', 'D', 'E', 'F']
    lst = [str(key[i]) for i in tple]
    return (''.join(lst[0: 5]), ''.join(lst[5: 8]), ''.join(lst[8: 13]), ''.join(lst[13: 16]))


def display_tuple(tple):
    print '   ' + tple[0] + ' x ' + tple[1]
    print ' - ' + tple[2] + ' x ' + tple[3]
    print ' = ', int(tple[0], 16)*int(tple[1], 16) - int(tple[2], 16)*int(tple[3], 16)

if __name__ == '__main__':

    print find_sum_equal_n_16bit()

Answer 1

Looking axx*bxx for some a and b we can see that this restricts possible c and d in cxx*dxx for 2nd product.

in 10 digit numbers you can build in this order (digits represnts ordering)

048  15
269  37

This way it is possible to generate numbers in way to quickly reduce large portion of search tree when it is detected that result will be larger than prevously found optimal solution.