The secret? The old program would find all possible permutations of all possible combinations for each sum, then painstakingly remove all the impossible ones. It turns out that using a list comprehension, and removing in advance the permutations that are disallowed by just the first and last cells of the sum -- this one step -- gives almost an order of magnitude speedup. I suspect some of the savings is due to reduced demands on memory management.
Almost another order of magnitude can be gained by using the entire list of cells in the aforementioned pre-screening. It turns out that since the list of "possibles" is constant while we're screening out permutations, we can build a string like
"lambda vec: vec in (1,2,3) and vec in (1,2) and..."then say mm=eval(that string), and then code the list comprehension as [x for x in permutes(...) if mm(x)]
I have to say Guido and the Python team were genius to give us list comprehensions and the "eval" function. That was a lot of fun, too! Oh -- I updated the website with the latest sources, as well as the steps from the old to new, for your code-reading pleasure. Enjoy!