Kakuro solver

Friday, August 18, 2006

Kakuro solver

What is Kakuro Solver?

This blog details one possible programmatically implementation of Kakuro Solver.

What is Kakuro?

Kakuro is a great, entertaining and incredibly addictive puzzle game.
It is basically the mathematical transliteration of crosswords (that is why it is also known as Cross-Sums).
Kakuro is often referred as the "brother" of Sudoku, another great puzzle having sensational worldwide success.

The rules are:
1. Place a single number from 1 to 9 in each empty cell.
2. Numbers may only be used once in each run (run is vertical or horizontal one lined block).
3. The sum of all numbers in a run must be equal to the clue square value (the number at beginning of the run).

In www.KakuroPlay.com you will be able to learn how to play Kakuro and even play Kakuro puzzles online for free with great user interface, three different game difficulties, turorials and discussion forum.

The Problem

Few years ago I was sure that machines can do/calculate everything, just give the machine the right equipment (Memory, CPU, Storage) and it will do it for you, no problem.
And you know what, even if it will take 2 or 3 seconds, it will still solve the problem and if it won't we will give the machine another few seconds and it all will be behind us.
I remember once, when I was in high-school, I was thinking to myself, why can't somebody make the hours schedule windowsless (meaning without the free windows during the day when you have nothing to do). It does not sound right! What, can't somebody write a program to calculate the best hours schedule for my school?
So, I tried writing it my self. Believe me, I was so naive.
As you expect I could not do it, I was amazed to see how "weak" the machine is. When the program I wrote run for over an hour I stopped the program at a break point and I was amazed to see how little it has covered in this hour. It would take ages to do so !!!
Well, it turns out that there are so many problems machines can not solve, problems like Knapsack problem, Traveling salesman problem, Clique problem and much more.
I suggest you will read about these kind of problems and even harder, start look at NP-Complete problems.

Anyhow, back to our Kakuro.

Solving a Kakuro game can be hard problem. In this blog I will detail pretty simple and intuitive solution for the solving a Kakuro game.

The Strategy

So, how does one solve a Kakuro puzzle.

The simple, intuitive and naive solution is this:

1. Find out all possible numbers to place in each empty cell of the puzzle. You should have two sequences of numbers, one for the horizontal run and one for the vertical run.
2. Intersect the two sequences. That way you will be left only with the possible numbers to place which match the horizontal and vertical restrictions.
3. If 2 was successful, repeat 1 and 2 again.
4. Choose a square with as little possible numbers to place as possible and iterate that square will all possible numbers by placing the next possible value and going back to step 1.

The tactics

The board

The board is a matrix. Each cell in the matrix is either a white cell, a clue cell or a black cell (which is meaningless).
The white cell contains pointers to his corresponding clue cells (horizontal and vertical clue cells).
The clue cell contains the amount of cells it has for it runs (horizontal and vertical).


To start the Kakuro Solver you simply have to create the board with all the right cells.
Place only the clue values and start the process...

Step 1

Go over all empty white cells left in the board (Optimization hint, always keep a list of empty white cells in the board).
For each empty white cell, calculate all the possible values for its horizontal clue and for its vertical clue.
The possible values are simply combination of the amount of cells for the corresponding clue cell run with the clue cell values. If the clue cell run is 2 cells and the clue cell value is 5 then the possible values are 1, 4 or 2, 3. (Optimization hint, keep in a hash table all the combination possible values you already calculated or pre calculate all possible combinations and store them before the program runs).
Reduce from each possible values list, the current existing values in the run. Pay attention that this is a little bit tricky. If that run has no values then all possible values are possible, but if that run has one value, you should remove that value and its matching combination items and not only the value.
(Example, if a run holds 2 cells and the clue is 5, the possible values are 1 + 4 and 2 + 3. If both the cells are empty, the possible values for one of the cells is 1, 4, 2 and 3, but if one cell holds the value 2, it means that the possible values for the other empty cell is not 1, 4 and 3 but only 1 and 4).

Step 2

Intersect the two reduced list you calculated.
If you have only one value left, place that value of that square.
If you have more than one value, keep that list of values for future use.

Do that for all empty cells.

Step 3

If step 2 was successful, go to step 1 and try again to find "easy" cells (Optimization hint, you should check only the cells belonging to the same runs as the updated cells).
If step 2 was not successful you have to proceed to the "guessing " route, step 4.

Step 4

If you got to this step, you will have to "guess" the next possible value and hope that it works.
Choose the empty cells with as little as possible values to place.
Iterate all possible values for that cell, place the value and go back to step 1. This is the hardest and longest part of the algorithm.


If the Kakuro puzzle can be solved with only steps 1 and 2, the upper bound complexity is reasonable even for big boards.
If the Kakuro puzzle will lead you to step 4, you will be unable to find a solution for very big boards.

Does it work?

I tried to solve many Kakuro puzzles, puzzles up to the size of 11x11. The algorithm worked perfectly even if the puzzle led me to activate my big step 4 routine.

Great, it works !!