Categories

# Classics Collection: Kakuro

Hi folks,
the Classics Collection continues! There will probably be another Beginners Contest next, but we already have more puzzle types in mind to go on with our series. Kakuro is certainly a “classic” style; it is not particularly rich in solving techniques, but those who enjoy arithmetic-based logical puzzles will typically get what they pay for. Here is the PDF file: Kakuro

Since Kakuro grids do not have to be quadratic, there are no standard grid sizes for this puzzle type. (In fact, there are Kakuros of virtually every reasonable size and every height-to-width ratio around.) Today’s set consists of twelve grids of slowly increasing size. As usual, the first half is designed to demonstrate typical solving steps. The second half is already quite demanding for a beginner’s set, and the last two puzzles are especially tricky.

Rules: Enter a number from 1 to 9 into each white cell. The numbers in grey cells indicate the sums of the numbers in the horizontally or vertically adjacent “words”. Within each word, no number can appear more than once.

Note that some cells are circled. The circles can be ignored for the purpose of solving the puzzles, they are just relevant for the solution code.

Example and solution:

The rules are pretty much self-explanatory. It is worth emphasizing, though, that the rule about repeating digits applies only to “words” (we will use this expression repeatedly), not to full rows or columns of the grid. For example, the bottom row contains two 3’s, just in different words within the same row. This is allowed, and in practice such repetitions will occur all over the place.

The solution code may also contain digits more than once. By the way, I have tried to keep things simple by just circling one diagonal sequence of cells. The answer key for Kakuros in (online) competitive events often consists of several such diagonals. The circled sequences in Kakuro 9 and Kakuro 11 from the PDF file pass through some grey cells; please ignore these cell when entering the code.

Regarding terminoloy, I suggest we use the expression RxCy to designate the cell in Row x and Column y of the entire grid, not just the white area. For instance, the top entries in the example go into the cells R2C2, R2C3, R2C5 and R2C6. This agreement makes it easier to speak about entry cells and clues for arbitrary shapes in a uniform manner.

Now, let us dicuss solving techniques. Obviously, a general familiarity with arithmetic thinking helps. More precisely, in order to solve a Kakuro efficiently one must be able to determine all the ways to decompose a given sum into a fixed number of distinct summands. For example, a sum of 12 can be reached from three summands as 1+2+9, 1+3+8, 1+4+7, 1+5+6, 2+3+7, 2+4+6 and 3+4+5. When entering the digits, permutations come into play, of course; when speaking about decompositions, we will typically ignore them and use an ascending or descending order.

It is not necessary to memorize all the possible decompositions when there is such a large number of them. However, it is helpful to know the “extreme” cases. For instance, 3=1+2 is the minimal sum for two summands, 17=9+8 is maximal. For three summands, the extremes are 6=1+2+3 and 24=9+8+7, and so on. Note that the decomposition is also unique for a sum that is larger by 1 than the minimum or smaller by 1 than the maximum (e.g. 4=1+3, 16=9+7, 7=1+2+4 or 23=9+8+6). Experienced Kakuro solvers know these specific constellations – and perhaps a few others – by heart.

You may notice that the puzzle type as a whole is “invertible”, that is, if one replaces each entry N by 10-N and each clue C by K*10-C (where K denotes the number of summands), one obtains another solved Kakuro which also has essentially the same solving steps. This knowledge is not really helpful when solving a Kakuro, but Kakuro authors will typically design their creations such that some areas contain many large clues/entries and others contain many small ones, for the sake of diversity.

The most basic entry points are extreme sums, ideally with only two or three summands, since they provide rather small sets of candidates. (Candidates are the potential entries for a cell in question. For what follows, I will assume that you are already familiar with candidates from other Filling Puzzles, such as Sudokus or Skyscrapers. An understanding of candidates is essential in order to get started with Kakuros.)

Junction cells for such sums can lead to definitive entries very quickly: If the respective candidate sets have only one number in common, it can be entered at once. For example, the cell R4C6 in Kakuro 1 from the PDF file must contain a 1 because that is the only common candidate from 4=1+3 and 3=1+2. It clearly makes sense to search for extreme sums at the beginning, and in particular intersections of those.

Sometimes, it is enough to have only one restrictive candidate set. For instance, the cell R2C4 can only accomodate a 8 or 9 due to the vertical sum. The horizontal clue is a priori not very restrictive, but since a sum of 9 cannot use any single summand of 9, the 8 is the only remaining candidate. Eliminations of this type are also very typical.

This technique is not limited to sums from two summands. The corner cell R6C6 in Kakuro 2 can only contain an entry of 1; the almost-extreme sum 7=1+2+4 has three summands and still rules out an entry of 3. The cell R2C3 in the same puzzle lies at the junction of one restrictive and one non-restrictive clue, and the outcome is again a unique entry.

