I have been doing a few of these. Only a handful. Certainly not as many as Andrew at Anotherblog<\/a>.<\/p>\n As my regular readers will know, I prefer to solve the general case<\/a>, rather than solving individual puzzles, and preferably with an elegant algorithm than using an elephant gun, like backtracking.<\/p>\n So let’s look at Kakuro…<\/p>\n How do I solve Kakuro puzzles? <\/p>\n I looked at my approach. I seemed to ask a lot of “What If?” style questions (“If this cell was the maximum it could be, and this cell was the maximum it could be, then that would dictate the minimum value the last cell could be.”)<\/p>\n However, it all seemed to boil down to:<\/p>\n It seemed pretty simplistic and obvious. However, I’ve been fooled before. Sudoku didn’t fall to the simplistic and obvious. <\/p>\n Time to implement a Kakuro solver to find out.<\/p>\n I’ve done this a couple of times before (Nonograms<\/a>, Sudoku<\/a>, Australian Bush Game<\/a>) so the approach was familiar. As usual, I was careful not to see look to see how anyone else approached it.<\/p>\n I rounded up the usual suspects: about 350 lines of Python code with the help of PyGame and Python Imaging Library for the animation.<\/p>\n The objects were straightforward:<\/p>\n The Grid represents the whole table, full of Cells. <\/p>\n Cells represent a square on the grid, and know what values that they can have. <\/p>\n Rows represent horizontal and vertical<\/em> sets of Cells with a total – i.e. the clues to the puzzle. They don’t record the actual values of the cells. Rows really only have a responsibility during the start-up phase, and then they are redundant.<\/p>\n PossibleRowValues represent a set of values for each Cell in a row.<\/p>\n The only complexity in the data structure was that Cells have a list of all the PossibleRowValues, grouped by the value the cell would have to take to fit. Meanwhile each PossibleRowValues object has links back to the Cells that are affected by it.<\/p>\n The main program creates the Grid. The Grid creates and owns the Cells. <\/p>\n The main program creates the Rows. The Rows register themselves with the Grid, which returns the set of cells associated with them. The Rows then create the PossibleRowValues (discussed more later), and help create the mapping from the Cells to the PossibleRowValues and vice versa. <\/p>\n When triggered, each Cell compares the horizontal PossibleRowValues to the Vertical PossibleRowValues with the aim of eliminating cell values that are not in common with both. <\/p>\n Once a cell value is marked for elimination, all of the corresponding PossibleRowValues are “deleted”. During their deletion, the PossibleRowValues inform the other cells in the same row that the PossibleRowValue is being deleted.<\/p>\n This is a recursive algorithm. Once a Cell is informed that a PossibleRowValue has been deleted, it can be considered a trigger to redo its own calculations.<\/p>\n In past puzzles, I have used two different approaches here.<\/p>\n The obvious approach is to do this recursively – have each cell trigger other cells directly, and let the program stack keep track of the progress.<\/p>\nWhat’s the Algorithm?<\/h3>\n
\n
The Implementation<\/h3>\n
Technology<\/h4>\n
Data Structures<\/h4>\n
Interactions<\/h4>\n
Start Up<\/h5>\n
Calculation<\/h5>\n
Flow of the Trigger<\/h5>\n
![\"Kakuro](\"http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2006\/02\/kakuro_startup.PNG\")
<\/p>\n![\"kakuro](\"http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2006\/02\/kakuro_halfway.PNG\")
<\/p>\n![\"Kakuro](\"http:\/\/www.somethinkodd.com\/oddthinking\/wp-content\/uploads\/2006\/02\/kakuro_solved.PNG\")
<\/p>\n","protected":false},"excerpt":{"rendered":"