What Is Kakuro (Cross Sums) - Solving Kakuro Puzzles
Mathematics of Kakuro - Kakuro Variations - Links
Like Kakuro? Try Sudoku!

Mathematics of Kakuro

Cross Sums are NP-complete.

There are two kinds of mathematical symmetry readily identifiable in Cross Sums. Minimum and maximum constraints are duals, as are missing and required values.
All sum combinations can be represented using a bitmapped representation. This representation is useful for determining missing and required values using bitwise logic operations.

Here is a list of some of the clue/length pairings with only one legal combination in a Cross Sums puzzle; note that the order of the digits must still be determined:

3-in-two: 1, 2
4-in-two: 1, 3
16-in-two: 7, 9
17-in-two: 8, 9
6-in-three: 1, 2, 3
7-in-three: 1, 2, 4
23-in-three: 6, 8, 9
24-in-three: 7, 8, 9
10-in-four: 1, 2, 3, 4
11-in-four: 1, 2, 3, 5
29-in-four: 5, 7, 8, 9
30-in-four: 6, 7, 8, 9
15-in-five: 1, 2, 3, 4, 5
16-in-five: 1, 2, 3, 4, 6
34-in-five: 4, 6, 7, 8, 9
35-in-five: 5, 6, 7, 8, 9
21-in-six: 1, 2, 3, 4, 5, 6
22-in-six: 1, 2, 3, 4, 5, 7
38-in-six: 3, 5, 6, 7, 8, 9
39-in-six: 4, 5, 6, 7, 8, 9
41-in-seven: 2, 4, 5, 6, 7, 8, 9
42-in-seven: 3, 4, 5, 6, 7, 8, 9

Any eight- or nine-cell entry has only one combination: nine-cell entries always have all digits from '1' to '9' and therefore are always clued as "45"; eight-cell entries are necessarily clued as 45 minus the value of the missing digit. Kakuro Combinations is a complete table of combinations while Kakuro Helper by Koalog is an interactive assistant displaying the combinations corresponding to a given sum and a given number of cells (These are also candidates for solving the puzzle known as Killer Sudoku.)

For practical solving an abbreviated list is useful as follows

Minimum vales for each clue length

3 = 1, 2
6 = 1, 2, 3
10 = 1, 2, 3, 4
15 = 1, 2, 3, 4, 5
21 = 1, 2, 3, 4, 5, 6
28 = 1, 2, 3, 4, 5, 6, 7
36 = 1, 2, 3, 4, 5, 6, 7, 8
45 = 1, 2, 3, 4, 5, 6, 7, 8, 9

(the triangular numbers)

Maximum vales for each clue length

17 = 9, 8
24 = 9, 8, 7
30 = 9, 8, 7, 6
35 = 9, 8, 7, 6, 5
39 = 9, 8, 7, 6, 5, 4
42 = 9, 8, 7, 6, 5, 4, 3
44 = 9, 8, 7, 6, 5, 4, 3, 2
45 = 9, 8, 7, 6, 5, 4, 3, 2, 1

This list can be constructed rapidly and provides an effective memory aid to the additional unique combinations. For example the minimum value combination for clue length four is 10 = 1, 2, 3 ,4, the next highest value for this clue length is 11 and the only combination which produces this is 1, 2 ,3 ,5

Didn't Find What You Were Looking For? Try Google!