Kakuro

Kakuro or Kakkuro or Kakoro (Japanese: カックロ) is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. Kakuro puzzles are regular features in many math-and-logic puzzle publications across the world. In 1966,[1] Canadian Jacob E. Funk, an employee of Dell Magazines, came up with the original English name Cross Sums [2] and other names such as Cross Addition have also been used, but the Japanese name Kakuro, abbreviation of Japanese kasan kurosu (加算クロス, "addition cross"), seems to have gained general acceptance and the puzzles appear to be titled this way now in most publications. The popularity of Kakuro in Japan is immense, second only to Sudoku among Nikoli's famed logic-puzzle offerings.[2]

An easy Kakuro puzzle
Solution for the above puzzle

The canonical Kakuro puzzle is played in a grid of filled and barred cells, "black" and "white" respectively. Puzzles are usually 16×16 in size, although these dimensions can vary widely. Apart from the top row and leftmost column which are entirely black, the grid is divided into "entries"—lines of white cells—by the black cells. The black cells contain a diagonal slash from upper-left to lower-right and a number in one or both halves, such that each horizontal entry has a number in the half-cell to its immediate left and each vertical entry has a number in the half-cell immediately above it. These numbers, borrowing crossword terminology, are commonly called "clues".

The objective of the puzzle is to insert a digit from 1 to 9 inclusive into each white cell so 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 Kakuro puzzles with unique solutions possible. Like Sudoku, solving a Kakuro puzzle involves investigating combinations and permutations. There is an unwritten rule for making Kakuro puzzles that each clue must have at least two numbers that add up to it, since including only one number is mathematically trivial when solving Kakuro puzzles.

At least one publisher[3] includes the constraint that a given combination of numbers can only be used once in each grid, but still markets the puzzles as plain Kakuro.

Some publishers prefer to print their Kakuro grids exactly like crossword grids, with no labeling 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 either the solution nor the logic required for solving.

In discussing Kakuro 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, both "43-in-eight" and "44-in-eight" are still frequently called as such, despite the "-in-eight" suffix being equally implied.

Solving techniques

Combinatoric techniques

Although brute-force guessing is possible, a more efficient approach is the understanding of the various combinatorial forms that entries can take for various pairings of clues and entry lengths. The solution space can be reduced by resolving allowable intersections of horizontal and vertical sums, or by considering necessary or missing values.

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.

When solving longer sums there are additional ways to find clues to locating the correct digits. One such method would be to note where a few squares together share possible values thereby eliminating the possibility that other squares in that sum could have those values. For instance, if two 4-in-two clues cross with a longer sum, then the 1 and 3 in the solution must be in those two squares and those digits cannot be used elsewhere in that sum.[4]

When solving sums that have a limited number of solution sets then that can lead to useful clues. For instance, a 30-in-seven sum only has two solution sets: {1,2,3,4,5,6,9} and {1,2,3,4,5,7,8}. If one of the squares in that sum can only take on the values of {8,9} (if the crossing clue is a 17-in-two sum, for example) then that not only becomes an indicator of which solution set fits this sum, it eliminates the possibility of any other digit in the sum being either of those two values, even before determining which of the two values fits in that square.

Another useful approach in more complex puzzles is to identify which square a digit goes in by eliminating other locations within the sum. If all of the crossing clues of a sum have many possible values, but it can be determined that there is only one square that could have a particular value which the sum in question must have, then whatever other possible values the crossing sum would allow, that intersection must be the isolated value. For example, a 36-in-eight sum must contain all digits except 9. If only one of the squares could take on the value of 2 then that must be the answer for that square.

Box technique

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. This technique works because addition is both associative and commutative.

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. Because of space constraints, instead of digits, some solvers use a positional notation, where a potential numerical value is represented by a mark in a particular part of the cell, which makes it easy to place several potential values into a single cell. This also makes it easier to distinguish potential values from solution values.

Some solvers also use graph paper to try various digit combinations before writing them into the puzzle grids.

As in the Sudoku case, only relatively easy Kakuro puzzles can be solved with the above-mentioned techniques. Harder ones require the use of various types of chain patterns, the same kinds as appear in Sudoku (see Pattern-Based Constraint Satisfaction and Logic Puzzles[5]).

Mathematics of Kakuro

Mathematically, Kakuro puzzles can be represented as integer programming problems, and are NP-complete.[6] See also Yato and Seta, 2004.[7]

There are two kinds of mathematical symmetry readily identifiable in Kakuro puzzles: 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.

Popularity

Kakuro puzzles appear in nearly 100 Japanese magazines and newspapers. Kakuro remained the most popular logic puzzle in Japanese printed press until 1992, when Sudoku took the top spot.[8] In the UK, they first appeared in The Guardian, with The Telegraph and the Daily Mail following.[9]

See also
  • Killer Sudoku, a variant of Sudoku which is solved using similar techniques.

References
  1. Timmerman, Charles (2006). The Everything Kakuro Challenge Book. Adams Media. p. ix. ISBN 9781598690576. Retrieved November 18, 2018.
  2. "Kakuro history". Retrieved November 18, 2018.
  3. "Sudoku From Denksport". Keesing Group B.V. Retrieved November 18, 2018.
  4. "Kakuro rules". Retrieved November 18, 2018.
  5. Berthier, Denis (April 5, 2013). "Pattern-Based Constraint Satisfaction and Logic Puzzles". arXiv:1304.1628 [cs.AI].
  6. Takahiro, Seta (February 5, 2002). "The complexities of puzzles, cross sum and their another solution problems (ASP)" (PDF). Retrieved November 18, 2018.
  7. Yato, Takayuki; Seta, Takahiro (2004). "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles" (PDF). Retrieved November 18, 2018. {{cite journal}}: Cite journal requires |journal= (help)
  8. "What is Kakuro". Retrieved November 18, 2018.
  9. "Kakuro History". Retrieved November 18, 2018.
Wikimedia Commons has media related to Kakuro.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.