Jason, very interesting reading. I'll have to go through that a few more times though ;-)
If anybody is interested, I ended up coding the whole Kakuro solver in Python 3. It will take 0.1 seconds (measured on my not-so-recent laptop) for a regular 9x9 puzzle, or 0.5 seconds for the one I included in the source code, classified "diabolical". Most of the time is actually spend in deepcopy() so you can probably get a big speedup if you create a specific deepcopy() function. Given the fact that I need minutes to enter the puzzle in text format, this was good enough and I stopped optimisations right there. I ran it with pypy3 which also features a JIT compiler. The execution times were worse than with stock CPython for obvious reasons. The code is available at https://github.com/uselpa/kakuro-solver. Thanks to all of you for your feedback! An awesome community is what makes an excellent language a great language. Regards, Patrick