Kakuro

Easy Cross Sums puzzle

The Cross Sums is a very common type of logic puzzle that is often referred to as a mathematical transliteration of the crossword. In principle, Cross Sums puzzles are integer programming problems, and can be solved using matrix techniques, although they are typically solved by hand. Cross Sums are regular features in most, if not all, math-and-logic puzzle publications in the United States; Dell Magazines uses the Cross Sums name, which was formerly unique to them but is now in common use among various publishers (although some other names, such as Cross Addition, are still used). In Japan, where the puzzle is called Kakro, its popularity is immense, second only to Sudoku among Nikoli's famed logic-puzzle offerings; in an international tapdance, Kappa reprints Nikoli Kakro in the United States, in GAMES Magazine under the name Cross Sums, and The Guardian in Britain prints it under the name Kakuro.

Standard play and terminology

The canonical Cross Sums puzzle is played in a grid of filled and empty cells - "black" and "white", respectively - usually 16×16 in size but can vary widely. Apart from the top row and leftmost column - which are entirely black - the grid, just like a crossword, is divided into "entries" - orthogonal lines of white cells - by the black cells. The black cells themselves - possibly barring those in a cluster - are not entirely solid but rather contain a diagonal slash from upper-left to lower-right and a number in one or both halves, such that all horizontal entries have a number in the black half-cell to their immediate left and all vertical entries have a number in the black half-cell immediately above it. These numbers, continuing the borrowed crossword terminology, are commonly called "clues".

The object of the puzzle is to insert a digit from 1 to 9 inclusive into each white cell such that the sum of the numbers in each entry matches the clue associated with it and that no digit is duplicated in any entry. It is that lack of duplication that makes creating Cross Sums with unique solutions possible.

Some publishers prefer to print their Cross Sums grids exactly like crossword grids, with no labelling in the black cells and instead numbering the entries, providing a separate list of the clues akin to a list of crossword clues. (This eliminates the row and column that are entirely black.) This is purely an issue of image and does not affect solving (at least, not beyond the degree of needing to look outside the grid to solve).

In discussing Cross Sums puzzles and tactics, the typical shorthand for referring to an entry is "(clue, in numerals)-in-(number of cells in entry, spelled out)", such as "16-in-two" and "25-in-five". The exception is what would otherwise be called the "45-in-nine" - simply "45" is used, since the "-in-nine" is mathematically implied (nine cells is the longest possible entry, and since it cannot duplicate a digit it must consist of all the digits from 1 to 9 once). Curiously, "3-in-two", "4-in-two", and "5-in-two" are still called as such, despite the "-in-two" being equally implied.

Solving techniques

Although brute-force guessing is of course employable, a better weapon is the understanding of the various combinatorial forms that entries can take for various pairings of clues and entry lengths. Those entries with sufficiently large or small clues for their length will have fewer possible combinations to consider, and by comparing them with entries that cross them, the proper permutation - or part of it - can be derived. The simplest example is where a 3-in-two crosses a 4-in-two: the 3-in-two must consist of '1' and '2' in some order; the 4-in-two (since '2' cannot be duplicated) must consist of '1' and '3' in some order. Therefore, their intersection must be '1', the only digit they have in common.

A "box technique" can also be applied on occasion, when the geometry of the unfilled white cells at any given stage of solving lends itself to it: by summing the clues for a series of horizontal entries (subtracting out the values of any digits already added to those entries) and subtracting the clues for a mostly-overlapping series of vertical entries, the difference can reveal the value of a partial entry, often a single cell.

It is common practice to mark potential values for cells in the cell corners until all but one have been proven impossible; for particularly challenging puzzles, sometimes entire ranges of values for cells are noted by solvers in the hope of eventually finding sufficient constraints to those ranges from crossing entries to be able to narrow the ranges to single values.

Possible sums

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

This list is easily expanded. 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.

Mathematics of Cross Sums

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.

Variants

A relatively common variant of Cross Sums is its logical successor, Cross Products (or Cross Multiplication), where the clues are the product of the digits in the entries rather than the sum. Another variant is Arrow Numbers, where the combinations for each clue value cannot be repeated within the grid.

The final puzzle of the 2004 United States qualifier for the World Puzzle Championship is titled Cross Number Sums Place: it is a Cross Sums where every row and column of the grid (except the top row and leftmost column as usual) contains exactly nine white cells, none of which - even across multiple entries - are allowed to contain multiple digits, like a Number Place (Sudoku); in addition, small circles are printed on the borders between some white cells; arithmetically adjacent digits must be placed astride those circles, and may not appear orthogonally adjacent when not astride a circle.

External links

• Tutorial at Nikoli (Macromedia Flash required)
• Rules and walkthrough at Puzzle Japan
• Cross Sums
• Cross Sums Number Combination Guide: Guide detailing the various number combinations that are possible for a certain number of blanks and a certain number of spaces. Site also has a free number finder for cross sums.
• Kakuro Walkthroughs
• Kakuro Cross Sums daily puzzles Site providing different Kakuro cross sums every day and some examples of huge puzzles.
• Kakuro-san Daily graded puzzles, a good tutorial, and an Online Assistant with Help feature