Article

A simple Kakuro solver

Because I’ve become quite a fan of the Kakuro puzzles published in The Guardian, I figured it might be nice to create my own little Kakuro solver. After spending some hours on this, I came up with a Java solver program (downloadable below), using a pretty elegant algorithm (some comments follow).

About solving Kakuros

The Kakuro, according to Wikipedia, is “a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword”. Becoming more popular in the slipstream if the Sudoku, indeed it is kind of similar puzzle.

Wikipedia mentions that the problem of solving a general Kakuro puzzle is NP-complete, which basically means that even as a puzzle gets a bit bigger, the hardness of the problem of finding the solution gets much harder. It seems that the source of this claim is this article. Thus, just using simple, naive approaches to solving Kakuro puzzles, should not be expected to give the right result all the time.

The solver

Before I go on to explain how my Kakuro solver works exactly, let’s first show off the meat.

The program (Java JAR file downloadable here, Netbeans project here) features a pretty simple user interface, as shown below:

The program comes with three sample Kakuros, and other Kakuros, saved in text format like this example, can be loaded into the program.

In each cell, the yellow squares indicate which numeric values are still possible; since no calculation has been done in this puzzle, every possibility is still considered open. The text in the status bar indicates the combinations that are due to be considered; in this case, the vertical 17-in-2 in the second column is next.

By pressing the “Iterate 1″ button, the 17-in-2 is considered. Since either 17=8+9 or 17=9+8, we now know that the two cells in the second column are both 8 or 9. By pressing the “Iterate S” button, all combinations are tried to see which numbers are possible, until this gives no new results. In many cases, this will already have completely solved the puzzle, but not in this case: we are left with the diagram below:

Now, a more advanced method needs to be applied, as can be seen because a “T” is placed after the 10-in-2 displayed in the status bar. Basically what will happen is that all possibilities for the 10-in-2 that are still open (in this case, 10=8+2 or 10=9+1) will be filled in, and the algorithm will see what happens using the simple calculation as done above. All possibilities for the cells that actually never occur in this way are then crossed out.

Pressing “Iterate 1″ will do one of these steps; pressing “Iterate A” will do this for all sequences until it has found a solution. In this case, 10=8+2 will quickly lead to a contradiction elsewhere in the puzzle, so 10=9+1 has to be right and the rest of the diagram is simple to fill in:

Pretty cool, eh? One final option is that when you click on a sum value or on a cell, all possibilities for this sum value or cell will be tried out, and similar to the above, all values that never occur are striped out. For example, if after pressing the “Iterate S” we try all possible values for the 22-in-4, we now know that the 22-in-4 has to be 22=1+5+9+7, but we still don’t know much of the rest of the diagram:

After trying all possibilities for any one of the sequences or cells we don’t know yet, we now still get the solution in the next step.

The algorithm

The obvious way to solve a Kakuro is to list for each sum the ways it can be written, and then check for each possibility whether it is consistent with the information so far. For example in the above diagram, for the 17-in-2 we have that it is either 8+9 or 9+8, so the 10-in-2 has to be 8+2 or 9+1. Then for each cell in the sum, the set of possible values is set to be the set of values that occur in one of the possibilities for the sum. By repeatedly applying this process for all sums (let us call this process simple iteration), in the end we hope to get one unique possibility for each sum.

In fact, that’s not what’s going to happen in general: in the above example, this gives us a unique solution for two of the sums only (in fact, for the larger puzzles that one usually encounters, this is usually enough). So we use another approach: we pick some sum, and for each possible way it can be written, we try filling that in and see what happens when we use simple iteration on each of this possibilities. Then, simularly to above, the set of possible values that any cell in the grid can attain is just the set of possible values that occur in all the grids we tried (what frequently happens is that if one tries to fill in the sums, all but one of them will end up being contradictory, so we know exactly how the sum should be written). Let us call this process level 1-iteration.

So an obvious algorithm would be to try to do simple iteration until this gives no more results, try 1 step of level 1-iteration, then see what simple iteration give again, and so on until we have solved the puzzle, or level 1-iteration gives no more results but the puzzle is not solved (see “Does this solve all Kakuros?” below).

Which is basically what we do, but with some refinements. Obviously it is faster to consider a sum which can be written in a small number of ways (e.g. for 24-in-3 there are 6 possibilities, while for 13-in-3 there are 42). Also, if for none of the cells in the sum the information has changed since we last checked all possibilities, there is no need to do it again.

This leads us, then, to keep a priority queue P with all the possible sequences we need to consider, sorted by the number of possibilities for the sum there were the last time we checked. So the algorithm:

  • gets the sum S with the least number of ways of writing it from P;
  • checks in which ways it can be written that are consistent with our current information about the cells;
  • for each cell, sets the possible values of the cell to be the values that occured in the previous step;
  • for each cell for which the set of possible values changed compared to last time, add the sum in the other direction this cell is also in to the queue P.

