Update 2011-02-09 Use version 14

@@ -87,8 +87,7 @@
             passno += 1
 
             for acell in [x for x in reduce(lambda a,b:a+b, the_puzzle) 
-                          if x.type == 0 and len(x.possibles) == 2]:
-                # For now try it only on cells having exactly 2 possibles
+                          if x.type == 0]:
                 for aval in acell.possibles:
                     achange = cut_contradictory_possibles(acell, aval)
                     more_to_do += achange 

Update 2010-03-28: This version is 60-90x as fast

• version 8 implements this rule: Suppose we have two cells which must be either 1 or 2. Then no other cell in that sum can be either of those values. The same thing holds if there are three cells which must be one of (1,2,3) -- no other cell can have any of those values. As you can see, it helped nontrivially but not spectacularly.
• version 9 changes the trace outputs a little (why did I bother?)
• version 10 was the first major improvement (about 7:1); when setting up the list of possible permutations for each total (e.g., the 45 heading downward in the puzzle at right), only allow those permutations whose first element is in the first cell's list of possibles, and whose last element is in the last cell's list of possibles.
• version 11 gives another 10:1 (or better) improvement over version 10 by screening the possible permutation against the possible values in all the cells. This screening is done using a "compiled" lambda (create a string that checks each component of the permutation vs a constant list of the possibles of each cell in the sum).
• version 12 applies the change of version 11 to every pass, but not the list of permutations while initially loading into the Total instance. This is a little slower than version 11 (memory allocation overhead?).
• version 13 restores the screening to the "while initially loading" phase. This is the fastest version so far.
• Version 14 again solves the veryhard puzzle.

Update 2010-03-21: Solves Vegard Hanssen's very hard puzzles

The new k2.py can; it has prettier HTML, too. See download section for sources.
An example of the prettier html is at veryhard.html, which was created like this:

./k2.py < veryhard-messeske.no-395943 > veryhard.html

Update 2010-03-19: HTML output

$ ./k2.py < sample-march7.txt > march7.html

• my first whack: http://collinpark.blogspot.com/2010/03/python-and-kakuro.html
• full solution: http://collinpark.blogspot.com/2010/03/its-not-pythonic-but-it-works-so-far.html

Download

The program text is Copyright © 2010 Collin Park; see the source for details. If your browser tries to execute the programs when you click on the link, you can try using right-click (or ctrl-click on Mac OS) and "save as". You may need to run Python explicitly if /usr/bin/python doesn't exist on your computer. It's been run under Python 2.3.4 and Python 2.6.2.

• Cell.py, the cell class;
• k2.py (or k2-11.py or...), the solver's "main" part, which will give HTML output on stdout.
• graytotals.png for pretty HTML
• a sample puzzle or two, e.g., sample1.txt or bestkiller2

• 2010-03-28 update: 60-90x speedup, and intermediate stages...
  • k2-8.py version 8
  • k2-9.py version 9
  • k2-10.py version 10
  • k2-11.py version 11 ⇐the fastest one
  • k2-12.py version 12
  • k2-13.py version 13 ⇐the fastest as of 2010-03-29
• k1.py -- the main part of the solver
• k2.py prettier HTML and *does* solve Vegard Hanssen's veryhard puzzles -- at least the ones I tried
• graytotals.png needed for the prettier HTML
• k2-Mar_19_2255.py -- k1.py but with HTML output (doesn't solve Vegard Hanssen's puzzles)
• Cell.py -- Cell and Total classes needed by k1.py

• sample1.txt -- from the Examiner, maybe 2010-02-26?
• sample-march7.txt -- from the Examiner, 2010-03-07
• easy.19mar2010 -- from http://kakuro.cc/E19-3-2010-kakuro.aspx -- see pretty solution here
• Hard_Kakuro_for_19.March.2010 -- from http://kakuro.cc/H19-3-2010-kakuro.aspx
• med.14x10.kakuro.com.18mar2010 -- from http://www.kakuro.com/puzzles.php
• bestkiller2 transcribed from http://www.bestkakuro.com/killer2.gif, apparently modified Sun 14 May 2006 08:06:30 AM PDT

$ ./k1.py < Hard_Kakuro_for_19.March.2010 
k1.py: solve a kakuro puzzle from stdin
    Copyright (C) 2010 Collin Park

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    See <http://www.gnu.org/licenses/> for full license text. 

      A     B     C     D     E     F     G  
   +-----+-----+-----+-----+-----+-----+-----+
  0|XXXXX|XXXXX|11\  |25\  |XXXXX|XXXXX|XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
  1|XXXXX|27\ 6| ___ | ___ |20\  |12\  |13\  |
   +-----+-----+-----+-----+-----+-----+-----+
  2|  \39| ___ | ___ | ___ | ___ | ___ | ___ |
   +-----+-----+-----+-----+-----+-----+-----+
  3|XXXXX| ___ | 7\30| ___ | ___ | ___ | ___ |
   +-----+-----+-----+-----+-----+-----+-----+
  4|  \11| ___ | ___ | ___ | ___ | 6\  | ___ |
   +-----+-----+-----+-----+-----+-----+-----+
  5|  \21| ___ | ___ | ___ | ___ |  5  | ___ |
   +-----+-----+-----+-----+-----+-----+-----+
  6|XXXXX|XXXXX|XXXXX|  \ 4|  3  |  1  |XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+

