零和游戏16位版本

Question

1.前言

常见的脑力激荡器是使用0..9恰好一次填充下面的空格,以使总和最小化.

  xxx*xx
- xxx*xx
= 

一个解决方案是408 x 37 - 296 x 51 = 0.然而,由于只10! = 3.6*10^6存在数字的排列,所以这个问题很容易被强制解决.我写了一个简单的代码来解决下面发布的这个问题.

2. 16byte问题

类似但更难的问题是使用十六进制数系统执行与上述相同的操作.0...F准确使用数字一次

  xxxx * xxx
- xxxx * xxx
= 

最小化.我这里只发现了两个解决方案.

   FD906 x 5A1
 - 7EC83 x B42
 =  0

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

3.问题

是否存在一种更巧妙的方式来改变排列并找到零解决方案？问题是现在布鲁顿力量的排列太多了.

4.尝试

对于16位数字系统3.5 * 10^14,与仅存在3.6 * 10^6基本10版本相比存在.因此,普通的暴力解决方案需要很长时间.我的第一次尝试是将数字列表分成两组

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

第一组是第一个产品,第二组是第二个产品.创建这些列表的方式是使用贪婪的排序,并且总和为60.这应该提供更高的理论上相等的机会.现在要迭代的排列数8! * 8! = 1.6*10^9.好多了,但仍比基本10版大150倍.

任何更快速的方法提示都是非常有用的.

Base10版本

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版本

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

寻找axx*bxx一些a，b我们可以看到这限制c了第二个产品的d可能性cxx*dxx。

您可以按此顺序构建 10 位数字（数字代表排序）

048  15
269  37

这样，当检测到结果将大于先前找到的最佳解决方案时，可以以快速减少搜索树的大部分的方式生成数字。