In general, you may find constellations where one clue of an intersections requires mostly large summands and the other needs small ones; we might call this a min-max argument. Even if either clue by itself offers a lot of choices, the cell at the junction point might remain with just a single candidate. For example, if there are sums of 22 and 8 intersecting, both with three summands, the only common candidate is 5. You will not find this particular pairing anywhere in today’s set, but it is worth keeping one’s eyes open for similar min-max constellations.

Some sums allow various decompositions, but they all share a common summand. The 22 with three summands was such an example; it simply does not work without a 9. On the other hand, there are sums which cannot use a specific candidate, despite an abundance of possible decompositions. We have already seen such occurrences where the summand in question would be too large or too small. Other typical cases are even sums with two summands. For example, a 12 rules out summands of 1 and 2 simply due to size reasons, but a candidate of 6 as well. This step reduces the candidate set in R2C2 of Kakuro 4, for example.

Whenever one has a sum with two summands and the candidates for one of the respective two cells are already under investigation, it makes sense to also consider the corresponding candidates in the other cell; the point is that one entry automatically determines the other. (This typically does not work that well when there are three or more summands, unless some of the entries are already known.) Even if only specific candidates can be eliminated and more than one possibility remains, you never know whether there will come a point when the knowledge of the corresponding candidates suddenly turns out useful.

There are cases where the candidates for a single cell are not sufficient to make progress, but studying the candidates for groups of cells leads to progress. For example, the cells R3C7 and R4C7 in Kakuro 3 share the candidates 7 and 9. What we have here is the equivalent of a Pointing Pair (a technique known from Sudokus). As a consequence, no other cell in the same vertical word can contain either of these two digits.

If we combine the last two techniques, we are getting somewhere: The entry in R3C8 must be 7 or 9, so the corresponding candidates for the cell R2C8 are 2 and 4. This leads to candidates 5 or 7 in R2C7, but only one of the two possibilities survives the pointing pair. Thus we can enter a 5 in R2C7 and, retracing our steps, fill this entire block at once. Such progress is typical for regions in Kakuros which have many sums with two summands. It is often worth taking the time and entering the candidates, even though it may take several steps to reach a contradiction for a certain candidate.

We move on to a completely different kind of technique, sometimes referred to as the “Law of Leftovers”. It can best be explained by means of a specific example. Let us have a look at the puzzle Kakuro 4. The sum of the two horizontal clues in the bottom rows tells us that the total of the seven entries in these row is 36. On the other hand, if we add um the three vertical sums in the same area, we obtain a total of 28 for six of the seven cells. The difference between the total horizontal and vertical sum must be equal to the remaining entry, hence we can enter the digit 8 in R6C5.

Comparing the sum of horizontal and vertical clues is particularly fruitful when there is an almost closed region, like the “chamber” we have here: it yields an entry at once if the difference of the covered areas is just a single cell. The same technique also yields the value of R3C5. Please observe that at this point we obtain several independent smaller puzzles within the original grid, since the remaining groups of white cells do not interact with each other any more at all.

There are weaker forms of this technique. For example, one can deduce the sum of the cells R7C4 and R7C5 in Kakuro 6; this time the difference of the covered areas consists of two cells (and we obtain an extreme sum for a partial word). Similarly, we can compute the sum of the entries in R3C2 and R3C3 in Kakuro 5. However, this constellation is not quite chamber-like, and the technique does not lead to substantial progress here.

If we had not already used the pointing pair, we could do the same thing in the top-right part of Kakuro 3. The Law of Leftover tells us that the entries in R4C7 and R5C7 add up to 9, which in particular eliminates the candidate of 9 from R4C7. And there is another way to look at this formation: If we include the horizontal sum of 16 into our computation, we find that the difference between R4C6 and R5C7 must be 7, hence the entry in R4C6 must be at least 8. Such difference considerations are generally weaker but can still produce helpful results if a region of the grid is only almost a chamber, especially if the given sums have the potential for min-max arguments.

Let me mention one more technique. So far we have only studied sums with very few summands. Long words can also lead to progress in terms of candidates. We know that the sum of all nine digits is 45, so if he have exactly eight summands – as in the long white row in Kakuro 5 – we can immediately conclude which entry is missing. This is kind of an “inversion” argument (different from the type of inversion mentioned above). One can study which candidates do not occur in large words: a sum 28 with seven summands must be missing 8 and 9, a sum of 42 must be missing 1 and 2, and so on.

So much for an introduction to solving steps; in fact, I do not think there is much more, except that larger and harder puzzles make use of the same techniques by means of more complex constellations. Like I said, the second half of today’s set is a lot more challenging, but basically it requires little more than repeated applications of the same techniques. In large Kakuros, the difficulty often lies in the search for the next useful clues (or groups of clues). Anyway, I hope you enjoy the puzzles.