What is Kakuro?
Kakuro is an arithmetic puzzle on a grid such as the one shown here. The grid is made of two types of cells: red and white. The white cells must be filled with the digits 1 to 9 according to clues placed in some of the red cells. A clue gives the sum of an uninterrupted column of white cells below or an uninterrupted row to the right of the clue. The only other rule of Kakuro is that a digit cannot repeat in the solution of a clue. For example, if a clue is 4, then one can have but not .
In this web site I give some tips on how to solve Kakuro puzzles through several examples. Each example is on a different web page; you can navigate through them using the navbar on top of the pages. The discussion for each example starts from tips and solution to detailed discussion of the mathematical structure that arises in each solution. You can break off at any point in this discussion and go on to another example without losing much. The main point to this tutorial is that Kakuro need not be hard: you can break up many Kakuro puzzles into smaller puzzles which are much easier to do. Using this idea one can prove that some of the smaller versions of Kakuro are in P and not in NP. Kakuro itself has been proven to be in NP.
We need some notation to refer to cells. That is indicated by the letters on the side of the grid above. Each cell is named using an upper case and a lower case letter. The top left cell is always Aa, and the remainder follow alphabetically. The rows are labelled by capital letters: for example, A is always the top row. The columns are labelled by lower case letters: as an example, the leftmost column is always labelled a. The notation [N] denotes the number in the cell labelled N. For example, in the above picture, the clue on row C means . If all this reminds you of spreadsheets, then I count myself successful.
The mathematical content of the method is the following. The number of cells to be filled in exceeds the number of clues. Finding the minimum number of free variables is a straightforward problem in linear algebra; the tedium involved can be eliminated by a process similiar to spreadsheets. Once these free variables have been found, the process of solving the puzzle is that of integer linear programming. In simple puzzles this part is straightforward. Satisfactory puzzles are those where complex choices must be made to reach a simple solution. Unfortunately no theorem excludes tiresome puzzles, namely those in which the full theoretical apparatus must be brought to bear on the puzzle.
Among Kakuro references, one could single out the Wikipedia entry for the usual reasons, and kakuro.com for reasons of popularity. Tutorials available on the web follow combinatorial methods, quite different from the one I suggest here. The best such tutorials I have come across are Grosse is a geek :: Kakuro Tutorial and Indigo Puzzles - Help.
© Sourendu Gupta. Mail me if you want to reproduce any part of this page. My mailing address is a simple (satisfactory) puzzle for you to solve. Created on 23 November, 2006.