Initially, of course, P contains any sum in the Kakuro. Note that to calculate the number of ways in which we can write the sum a priory, we do not need to explicitly construct all these possibilities: with a simple recursive algorithm we can calculate the number of possibilities in which the cell values are increasing, and multiply by n!, where n is the length of the sum.

In fact, we never need to store an explicit list of possibilities for each sum: we can generate this on the fly (the algorithm has an Iterator class for this). This is quite convenient because if we have a large sum, for example a 35-in-7, then we will only consider this when all easier sums are already out of the queue, at which point there are hopefully just a few ways of writing this sum left to consider.

So, where does the level 1-iteration enter? Well, sums also get added to P with a “use level 1-iteration” flag attached to them (obviously placed in the queue after all elements without this flag), according to the following rule:

  • If a sum without flag gets removed from the priority queue, it is added to the queue again with the flag;
  • if a sum is about to be added without the flag, then the sum with flag is first removed from the priority queue.

Thus, at any one time, either the sum is in the queue without flag, or it has been considered and is in the queue with flag, or it has been considered with level 1-iteration and it is not in the queue at all.

Does this solve all Kakuros?

So, because we found out that simple iteration doesn’t work for all puzzles, we added this step of level 1-iteration, which seems to make the algorithm work for at least any puzzle that I have thrown at it. But does this solve any Kakuro that exists?

Well, one can say that if this algorithm cannot solve a given Kakuro, then for any sum in the Kakuro we don’t know, and any value we fill in that is consistent, then we can fill in the puzzle with simple iteration, and this will give us no new information on any of the other sums we don’t know yet.

Given that simple iteration usually gives quite a lot of information, especially locally, and we are assuming that there is an unique solution (so everything that we fill in that isn’t right, should cause a contradiction somewhere), this seems quite a strong property.

However, I still suspect there should be Kakuros that cannot be solved by only level 1-iteration, i.e., to get the solution, we should guess the composition of two different sums simultaneously. I haven’t found one yet, but am very open to suggestions on how one might construct one.

Survey of other solvers

Solving Kakuros is a fun little problem to consider, so of course I’m not the only one who tried his hands at a solver. A quick survey:

  • A K.R. Chandrasekaran wrote a solver, but I didn’t try it and there is no info on the method
  • Zvika Ben-Haim wrote a solver in C# (includes source!), which doesn’t come with documentation but seems to to use the cell with the least number of possible values, tries all possible values and iterates with this. I tested it on the above example, and it worked
  • I didn’t try SAAM’s Kakuro Solver
  • zvrba has written a solver, and claims that Kakuros can always be solved without guessing, i.e. without my level 1-iteration. Should see what happens on the above puzzle
  • Julian wrote about implementing a simplistic solver which does essentially the same as mine but doesn’t have the queue structure and doesn’t seem to have my level 1-iteration. Unfortunately the solver is not available for download
  • Here at Google Code there’s a solver by gravix
  • An actual shareware Kakuro game called Kakuro Epic seems to have a solver
  • This is a solver; no further information available
  • This is a very promising-looking way of looking at Kakuro as a particular instance of a “constraint model”. It also mentions papers and has LaTeX-formulas, so I should look into this

Comments (3 comments)

An interesting discussion, thank you.

You are right in saying my Kakuro Solver has neither your queue nor your guessing 1-layer.

The lack of queue was as an experiment. I used (inefficient) iteration instead. I see the queue as a fundamental part of the architecture, I have attempted and written up <a href=”several different techniques.

The lack of guessing was, at least in part, because I didn’t find I needed it in the (most admittedly very tiny) sample of two real-life puzzles that I tried it out on, including one that was classed at the “Ninja” level.

Julian / December 4th, 2008, 05:44

Wonderful little tool to solve Kakuros, thanks. It only seems to support quadratic input instances, though, or am I mistaken? It didn’t accept my 10×9 input until I inserted a whole column consisting of “xxxx” blocks.

Karsten Hiddemann / June 6th, 2011, 11:19

Looking for a Kakuro solver and landed on this – using it on examples from the WIndows 8 “Metro” App Kakuro Master by Croys Apps. This seems to have a lot of examples that cannot be solved by logic and need a guess or iteration to get started.
You were looking for an example that could not be solved – the one below fails!

Is that because the solver runs out of ideas or because the solution is not unique? I’ve noticed that many of the examples in the app do have multiple possible answers (I’ve put in extra rows of xxxx to square things up as per Karsten’s comment.

| | |26 |09 |09 |09 |31 | |
| |1733| | | | | |09 |
|0522| | | | 09| | | |04
13| | | |03 |xxxx|0918| | |
| 07| | | |0106| | | |xxxx
|xxxx| 24| | | | | |xxxx|xxxx
xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx
xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx
xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx
xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx|xxxx

SteveE / March 12th, 2013, 16:59

What do you think?

Logged in as admin. (Logout)

Categories