ArticlesIntroducing Kakuro
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.
The Implementation
I’ve done this a couple of times before (Nonograms, Sudoku, Australian Bush Game) so the approach was familiar. As usual, I was careful not to see look to see how anyone else approached it.
Technology
I rounded up the usual suspects: about 350 lines of Python code with the help of PyGame and Python Imaging Library for the animation.
Data Structures
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.
Interactions
Start Up
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.
Calculation
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.
Complexity
As an accidental side-effect of this iteration, it offered a simpler upper-bound complexity analysis.
The 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 O(|grid|.|alphabet|).
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 O(|grid|2.|alphabet|2).
Permutations
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.
Algorithm Animation
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.
Outcome
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.
Hooray!
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!
Double Hooray!
For n=2, it looks like the simplistic algorithm works!
Solver in Action
Legend:
- 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
Half Solved
Solved!
Comment by LuÃÂs on March 4, 2006
Hello julian. I am triyng to get a kakuro solver, so i can solve some puzzels that are almost impossible to solve. the problem is that i don’t know anything about C++. Can you help me?
If you want i’ll send you a copy of some a this puzzels so you can see how hard they are. Thanks
Comment by Julian on March 5, 2006
Luis,
My first reaction to your request was negative. I am not interested in packaging my tool up and making it an application that anyone can install. I am also not interested in cleaning it up and supporting it to the extent that I could release it as open-source with pride.
So I was going to tell you to look elsewhere.
The second reaction to your request was to realise that I hadn’t really given the solver a real work out. I have only used it to solve a couple of puzzles (one at the “Ninja” level) and perhaps getting a couple of known-hard puzzles would solve it.
So, I was going to tell you to submit your puzzles.
My third reaction was to take care, because no doubt non-solvable puzzles exist – and failing to solve an unsolved puzzle that was submitted from an unreliable source wouldn’t prove anything.
So, I was going to tell you to look elsewhere.
I decided to see whether I could be more helpful by pointing you to someone who had released a Kakuro Solver.
I found Zvrba had written an article which not only described an open-source C++ Kakuro Solver, but shared my concerns about the claims about Sudoku.
There I found that, Luis, you had posted a comment there too, with the same now-not-so-cryptic comment about C++. (For the record, no C++ was harmed in the making of my solver. It was all Python.)
So when that I realised you are repeating the same request around the blogosphere, my fourth reaction was not to feel motivated to respond at all.
Sorry, and good luck with your search.
Comment by Christian on March 24, 2006
Hi ! Thanks for sharing ! But I saw at http://www.kakuro.com/, that the puzzle UI was created using Flash ? Do you think that the code lies behind using Actionscript ? Well, I am amazed if the programmer created such a beautiful mind killer using only ActionScript.
Thanks !
Comment by Paul Hounshell on June 7, 2006
I went down a very similar path for solving the puzzle (avoiding other solutions, expecting the worst, using dirty/trigger flags, etc.) The one thing I did that I didn’t see you mention was the way I organized my data structures.
I assumed you worked off of the 2 dimensional matrix for your work, which means looping horizontally and vertically to check each field’s possible values, and then again to trigger the changes.
Instead, I created “relationships” up front. A group of horizontal cells forms a relationship and a group of vertical cells forms a relationship. Then when doing your logic and triggers, you only need to loop through all relationships a cell is in, then all cells in that relationship. There’s an extended benefit to this. If you were to construct a Kakuro puzzle of a 9×9 grid (10×10 with clues) where each row and column had 9 cells which add up to 45, throw in a couple of known values, and add a relationship consisting of each non-overlapping 3×3 grid, your kakuro solver has effectively turned into a sudoku solver.
To go one step further (a task I haven’t undertaken yet, but plan to), giving your relationships a replacable validity algorithm gives you a very generic “number problem solver” which can be used for a very wide array of games like this. For example, a Sudoku Relationship indicates that each cell in the relationship must have a unique value. A Kakuro Relationship indicates that each cell must have a unique value and add up to the predetermined total.
Anyway, just some ideas. I am not familiar with Python, so I’m not sure how doable this is in that context.
Oh, one last thing, try turning your animation off. I put animation in mine and the solution for the hardest puzzles was comparable (~25 seconds). I switched to just animating on completion and solution time dropped to around 1/10 of a second. Need to time it to make sure.
Comment by Pico on July 20, 2006
You can try to solve Kakuro puzzles on http://www.varpi.com/kakuro.html.
Comment by KakuroPlay on August 4, 2006
There is a site called KakuroPlay, http://www.kakuroplay.com.
KakuroPlay offers free online Kakuro puzzles, tutorials and dicussion forum.
Try it, it’s nice.
Comment by Julian on August 6, 2006
I pondered whether to start deleting this “semi-relevant, come-visit-my-site almost-spam”, but I visited the second of the two links and played one game.
It posed a Kakuro with two legal solutions! It tries to assist by listing all the possible variants, but gets it wrong! So rather than delete the second link, I will just pooh-pooh it. Haven’t even bothered with the first link.
Comment by Alan B on February 10, 2007
When solving Kakuro puzzles by hand, a useful technique is to first determine the possible range of values for each cell. The lowest possible value for each cell occurs when the values for the other cells are maximum. Conversely, the highest possible value for any cell occurs when all the other cells are at their lowest value. Combining the ranges in both the horizontal and vertical positions will reduce the range of possible values still further.
Using this technique will reduce possible numbers in a large proportion cells in a puzzle to 4 numbers or less. Use of other techniques then becomes a much quicker route to the solution.
A fully detailed description of this method can be seen on http://www.kakuronerd.com.
Comment by Donnie on April 25, 2007
I have a kakuro puzzle that my friends and I believe to be impossible to solve (bad puzzle?). Anyone want to take a crack at it?
Comment by pptpin1 on May 1, 2008
I’m sorry ,but I don’t understand the Algorithm well enough .Could you give me some more drtails asap? Thanks a lot!
Comment by Kakuro ATK on May 2, 2008
There are many techniques to solve a Kakuro puzzle. When the simple techniques don’t work, you need to use a more complicated solve technique. This can get to a point where it almost looks but not impossible to solve and may take a long time using a automatic solver let alone solving it by hand. Just as long that there is only one solution that will work. Try this online game: Kakuro
Comment by bigdogdman on July 16, 2009
After scouring the internet, the only two pages I could find on kakuro solvers were this one and http://kakuro-solver.blogspot.com/2006/08/kakuro-solver.html
All I’m looking for is some sample code that already works to expand upon and tweak; your animated solver fit the bill perfectly, since I’m not as up to speed on graphical coding as I am on algorithms. Is your python code available for examination by any chance?
Thx for the post BTW; it was very helpful in my own kakuro-solving endeavors.
Comment by William on July 29, 2009
Can you send me the algorithm?
Comment by UltraMadWizard on July 30, 2009
Hi,
I have recently written my own kakuro-solver and want to test it now. Does anyone know a website where I can find extremly hard kakuros (I mean 25 times 25 or something like that, the maximum value of the summands can be arbitrary( but must be known ahead of corse) and doesn’t necessarily has to be 9 (but can be 9 of corse)). Or could someone having an ultra-hard Kakuro available please post it or send me.
thx+bye.
Comment by chandresh on December 5, 2009
hi,
i am getting project on kakuro in my college..using C language..
but i cant understand how to implement it in C language.
please help me if you know please guide me.
Comment by John on August 23, 2010
How do you start writing with any solver in C++,
I want to program a solver.
Such as a sudoku or kakuro solver. 🙂
How do I start, what do I have to include in my file, what algorithm(s) to use?
I am planning to program solvers and use it for my own.
Thank you for reading 🙂
Comment by Julian on August 24, 2010
John,
It can certainly be hard to start out.
I would look for an article about Kakoro Solvers which described the simple algorithm near the top – maybe in the second section?
You probably wouldn’t get any “Beginner C++ Programming” advice there – you’d need to look elsewhere. Perhaps Google? I can’t imagine what a good search term might be.
Try to avoid blogs where the author uses irony when he is tired and grumpy.
Comment by Andrew on August 24, 2010
Julian, your third paragraph should read “On the other hand, you probably…”; and after “It can certainly be hard to start out.” you should have added another paragraph with some encouraging words. I suggest “Don’t be discouraged, however.”
This would make your reply much more enlightening to, well, beginners.
Comment by Julian on September 1, 2010
Indeed, Andrew. In fact, it should probably have started out: “I’m off to bed. I’ll answer this when I’ve had some sleep.” 🙂
Comment by Maria on June 2, 2016
hey Julian,
I’m doing some researches about the Kakuro solver.
I wanted an algorithm that can be implemented “fast” (like I have only 24 hours to solve it with a group of 4 members).
I see that your approach is not complicated, yet the graphic is hard.
is it possible to implement it within 24 hours?
thanks