%%% 1C [2, 4, 5]
%%% 1D [1, 2, 4, 5]
%%% 2B [5, 6, 7, 8, 9]
%%% 2C [4, 5, 6, 7, 9]
%%% 2D [4, 5, 6, 7, 8, 9]
%%% 2E [4, 5, 6, 7, 8, 9]
%%% 2F [4, 5, 7, 8, 9]
%%% 2G [4, 6, 7]
%%% 3B [3, 5, 6, 7, 8, 9]
%%% 3D [6, 7, 8, 9]
%%% 3E [6, 7, 8, 9]
%%% 3F [7, 8, 9]
%%% 3G [6, 7]
%%% 4B [3, 5]
%%% 4C [1, 2, 3, 5]
%%% 4D [1, 2, 3, 5]
%%% 4E [1, 2, 5]
%%% 4G [1, 2, 3, 4, 6, 7]
%%% 5B [3, 6]
%%% 5C [1, 2, 3, 4, 6]
%%% 5D [1, 2, 3, 4, 6]
%%% 5E [1, 2, 4, 6]
%%% 5G [1, 2, 3, 4, 6]
>>> 0C down [(5, 6), (4, 7), (2, 9)]
>>> 0D down [(3, 4, 5, 6, 7), (2, 4, 5, 6, 8), (2, 3, 5, 7, 8), (1, 4, 5, 7, 8), (1, 3, 6, 7, 8), (2, 3, 5, 6, 9), (1, 4, 5, 6, 9), (2, 3, 4, 7, 9), (1, 3, 5, 7, 9), (1, 2, 6, 7, 9), (1, 3, 4, 8, 9), (1, 2, 5, 8, 9)]
>>> 1B across [(2, 4), (1, 5)]
>>> 1B down [(5, 6, 7, 9), (3, 7, 8, 9)]
>>> 1E down [(2, 3, 4, 5, 6), (1, 3, 4, 5, 7), (1, 2, 3, 6, 8), (1, 2, 3, 5, 9)]
>>> 1F down [(5, 7), (4, 8), (3, 9)]
>>> 1G down [(1, 2, 4, 6), (1, 2, 3, 7)]
>>> 2A across [(4, 5, 6, 7, 8, 9)]
>>> 3C across [(6, 7, 8, 9)]
>>> 3C down [(3, 4), (2, 5), (1, 6)]
>>> 4A across [(1, 2, 3, 5)]
>>> 5A across [(1, 2, 3, 4, 5, 6)]

      A     B     C     D     E     F     G  
   +-----+-----+-----+-----+-----+-----+-----+
  0|XXXXX|XXXXX|11\  |25\  |XXXXX|XXXXX|XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
  1|XXXXX|27\ 6|  2  |  4  |20\  |12\  |13\  |
   +-----+-----+-----+-----+-----+-----+-----+
  2|  \39|  7  |  9  |  8  |  6  |  5  |  4  |
   +-----+-----+-----+-----+-----+-----+-----+
  3|XXXXX|  9  | 7\30|  9  |  8  |  7  |  6  |
   +-----+-----+-----+-----+-----+-----+-----+
  4|  \11|  5  |  3  |  1  |  2  | 6\  |  1  |
   +-----+-----+-----+-----+-----+-----+-----+
  5|  \21|  6  |  4  |  3  |  1  |  5  |  2  |
   +-----+-----+-----+-----+-----+-----+-----+
  6|XXXXX|XXXXX|XXXXX|  \ 4|  3  |  1  |XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
$ 

$ ./k1.py < easy.19mar2010 
k1.py: solve a kakuro puzzle from stdin
    Copyright (C) 2010 Collin Park

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    See  for full license text. 
      A     B     C     D     E     F     G  
   +-----+-----+-----+-----+-----+-----+-----+
  0|XXXXX|XXXXX|XXXXX|XXXXX|10\  |17\  |XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
  1|XXXXX|XXXXX| 3\12|  1  |  2  |  9  |XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
  2|  \ 3|  2  |  1  |10\ 9|  1  |  8  |XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
  3|XXXXX|  \ 6|  2  |  1  |  3  |17\  |XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
  4|XXXXX|XXXXX| 3\15|  2  |  4  |  9  |XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
  5|XXXXX|  \ 5|  2  |  3  |  \ 9|  8  |  1  |
   +-----+-----+-----+-----+-----+-----+-----+
  6|XXXXX|  \ 7|  1  |  4  |  2  |XXXXX|XXXXX|
   +-----+-----+-----+-----+-----+-----+-----+
$