Compose valid subtractions using all digits from a set
first of all try use middlenumber as set. Than adding numbers no by extends but something as middlenumber.add(x &lt; y - x and (x, y-x) or (y-x, x)). You have strange duplicates number
naive brute force algorithm use 9^6 checking as you mentioned
something better when you change to permutations (9!/3! checking). There example for simpler 3-digit version 

from itertools import permutations

def permutations_solver():
    digits = set('987654321')
    numbers = (''.join(x) for x in permutations(digits, 6))
    for x in numbers:
        a = int(x[0 : 3])
        b = int(x[3 : 6])
        c = a - b
        if b &gt; c and c &gt; 0 and set(str(c) + x) == digits:
            yield a, b, c

print(len(list(permutations_solver())))

checking b &gt; c and c &gt; 0 and set(str(c) + x) == digits above still is very ineffective
you can try write iterator on digits, something as 

"""           set('abcdefgh') == set('123456789') and set('zxyr') == set('01')
zxyr          abc &lt; def (enough a &lt; d)
 abc          z == 0
+def          x + a + d == g + 10 * z
----          y + b + e == h + 10 * x
 ghi          r + c + f == i + 10 * y
 zxy          r == 0 // it looks like logic programming problem
"""
from itertools import product

def digits_solver():
    column = [(x, a, d, (x + a + d) % 10, (x + a + d) // 10)
              for x, a, d in product(range(2), range(1, 10), range(1, 10))
              if len(set([a, d, (x + a + d) % 10])) == 3 and (x + a + d) % 10 != 0]
    first_column = [(x, a, d, g) for x, a, d, g, z in column if z == 0 and a &lt; d]
    for x, a, d, g in first_column:
        second_column = [(y, b, e, h) for y, b, e, h, xx in column if xx == x and not set([a,d,g]) &amp; set([b,e,h])]
        for y, b, e, h in second_column:
            third_column = [(r, c, f, i) for r, c, f, i, yy in column
                            if yy == y and not set([a,d,g,b,e,h]) &amp; set([c,f,i]) and r == 0 ]
            for _, c, f, i  in third_column:
                yield (100 * g + 10 * h + i, 100 * d + 10 * e + f, 100 * a + 10 * b + c)

in above example for by for by for is bad idea, you can remove it by recursion. The code will be much less messy
if you want try 6-digits number, you can change check unique digits (using set at examples) to multiset (at python you can use Counter class from collections library to emulate it)