Kakuro solver considered too slow -- but now fixed. "They see me mowin'..."

Couldn't leave well enough alone, so I googled "hard kakuro" and clicked to an astonishingly difficult kakuro puzzle at http://www.bestkakuro.com/killer2.gif; it took my old solver something like 15 minutes on my desktop box. This seemed entirely too long, so I played with it, resulting in a speedup of better than 94:1 on said desktop box. Running the old vs. new Python programs on a G4 Powerbook gave a better than 100:1 speedup.

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[0] in (1,2,3) and vec[1] 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!

3/29: took another 13-17% off the execution time!

What took 54:22 (yes, nearly an hour) on a powerbook G4 now takes under 23 seconds on the same box, roughly a 140:1 speedup. On a 2.6GHz Xeon 5150, the speedup was 5:54 down to under 5 seconds, better than 70:1. I really like Python.