8
$\begingroup$

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 am getting multiple solutions. Can somebody tell me how to generate kakuro puzzles that will have unique solution.

$\endgroup$
26
+50
$\begingroup$

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.

Grid

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.

Pattern

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.

First Intersection

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.

Ambiguity

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

B to 15

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.

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.

Resolved 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.

D 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.

EFG

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.

Trifurcation

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.)

Diabolical Move

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.

M

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.

L to 18

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

NOPQ

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.

RS

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).

TUV

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.

W

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 2

...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

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.

Apparently finished

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

Uniqueness

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...

Red Ambiguity

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.

Red Ambiguity 2

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.

Finally Done

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.

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.

$\endgroup$
  • 3
    $\begingroup$ Great answer! I hope this bounty gives you a head start in earning the privileges you need to contribute more to this community. (But I'll be expecting high quality posts from you from now on... :D) $\endgroup$ – boboquack Mar 14 '17 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.