It's not Pythonic, but it works (so far)

The code described below doesn't handle very hard puzzle #345943 by Vegard Hanssen; see this later post for an update.
– 2010-03-21

Following up on my earlier post on Python and kakuro, I did a few more things and it now solves every puzzle I've tried on it. I'll explain using this fragment of the earlier puzzle:

      A     B     C     D     E     F    
   +-----+-----+-----+-----+-----+-----+... 
  0|XXXXX|XXXXX|XXXXX|17\  |15\  |XXXXX| 
   +-----+-----+-----+-----+-----+-----+ 
  1|XXXXX|XXXXX|  \10| ___ | ___ |XXXXX| 
   +-----+-----+-----+-----+-----+-----+ 
  2|XXXXX|XXXXX|  \15| ___ | ___ |18\... 
   +-----+-----+-----+-----+-----+-----+-----+ ... 
  3|XXXXX| 9\  |16\  |  \11| ___ | ___ | ___ | ... 
   +-----+-----+-----+-----+-----+-----+-----+
                           | ... | ... | ... |

The earlier version did this:

1. For each blank cell, create a list of possible values. This is initially [1,2,3,4,5,6,7,8,9].
2. Given the number of cells that must add up to a given total (e.g., 1D+1E=10 because of 1C across), figure out all possible combinations of values (e.g., 1+9, 2+8, 3+7, 4+6; can't do 5+5 because that would repeat). Remove from the cells any possible value that isn't in this list of combinations (so that 1D and 1E would have at most [1,2,3,4,6,7,8,9]).

   Do this for all totals. (In the above example, 1D+2D=17 because of 0D, hence 1D and 2D can be at most [8,9]. Similarly, 1E can be at most [1,2,8,9]. More on this below.)

3. If the number of possible values becomes 1 for any cell, then that cell's value is decided. No other cell that's part of the same total (whether an across total or a down total) can have that value, so eliminate that value from the list-of-possibles for those cells. This may cause another cell's list-of-possibles to have only one value, so this other cell is now decided, and so on. Repeat until no more cells are getting decided.
4. Another way a call's value can be decided is this: Suppose that all combinations require a certain value (if you have to produce 22 in 3 cells, for example, this can be 9+8+5 or 9+7+6; in any case you need a 9), and suppose only one of your cells could possibly have that value (because of other decided cells/combinations), then that cell must have that value, so it's also decided. Repeat the loop of step#3 until cells stop getting decided.
5. For all totals, eliminate any combination that's impossible by virtue of step #2 (for example, the combinations possible for 1C are now reduced to 1+9 and 2+8, since 3+7 and 4+6 require values that 1D cannot have)
6. Repeat #2-#5 until they don't modify anything in the puzzle

That got me to the result shown earlier, with 41 cells left undecided. Here's what I added since that earlier posting:

• Handle 2x2 boxes with a tail on them. (The "box technique" is described concisely in the Wikipedia article.) In the above example, 1C says 1D+1E=10, and 2C says 2D+2E=15. Hence 1D+2D+1E+2E=25. Similarly 0D and 0E dictate that 1D+2D+1E+2E+3E=17+15=32; combining we see that 3E=7. This is another way a cell's value can be decided. Repeat the loop of step#3 above until no more cells are decided. This filled in a dozen cells, leaving 29 undecided.
• Make steps #2,#5 more effective by using ordered lists of numbers rather than unordered lists. In the example of step#2, we determined that 1E has possible values [1,2,8,9]; this is because 1C's list of possible combinations was reduced to 1+9 or 2+8; that code didn't take cell ordering into account. Yes, I know it was dumb, but I code the easy cases first! If we keep track of permutations (ordered lists) of possible cell values rather than merely combinations, the program will know that 1E can't be 8 or 9; it can only be 1 or 2, since 1D can be 9 or 8. With this logic added, the program solves all kakuro puzzles I tried, including today's from the Examiner.

  It seems like we have a sort of belt-and-suspenders thing going here; the "box" logic described in the previous bullet might overlap with what step#4 does, and the step of using permutations rather than combinations might have been adequate by itself. But I'm not sure and I'm not motivitated to work more on it now.

  Why not just start with the permutations in the first place? Well, if you have 9 cells (45 in nine), then how many permutations is that? Right, 9!=362880. Well, that's possible on most well-equipped modern computers, but it seemed rather much to me.

That sure was fun! I've put my code, and a few examples, on http://cpark.users.sonic.net/kakuro-python/ for your viewing pleasure.