In the footsteps of the Sudoku craze comes a wannabe replacement: Kakuro. (Visit the link to learn more; I won’t bother explaining the rules here.)
I have been doing a few of these. Only a handful. Certainly not as many as Andrew at Anotherblog.
As my regular readers will know, I prefer to solve the general case, rather than solving individual puzzles, and preferably with an elegant algorithm than using an elephant gun, like backtracking.
So let’s look at Kakuro…
What’s the Algorithm?
How do I solve Kakuro puzzles?
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.”)
However, it all seemed to boil down to:
- Work out what combinations of numbers add up to the total, given the restrictions on the individual cells.
- Eliminating illegal values: ones that aren’t in both the horizontal and vertical lists of possible values.
- Repeat, repeat, repeat
It seemed pretty simplistic and obvious. However, I’ve been fooled before. Sudoku didn’t fall to the simplistic and obvious.
Time to implement a Kakuro solver to find out.
I rounded up the usual suspects: about 350 lines of Python code with the help of PyGame and Python Imaging Library for the animation.
The objects were straightforward:
The Grid represents the whole table, full of Cells.
Cells represent a square on the grid, and know what values that they can have.
Rows represent horizontal and vertical 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.
PossibleRowValues represent a set of values for each Cell in a row.
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.
The main program creates the Grid. The Grid creates and owns the Cells.
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.
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.
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.
Flow of the Trigger
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.
In past puzzles, I have used two different approaches here.
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.
I have written before about using a Command pattern and a queue of Commands to turn recursion into iteration.
Both of those solutions probably would have worked here, but I went for a third approach this time.
I ignored triggers, and simply looped through each cell in the grid telling it to update whether it needed it or not. This wasn’t a decision based on careful evaluation of the optimal efficiency. It just struck me as fairly simple to implement.
As an accidental side-effect of this iteration, it offered a simpler upper-bound complexity analysis.
alphabet is the numbers from 1 to 9 that each cell can take.
The worst case time to evaluate every cell is the deletion of the PossibleRowValues corresponding to
|alphabet| - 1 values. The deletion of PossibleRowValues has a constant upper-bound. So each cell, worst-case, takes
O(|alphabet|) to evaluate.
|Grid| is the total number of cells in the grid (typically 9×9 = 81, although the labels make it appear to be 10×10).
The time taken to loop through the grid and trigger each cell is therefore
If this algorithm worked, it would need to eliminate at least one value in each pass through the grid. There are at most
|grid|.|alphabet| values in the grid, so the worst-case complexity is
The Row object must create one PossibleRowValues for every permutation of every set of values that add up to the total.
How many of these are there?
I’m glad you asked.
There are 8 possible row lengths from 2 to 9. Each has its own minimum and maximum total value. For example, the totals of a row of length 5 range between 15 and 35.
There are a total of 120 different length/total pairs.
The theoretical row with the most number of permutations is a row of length=9 and total=45. That has 9! = 362880 permutations.
The worst example I have found in “real-life” in the handful of Kakuro I have done is a row if length=7 and total=41, which has 5040 permutations.
I started out expecting the worst. I pondered how I could cache these calculated values and optimise them. (That would require space for just under a million permutations). Fortunately, I held back and just implemented a naive solution first. It takes about 7 seconds to generate all the combinations required for the typical puzzle. I didn’t feel the need to optimise further.
Drawing on my past experience, I gave development priority to the graphical display of the algorithm’s progress. The aim was to make debugging of the algorithm easier.
The debugging of this implementation went very quickly and painlessly. I don’t know whether that means that my effort to make debugging easier was wasted, or extremely well spent!
The largest source of errors was the data-entry of the clues into the grid. The graphical display certainly helped proof-reading those values.
I entered a Novice-level puzzle that I had previously solved. The software churned for about 7 seconds computing permutations, then displayed the grid on screen, and progressively solved it in about 25 seconds.
I entered a Ninja-level puzzle that I had previously half-solved. The software churned for about 7 seconds computing permutations, then displayed the grid on screen, and progressively solved it in about 25 seconds. No real difference!
n=2, it looks like the simplistic algorithm works!
Solver in Action
- White numbers: clues
- Blue numbers: solutions to cells
- Red Numbers: possible value this cell might take.
- Grey Background: Out-of-date; this cell has been updated since the last time it calculated the possible values.
- White Background: Up-to-date; no change since the last recalculation.
Ready to Begin Calculations