Nate Dorward II

(mirrored from Nate Dorward's blog)

Killer Sudoku: tips for solvers (II)

Since I wrote the initial “Tips” page, I’ve discovered some other techniques, or refinements of existing techniques; and other solvers have also done the same. So time to list some more techniques….

1: A plus-minus variant of the 45 rule

The 45 rule can sometimes be used in cases where you have both innies and outies. I don’t recommend using this as a first tactic, but if you’re stuck then this can be helpful, and some puzzle-designers like to make puzzles where this is the key to getting started on a puzzle. (An example is puzzle #89 in the Times Killer Sudoku book.). Here’s an example, in a puzzle I devised myself:

The initial moves on this one are obvious enough, as the 24(3) and 23(3) cages in the middle of the puzzle are respectively {789} and {689}, leading to this configuration:

I have marked the two outies with red outlines, the single innie with blue. The sum of the two outies - innie =

(15 + 24+ 15 + 6) - 45 = 60 - 45 = 15

The two outies are on the same row, so they can’t be the same number. This leaves only two ways to get a sum of 15:

17 - 2 = 15. Outies: 8 and 9 (sum: 17); innie: 2.

16 - 1 = 15. Outies: 7 and 9 (sum: 16); innie: 1.

Solution #1 is impossible, clearly, because the middle right nonet contains an {89} doublet already. So the right outie must be a 7 and the left outie must a be 9; the innie must be a 1. The result:

(I have filled in the 24(3) cage also, since the placement of the 8 and 9 is now obvious.)

The plus-minus technique is probably more than you need for puzzles of simple-to-moderate difficulty; but with the trickiest puzzles it is an essential tool. 2: Extensions of “normal” sudoku solving techniques: “complex elimination”

You should of course never forget to use regular sudoku solving techniques. Some of them are more useful than others; I’ve found that “X-wing” techniques (see here for an explanation) are often handy because killer sudoku puzzles tend to be littered with “dominoes” (two cells which each can only contain two values, but you don’t know which goes where). If two dominoes are stacked up parallel to each other, then X-wing can come into play.

Even if you haven’t got a domino — i.e. there is more than one pair of values that can go in a two-cell cage — the fact that the cells are bound together means that for the purposes of regular sudoku solving techniques you can sometimes treat them like a single cell. Let’s call this “complex elimination”: you combine the usual sudoku elimination techniques with information provided by the killer rules. Here’s an example of complex elimination, from the early stages of solving my puzzle #4:

In regular sudoku, if you had three cells that had the possibilities {12}, {1245}, {1245}, this wouldn’t tell you anything: it’s one cell short of a so-called “naked quad” (four cells with only four possible values, which would exclude those four values for the rest of the row, column or whatever). But here, the lower two cells which I’ve marked with a blue outline must add to 6 (21 - 6 - 9), which means it contains {15} or {24}. In other words, either 1 or 2 is somewhere in those two cells. So we’ve essentially got the same situation as in normal sudoku when we have a pair of {12} cells in the same column: we can remove all other instances of {12} elsewhere in the column. In this case this move permits us to ascertain the value of r4c6, as the only remaining value is 3:

3: Range restriction

This is a technique of last resort: it’s time-consuming and doesn’t always yield results. But some puzzles only respond to this approach. The idea is simple: if you have two areas of the puzzle (usually “new” cages you’ve created via cage-splitting) that add to a fixed sum, then you can narrow down minimum and maximum values for the two areas — which in turn may in turn permit you to similarly winnow down the minimum and maximum values for other cages and cells elsewhere, until eventually you (hopefully) can squeeze the range down to one or two values. The first puzzle I’ve designed that requires this technique is #7 (available here). An initial application of the 45 rule determines that there’s an intersection of a hidden 8(3) cage on column 4 and a hidden 28(4) cage on row 6, so that r6c4 = {45}. You can then apply the range-squeeze technique as follows (I have cleared away irrelevant cages for clarity’s sake):

I have labelled the new cages with letters. Keep in mind that on row 6, the 28(4) hidden cage must be either {9874} or {9865} (the only possibilities), and that the rest of the row must add to 45 - 28 = 17. So, here’s the min-max squeeze:

cage A: max value is 16 = {79} (can’t be 17, as {89} would conflict with both {9874} and {9865}).
cage B: min value is therefore 23 - 16 = 7
cage C: max value is 17 - 7 = 10
cage D: min value is 26 - 10 = 16

The minimum value for cage D is, as it happens, only just below the maximum possible value for a two-cell cage (17 = {89}). In other words, cage D = either 16 or 17, i.e. either {79} or {89}. Now that we’ve determined this, cages A, B, and C must similarly have only two possible values! So now we get (working our min/max in reverse):

cage D: 16..17
cage C: 9..10
cage B: 7..8
cage A: 15..16

(NB: I use two dots rather than a hyphen to indicate “range” to avoid confusion with “minus sign”).

The only possibilities for cage A are thus {69}, {78} or {79}. So our squeeze has uncovered a “naked quad” (”four of a kind”): we know the exact four cells where the numbers {6789} must go in nonet 6:

Things worked out nicely here, because I designed the puzzle to be solved this way. With other puzzles, this technique may or may not be helpful… handle with care!

4: Subtraction combo

The name is the coinage of the solver Udosuk. It’s an efficient way to deal with subsets and combinations without having to resort to listing all the combinatoric possibilities and mechanically working through them. Basically: once you have reduced the candidates for a given row/nonet/column to a limited set, you can figure out the sum of the numbers that lie outside a particular cage by summing up all candidates & subtracting the sum of the cage.

A simple example: say you have a 16(3) cage, and have determined that it can only contain the numbers {3567}. Instead of trying to figure out which three of those four numbers add to 16, it’s much faster to use subtraction combo:

3+5+6+7 = 21
21 - 16 = 5

So the 5 must be left out, and the 16(3) cage = {367}.

A more complex example: a 14(3) cage in a nonet with five numbers/cells that are unclaimed: {24567}. Subtraction combo:

2+4+5+6+7 = 24
24 - 14 = 10

The two cells outside the 14(3) cage add to 10. In {24567} the only pair that adds to 10 is {46}. So the 14(3) cage = {257}; the other two cells are {46}. 5: Overlap

This idea was first advanced by Jean-Christophe Godart, and rather than describe it here I’ll simply point you to his website. It’s a variation of the 45 technique which can get results much more elegantly, though it only works if the puzzle has some very special properties. I will post more on this if I design a puzzle making use of this technique (I’m currently at work on one…!). Pencil and paper tips

I always solve these puzzles on paper because there is no computer program that permits you to make the more complex pencilmarkings that you need to solve the harder puzzles (innie/outie sums & differences, min-max values, split cages, &c). With simple cage-splits it’s easy to just draw in extra lines and extra cage-sums, but this doesn’t work if the splits start to get complex. My advice for dealing with the more complex puzzles that can be a mess to mark up: when you create new cages via cage-splits, mark each cell of the new cage with a letter (A, B, C, D…). Then you can make a list elsewhere on the page of the values and cell-counts of each lettered cage. (The cell-counts are important because splits can create cages whose cells are not contiguous, and you need to keep track of how large they are!) So as you solve you make a list:

A(2) = 15
B(3) = 10
C(2) = D + 6
etc.

This saves you from madly drawing circles, arrows and numbers on the grid itself, which gets terribly confusing.