Creating a Kakuro puzzle with a unique solution

Question

I start with a grid of black and white cells. I randomly populate the white cells from numbers (1-9) using Kakuro rules. Then I calculate the horizontal and vertical sums. I remove the numbers from the white cells and try to solve it using Kakuro rules from sums. But I get multiple solutions. How can I generate Kakuro puzzles that will have unique solutions?

Answer 1

Kakuro is a type of puzzle that is better created using a bottom-up process, in which you specify one or two sums at a time and explore the logical implications of those moves.

Take a look at this list of combinations for 3 cells:

 6: 123
 7: 124
 8: 125 134
 9: 126 135 234
10: 127 136 145 235
11: 128 137 146 236 245
12: 129 138 147 156 237 246 345
13: 139 148 157 238 247 256 346
14: 149 158 167 239 248 257 347 356
15: 159 168 249 258 267 348 357 456
16: 169 178 259 268 349 358 367 457
17: 179 269 278 359 368 458 467
18: 189 279 369 378 459 468 567
19: 289 379 469 478 568
20: 389 479 569 578
21: 489 579 678
22: 589 679
23: 689
24: 789

An interesting observation to make is that the number of combinations starts at 1 for the sums of 6 or 7, reaches a maximum of 8 for the combinations of 14-16, and goes back down to 1 for sums of 23 or 24.

For this reason, populating a Kakuro grid with random numbers will almost always give you multiple solutions. A random mix of high and low numbers in every row and column results in sums that fall near the middle of their possible ranges, creating the greatest ambiguity. As a constructor, you must reduce the number of possible combinations in creative ways, usually by indicating sums that are at the higher or lower end of their ranges.

A typical way to start is to use a high sum on one axis and use a low sum on the crossing axis. For example, consider a sum of 38/6 crossing a sum of 10/4. Each direction only has one combination, and only the number 3 is common to both combinations, so the cell at that intersection must be 3.

---

As promised, here is a walkthrough for designing a Kakuro puzzle. I've decided that this walkthrough should cover not only basic steps, but some moves you can use to make hard puzzles, as well as a few steps you can take to nail down puzzles that don't want to become unique. Puzzle making can be a messy process...

Let's start with an 11x11 grid, making the top and left borders all black. This results in a 10x10 area of white cells.

Then let's locate some black cells. The only rule placing these cells that must be followed absolutely is that no line of white cells can have a length greater than the range of the puzzle (1-9). Besides that, there are a few aesthetic rules that are usually followed for this step as well:

1. Black cells should have a 180 degree rotational symmetry about the point at the center of the white cells, as illustrated above.

2. 1-cell sums should be avoided.

Let's make this puzzle a little more difficult by avoiding pockets of 2-3 cell sums. Here is a challenging pattern we'll use, with slashes added to cells that will contain at least one sum.

Next it's time to start specifying some sums. There are some 9 cell sums on the grid, so we know these must be 45.

For my first intersection, I'll go with the 38/6 and 10/4 that I mentioned earlier and arbitrarily locate it in the top right.

If we wanted to make a straightforward Nikoli-style puzzle, we could complete an entire grid out of intersections like this. We could put a 27 in the sum marked "A", forcing the intersection of 10/4 and A/4 to be 4, now that 3 is already placed, and so on...

But let's make the puzzle more challenging. We'll still "go high" in the sum marked "A" with a sum of 26, limiting the intersection of 10/4 and A/4 to 2 or 4. Then, let's "go low" on the sum marked "B". 14 is as low as we can go for this sum to produce a solution.

...however this produces an unresolvable ambiguity with 1 and 2 in the red shaded cells. Let's set B to 15 instead.

Then let's bifurcate our pencilmarks a little bit around the possibilities for the intersection of 26/4 and 10/4. In the shaded cells, either all the pencilmarks on top are valid or all the pencilmarks on the bottom are valid. In both scenarios, 15/4 must contain a 1 in the red shaded cells, as must the 10/4 above it. This forms an X-Wing, eliminating 1 any other cells in the 45/9 vertical or the sum labeled "D". Let's capitalize this by setting the sum labeled "C" to 7.

The minimum values that can go into our 7/2 sum are 2 and 5, so we can definitively place them and resolve our bifurcation.

We have a considerable number of cells defined with smaller numbers. This gives us a lot of options to maintain our desired difficulty. We will have to be careful to avoid making the red shaded cell in 38/6 a 7, because it would create another ambiguity with 8 and 9. We can do something about this immediately by "going high" on the sum labeled "D" by setting it to 26.

