The Spoony Blog

Kakuro (also known as Cross Sums) is a popular number-based logic puzzle. It resembles crossword puzzles, except instead of clues made up of words, you have clues made up of numbers indicating the sum of the digits in the indicated cells, with the additional constraint that no entry contain the same digit more than once.

The MIT Mystery Hunt is no stranger to Kakuros. It has featured a number of Kakuro variants over the years, most of which often involve some special trick or gimmick not present in a standard Kakuro puzzle. Of course, figuring that out is part of the puzzle.

The 2009 Hunt featured an intriguing puzzle named Cross Something-Or-Others, by Thomas Snyder and Dan Katz. It had 8 different Kakuro variants (Nonsense Kakuro does not count). After the Hunt was over, I decided to write a generic, optimized Kakuro solver that could solve all of these variants for help with future Hunts. Although I did not get to use my solver during the 2010 Hunt (I missed whatever Kakuros there were, if there were any at all), I hope this will be useful for puzzle solvers present and future.

There are many other solvers out there (and more), but none of them were adequate enough for me. They all had various issues: some had no source code (making solving variants impossible), they had a horrendous interface for inputting puzzles, they weren’t portable enough, or they were too slow.

Actually, I probably could have gone with zvrba’s solver and modified it, but I decided to start from scratch anyways. “There are many like it, but this one is mine”, as the saying goes.

So anyways, back to my solver. I wrote it from the ground up to be blazing fast. It stores the set of possible values a cell can have using a bit set, and it uses some inline assembly (specifically the x86’s BSF and BSR instructions). So, it’s not completely portable out-of-the-box, but those can be replaced easily enough with generic C routines that will be slower, or the equivalent instructions on other ISAs. It also uses the pthreads library for multithreading. If you want to compile it for a platform that does not support pthreads (such as Windows), you can either replace pthreads with your platform’s equivalent, or nuke the threading support entirely. But other than those two things, the program is completely portable C.

Secondly, I also designed the solver to be as generic as possible, in order to be able to solve (or be modified to solve) as many different Kakuro variants as possible. The most flexible piece is the set of allowable numbers in a cell. In standard Kakuro, that set of numbers is 1–9. Common variants include allowing 0, or changing the base to make something like hexadecimal Kakuro (1–15). My solver allows any subset of the numbers 0–30; it could easily be modified to use a subset of 0–63, but I haven’t bothered with that yet, since extending that support might slow it down a little (probably not very much though) on 32-bit machines, and I’ve never seen a puzzle that uses cells with numbers that large.

I also coded up modifications to solve most of the variants in the puzzles linked to above. Again, for maximal speed, the logic in these variants is controlled by various #defines, producing separate binaries for each of them.

So how does it work? Under the hood, it’s got one simple rule, followed by a brute-force search. That one rule is:

• The minimum possible value for a cell is given by the total sum of the numbers in the entry (the clue) minus the sum of the maximum possible values of all of the other cells in the entry
• The maximum possible value for a cell is given by the total sum minus the sum of the minimum possible values of all of the other cells in the entry

It turns out that this is often all you need, especially for simple puzzles. This does not try to enumerate all possible sets of values for an entry—in other words, for a 2-cell clue with a sum of 4, it does not deduce that 2 is not a possible value for either cell. It only determines that 1–3 are legal values, since that is 4 (the sum) minus 1 (the minimum value for the other cell).

It also performs other logic which I consider so obvious that it shouldn’t need stating, but here it is anyways: if a cell can only contain one number, then all other cells in the two entries that go through that cell cannot take on that value.

It repeats this logic for every cell for every clue in both the across and down directions as long as it continues to make progress by eliminating numbers as possible values for cells. If you’re lucky, it might solve the entire puzzle this way (this is very fast). If you’re not so lucky, it starts a brute-force depth-first search of the entire remaining puzzle space and attempts to enumerate all possible solutions.

The brute-force search isn’t a dumb search, though. It picks one cell, iterates through all possible allowed values for that cell, and recurses. The cell that it picks is one that belongs to the entry that has the fewest possible total values, which is computed as the product of the number of values of each cell in that entry; once the entry is determined, the first cell with more than one possible value is used. The idea here is that for incorrect guesses (which most are), we want to reach a contradiction as quickly as possible, which we try to do by picking an entry with a small number of possibilities. In my tests, this usually seems to give vastly better results, but not always, when compared to just picking the first cell that can have multiple values.

Ok, enough with the discussion, you’ve been patient enough. You can download my Kakuro solver’s source code here. It’s licensed under the GPL version 3 or later. Comments are most welcome!

Filed under:
Programming by adam