The nice thing about this is 26/5 on its own has 11 combinations, but only 1 after we've followed the solving steps we've taken so far. Setting initially ambiguous sums like this is how we can narrow the solve path and make solvers retrace the same steps we took.

The red shaded cell in 38/6 cannot be 7 because then a naked pair of 8 and 9 would be eliminated from the two blue shaded cells in 26/5 - both would have to be 6. The red shaded cell in 26/5 cannot be 6 because it would similarly eliminate both 8 and 9 from the two blue shaded cells in 38/6.

In the blue shaded cells, 26/5 must contain one of {89}, 26/4 must contain two of {89} and 38/6 must contain one of {89}. This means that 8 and 9 can be nowhere else in the two horizontal lines in which the blue shaded cells are located. We can also conclude that the red shaded cells must have different values.

The sum labeled "E" has 3 numbers greater than or equal to 6, so it's sum is going to be pretty high. Let's "go low" as we can on this sum to make this sum initially more ambiguous. The lowest number we can set here is 27, which is still pretty high with 3 combinations, but we get a few definitive placements out of it.

Next, let's see if we can create some kind of interaction between the sums labeled "F" and "G", first setting F to a rather high sum of 13 and G to the rather low sum of 20. These values were chosen because they limit our possibilities without making the grid too ambiguous.

These values work out quite well. We find that there are 3 possibilities for 20/5, each of which is associated with one of the three possibilities for 13/2. We can rewrite our pencilmarks to indicate this trifurcation, which we're not going to resolve right away.

The trifurcation, indicated above with red shaded cells, becomes a little more interesting if we can eliminate possibilities from both sides: eliminating 4 from the 20/5 and one of the remaining possibilities from 13/2. Eliminating the 4 looks more challenging, so let's start with that.

Here's a particularly diabolical move we can use. Because we have most of the 45/9 in the second to last column resolved, we can calculate the sum of the red shaded cells in 20/5 and the blue shaded cells in the last two rows.

The sum of the blue cells = (20 + H + 45 + I) - (J + K + L + M + [the sum of the red shaded cells in 20/5] + [7 + 8 + 9])

Therefore the sum of the blue cells + the red cells = (20 + H + 45 + I) - (J + K + L + M + 24)

The maximum value we can specify for this sum is 14 + [9 + 8 + 6 + 5] + 9 = 51. Fortunately for us as constructors, we don't actually have to do all this math right away. As long as we properly understand the relationship between the cells in question, we can simply set numbers or pencilmarks to the values we want and the variables will fall into place.

(I very seldom use this move when constructing Kakuros because solving it involves a lot of arithmetic, which can make the puzzle less fun overall.)

This is a tough move to spot, and the solver is certainly rewarded for doing so, as now the puzzle is split in two. We now have to resolve the lower right corner into a single solution.

Let's set "I" to 39. Even though it has only one combination, I suspect that having 1, 2, or 3 in the bottom row will make it hard to clean up multiple solutions.

Let's set "J" to 6 and set "M" to its maximum value - 22, resolving all the cells in that line.

K and L give us good opportunities to go high since they are so constrained with two low numbers. Since these lines are interchangeable, let's arbitrarily set L first to the highest possible value, 18.

With this value set, the remaining values in the lower right corner fall into place.

The value in the blue shaded cell and it's associated sums could be any of {356}, but 6 provides the maximum ambiguity for sum "K". Even though a few numbers can be placed at the beginning, this makes them harder to spot. Besides, it's good to place a few red herrings.

Next, let's work on resolving that red shaded bifurcation by placing some clues in the upper left. Since we've already wrapped our logic all the way around the grid, we can put this bifurcation to bed with a high sum of 29 for "N".

For the sake of symmetry, let's set the sum labeled "O" to 39 and the sum labeled "P" to 38. Placing clues according to an aesthetic theme is a good way to progress when you're faced with a large number of decisions all at once.

Meanwhile, let's work on the lower left by going nearly as low as we can with Q. Because of the 9 and 5|6 already constrained, a value of 21 gives us two combinations: 12369 and 12459

A value of 27 for "R" maintains some ambiguity (2 combinations) and locks the 3|4 into place. It also creates 2 each of {89} in the blue shaded blocks. If we set S to "16" we can get 1 more 9, eliminating eliminating it as a candidate from all other cells in these columns.

One of the blue shaded cells must contain a 9. We can set T to a pretty ambiguous low value knowing this, however we're pretty constrained because any value that forces {12} into the unshaded cells of T/4 produces multiple solutions, as does any value that creates an ambiguous cycle of {789} in the red shaded cells. We need to find a way to avoid the blue shaded intersection of T/4 and 45/9 being 5. The lowest we can go to create a possible solution that avoids these pitfalls is {1369} = 19, but there is a lot of intractable ambiguity associated with this sum. We're better off going high and setting "T" to 30.

Let's set "U" to a low value that maintains some ambiguity: 14 (12 and 13 give us two intersections right at the start).

Since we're coming to the end of our puzzle, we need to tie up loose ends. Let's resolve the ambiguities we just created by going with a high value in sum "W". {6394} = 22 creates an impossibility. because it eliminates all possible values from the blue shaded cell, so let's try 21.

Luckily, since the blue cells can't be 3 and 4, this produces a single possible combination, which resolves quite a few numbers in our grid.

(Future note: assuming the intersection of 19/5 and 29/4 must be a 9 was a mistake I made, which we'll clean up later)

We're in a really good position, because we have a magic cell, shaded red, that we can work with the sums of "X" and "Y" to give us almost any value we want.

That 16/2 is a valuable place for a disambiguating low sum at this point, and that 9-elimination hasn't played a role in our solve path as I had originally planned. We are at liberty to bring it down. 10 is too low, eliminating all 6's from the bottom 45/9.

let's try 11...

...ambiguity created, shaded in blue.

12 also produces an ambiguity. One thing to notice is that the ambiguities involve the high numbers around the 27/4. Part of the reason for this is that the lower 2-cell sum is eating up our valuable mid-range 4|5, which we'll need to bring down to sum "Z".

Our earlier decision to make the ambiguous 27/4 is not helping us now. Let's tighten it up by setting it to 28, then let's withdraw our 2-cell sum until we're sure we know what to do with it.

Eureka! By setting the blue shaded cell to 6, we can take care of the ambiguous high numbers in the lower left and resolve this puzzle to a unique solution!

We just need to come up with sums for X, Y, Z, and S. Let's go high on "Y" and set it to 30, high on "X" with a value of 15 (otherwise the 47/56 becomes ambiguous), low on "S" with a value of 15. "Z" works out to be a nice initially ambiguous 23.

Let's check our puzzle for uniqueness by solving from scratch.

Looks like I made a few mistakes.

Most of our solve path is intact, except the vertical 29/4 in the upper left resolves our trifurcation right away. Oh well.

The blue shaded cells form an ambiguity with two possible combinations. We can resolve this one by lowering the 19/4 sum to 18 and the 21/4 sum to 20.

The red shaded ambiguity is a bit more challenging to address...

I first tried changing our "magic" cell, shaded red, to a 7 instead. This required changing the 15/4 sum in the upper left to a 13, and swapping the blue shaded cells. Since we lowered a vertical sum by 2, we need to lower a horizontal sum by 2. The only horizontal sum affected is 23/4 in the bottom left, which we'll change to 21.

It looks like we just made it worse, but it can be necessary to involve more rows and columns to resolve ambiguities like this.

We might have some luck if we pop that 6 in 30/4 out into the 38/6 sum and find another place for the 5, the objective being to lock the 6 in the horizontal 45/9 in the second to last row. Let's swap the blue cells, lowering the 30/4 sum to 29. We must reduce a horizontal sum by 1 as well. Let's move the 5 to the red shaded cell in the 21/4 sum and lower it's value to 20/4.

As luck would have it, that worked! Of course we will need to test it again...

Finally, we have a finished grid. Let's run it through the solver at Kakuro Online to confirm it has a unique solution. Success! It takes a satisfying several seconds to find a solution.

Here is our finished puzzle.

I hope this walkthrough has been enlightening on the different types of moves you can use when creating a Kakuro puzzle. From your tags and your work I've seen elsewhere, I get a sense that you're writing a generator. If that's the case, without getting too much into my opinion on the matter, I hope this will suggest just how difficult it can be for a generator to produce interesting puzzles.

Answer 2

The main difficulty in generating Kakuro puzzles lies in making sure the solution is unique. The big ideas I use in my generator are:

• Make choices which maximally decrease ambiguity at each step
• Pay heed to global constraints as early as possible, to avoid having to start over and/or undo work.
• Use good algorithms and heuristics to minimize (wasted) work.

Concretely, I have implemented the following process, with success:

1. Select which squares are black: start with everything white; repeatedly subdivide regions which are too large until no region is too large.
2. For each square with no clue above it or to the left: select a pair of clue values influencing that square, so as to maximally constrain the contents of that square (ideally to a single digit).
3. Repeatedly: find a clue which has not yet been given a value. Give it the value which most tightly constrains the whole board. (I pick the the clue with the largest number of possible values, where possible means "compatible with previously chosen clue values and solver deductions.")
4. If the problem doesn't yet have a unique solution, pick an arbitrary ambiguous square and paint it black. Erase the clues above and to the left of it, then re-choose clue values by step 3. If you cannot find a way of picking clue values in the now clueless squares, undo your choice of blackened square and try another.
5. (If there were no black squares in step 4). Pick an arbitrary ambiguous square. Erase the clue values above and to the left of it. Try all pairs of clue values; repeat step 5 with the clue value pair which maximally constrains the whole board, until the board has a unique solution (or you give up and restart from step 1).

By way of examples: The clue 26/3 only allows {6, 8, 9}, and the clue 21/6 only allows {1, 2, 3, 4, 5, 6}. Hence their overlap must contain the number 6. This is what I mean by "maximally constrain" in step 2. You can precompute a large table of maximally constraining clue values, by pairs of clue region sizes.

The global degree of constraint (or, reversely, ambiguity) I use in steps 3 and 5 is the product across all squares of the number of digits which could possibly go in that square. When the solution is unique, this measure has the value 1.

Note that if you sum the horizontal clues and the vertical clues you get the same sum. Never choose a clue value such that this cannot be made the case, given the set of clues still not having a value.

After each choice you make, run a solver to constrain the set of digits possible in each square, so as to properly constrain your future choices. Skip candidate clue values that lead to an unsolvable board.

Note that it is only in steps 4 and 5 you invalidate your solver's tentative conclusions; they need to rerun the solver from a blank canvas, the other steps can incrementally build on previous solver.

Be warned that step 5 can be a real time sink if you retry until you hit a unique solution. I try each ambiguous square once. If I decrease my ambiguity metric, I retry the (now maybe different) set of ambiguous squares, and keep retrying so long as I learn something. When I stop learning, I give up and retry from step 1.

In step 3, you're solving something similar to a subset sum problem: the problem of deciding a set of vertical clue values and horizontal clue values, such that the two way sum equality constraint is satisfied. For each clue, the set of values it could possibly take is often an interval: if a clue could be either 20 or 25, then it could also be 21, 22, 23 or 24. If you have two clues with intervals of possible values, say [a, b] and [c, d], then the possible sum of their values is the interval [a+c, b+d]. Use this idea to combine all intervals of possibilities first; they will typically be large enough that when you combine an interval with a non-interval, the result will again be an interval.

When implementing the solver I only re-check a clue if I've learned something about one of its squares. Also, I look at the shortest clues first, since there's less work to do there. In each size group, I do the horizontal ones first, then the vertical ones, just in case multiple horizontal clues trigger the same vertical clue twice, and I can response to two updates with a single re-check. When checking a clue with no value yet, or with the value 45, if there's at most one square with 2 possibilities, at most two squares with 2 or 3 possibilities, at most k squares with 2 or ... or k+1 possibilities, I cannot learn anything with my particular clue-checking approach of trying all combinations of digits and eliminating those digits in each square which do show up in a single valid combination. I use this fact to aggressively limit how much work is to be done.

If any of the five steps fails (steps 2 and 4 cannot fail, but step 2 can cause step 3 to fail, and you are advised to deliberately give up in step 5 after you've tried enough), I give up and restart from step 1. With the particular details of my current implementation, 10 retries is a lot. When it succeeds, it often succeeds without reaching step 5.

There's one issue I'm still only-almost-happy with, and that's step 4: it sometimes creates large bunches of black squares which I find aesthetically displeasing. I suspect that if I impose more constraints on which squares I'm willing to blacken (currently: no clue region has size 1, and every white square is contained within a 2x2 block of white squares), I will perform step 5 more often. That may be perfectly acceptable, I don't know yet—but step 5 might give up more often, if I feed it puzzles (or more accurately in-progress solver states) which are more ambiguous than at present.