Nate Dorward I

(mirrored from Nate Dorward's blog)

Killer Sudoku: tips for solvers (I)

I’ve been enjoying the exceedingly popular Sudoku puzzles that have been popping up everywhere lately, but once you get the knack of the strategies that work, filling them in is a fairly mechanical exercise, more like proofreading than logical deduction. So I was very intrigued by the advent of Samunamupure, which the Times has (unfortunately, I feel) dubbed “Killer Sudoku.” The rules and several examples of puzzles are available here. After having done a few of them I thought I’d set down some strategies I’d figured out for solving these elegant little puzzles. Despite the English version of the name, these aren’t necessarily harder than the original version; potentially they can give you a lot more information, in fact. But you have to know what to look for and what to do with it. Below I have set out some of the strategies I’ve worked out for myself (though many other solvers have independently deduced them, of course).

Terminology: I’ll use “cell” to refer to an individual square; “nonet” to refer to one of the 9 component boxes of the puzzle, and “cage” to refer to the special outlined internal boxes. My terminology was proposed originally as a makeshift, but I’ve been gratified that many solvers have picked up on it, presumably for the same reason I chose it: it eliminates the annoying ambiguity of words like “box” or “square”.

I use terms like “24-sum 3-cell cage” for clarity, but this is pretty awkward. I prefer to abbreviate this as: “24(3)”. Curly brackets are used here to mean “unordered set” (so {679} could be 6-7-9, 7-6-9, 9-7-6, &c.) Square brackets mean “ordered set” (so [679] means those numbers in exactly that order).

R, C and N = “row,” “column” and “nonet.” Nonets are numbered consecutively as follows:

123
456
789

Ruud at Sudocue has sensibly coined the term “house” for “any 9-cell unit of the nonrepeating digits 1-9,” i.e. as a catchall term for “row, column or nonet” (this could also be extended to other nonrepeating 9-cell units in killer sudoku variants like jigsaw killers and X/diagonal killers).

For more detail on killer sudoku notation conventions, see J-C Godart’s site.

A note on duplicates: For the first few months after Killer Sudoku was introduced in the Times, a debate ran among puzzle-solvers: can a cage straddling two nonets to contain a duplicate number? This would lead to enormous complications: for instance, normally a 23(3) cage must have {689} in it. But if it were an L-shaped cage positioned across a division in the puzzle, {779}, {788} and {599} would also be possible. The Times never published a puzzle containing a cage with duplicates, but their version of the rules did not explicitly disallow the possibility either. Since then, it’s become clearer that duplicates are not allowed (and the Times has redrafted its rules to clear up confusion). That said, the Times Killer Sudoku has a joker in the pack: puzzle #91 requires duplicates for a solution (there’s a 26(3) cage in it, i.e. {899}), while the 100-odd other puzzles in the book do not use them. This exception seems to have been a mistake, however. In the discussion below, I assume “normal” duplicate-free rules apply.

Don’t forget: Master all the regular sudoku techniques too! There are many sites on the web that will help you with complex techniques like X-wing, swordfish, colouring, forcing chains, &c. Most killer puzzles don’t require extensive use of these techniques, but the harder ones sometimes do. It’s as well to have them at your fingertips in addition to the methods listed below.

NB: This page is the first of two pages of solving tips. Once you’ve mastered the methods below, go here for some more sophisticated solving techniques.

Tip 1: Look for innies and outies

Let’s start with the obvious: each row, column and nonet (each “house”) must add up to 45 (the sum of the numbers 1 through 9). This will not help when the cages fit exactly into each house, but when they cut across demarcations then you can often deduce a lot. For instance look at this puzzle (from the Times article):

Note that the rightmost cages all sit exactly inside the right column of nonets EXCEPT for the cell I’ve marked, which is poking out. Now: add up all the sums inside those cages:

11 + 21 + 26 + 7 + 6 + 11 + 31 + 25 = 138

Since the column contains 3 nonets, it must add to 45 x 3 = 135. So the extra cell must have a value of 138 - 135 = 3.

You can deduce the contents of another cell now (the one I’ve marked above). See how the bottom right nonet contains only 2 cages, which add to 31 and 25? Two cells of the 31-sum cage hang outside the nonet: we’ve already figured out that one of them is a 3. We can figure out that the two extra cells must add to 11 (31 + 25 - 45 = 11). Since we know that one is 3, then the other is 11 - 3 = 8.

Sometimes you can’t figure out exactly what the number is in a cell, but at least you can narrow down possibilities and subdivide the cages (a technique known as “cage-splitting”). For instance, take a look at the bottom left nonet, which contains two cages (15(3) and 20(4)) plus there’s a 19(4) cage straddling the partition. The two cells of the 19(4) cage inside the nonet must add to 10 (45 - (15 + 20) = 10). The two cells outside the nonet must therefore add to 9 (19 - 10 = 9).

That seems like it’s not terribly useful information, but it will now help us figure out THIS cell:

We know that the cages that lie entirely within the nonet (7 + 16 + 12) add to 35. And we have just deduced that the top half of the straddling 19(4) cage must add to 9. Put these two pieces of information together and we can see that the top right cell is 45 - (35 + 9) = 1.

Using the same procedures I’ve outlined, you can figure out that the two “outies” associated with the top left nonet must add to 6; since one of them has already been revealed as a 1, the other must be a 5:

Note: The examples I’ve given above use nonets, because that procedure worked best for this puzzle, but the technique works for any “house.” On other puzzles, trying to find cells that stick in or out of rows or columns might work better (a single row or column adds to 45, two consecutive rows or columns add to 90, &c).

Tip 2: Work the pairs

The easiest cages to deal with are those containing just two cells (”doublets” or “dominoes”), and when multiple two-cell cages occupy the same house then it’s usually possible to start eliminating possibilities of paired numbers. The easiest ones are 3 (1 and 2 are the only possible pair), 4 (1 and 3), 16 (7 and 9) and 17 (8 and 9), but even when there are multiple possibilities you can usually work with them. Take a look at the top middle nonet:

The 14(2) cage must be either {59} or {68} (those are the only two possibilities that use only numbers 1 through 9 and contain no duplicates). But since we’ve already placed a 5 in the nonet we’ve eliminated one possibility; so it’s got to be {68}. The bottom nonet contains a 17(2) cage, which must be {89}; that means that the leftmost column can’t have a 8, so we now know where the 6 and 8 must go.

Now: the 13(2) cage. The possible pairings are {49}, {58}, {67}, but the latter two are eliminated because 5, 6, and 8 are already filled out in the nonet. So it’s {49}. Lastly, the 10(2) cage: the possibilities are {19}, {28}, {37}, {46}. But we’ve knocked out 4, 5, 6, 8 and 9 by now, leaving only {37}. The coup de grace: we have by now figured out where all pairs go, except for the leftover {12}. So these numbers must go in the remaining two cells.

Tip 3: Try combinations…carefully

Working out all the possible combinations for a particular cage is only helpful in the right circumstances: unless you have some constraints on the combination (e.g. if you know it can’t include particular numbers) you’ll end up with an unworkably large list of possibilities. Brute-force combination-crunching is a poor starting tactic: you should only resort to it once you’ve tried to narrow down the possible combinations with other techniques.

That said, watch out for certain combinations which are dead certs: here’s a list (brackets indicate number of cells):

 6(3): 123
 7(3): 124
23(3): 689
24(3): 789

10(4): 1234
11(4): 1235
29(4): 5789
30(4): 6789

15(5): 12345
16(5): 12346
34(5): 46789
35(5): 56789

21(6): 123456
22(6): 123457
38(6): 356789
39(6): 456789

If you need to work out the possible combinations for a cage, do it by starting with the largest possible number and work systematically downwards, exhausting the possibilities and always keeping the numbers in order of greatest to smallest. (Make sure you don’t skip any possibilities!) For instance: for 11(3) the possibilities are

821
731
641
632
542

at which point it’s impossible to go any further.

Even if you can only narrow things down to a few possibilities it can provide useful information. For instance, in the central nonet in our sample puzzle:

There are only two possibilities for the 17(5) cage: {74321} or {65321}. This tells us two useful things: (1) the cage MUST contain all of {123}; (2) it CANNOT contain {89}. A little reflection (and a glance at the placement of the 8 and 9 in the nonets above and below) will show that the only possible locations for 8 and 9 in the central nonet are as follows:

Note that I’ve filled in all the possibilities for the cells in the central nonet (I eliminated some numbers via crosschecking up and down the columns, and through keeping in mind that {123} must go in the 17(5) cage).

Coda

I’ll leave things there, although you can see that the filled-in cells already give plenty more clues: for instance, you should be able to easily locate the 8 in the middle-left nonet (nonet 4), and determine which of the numbers 4, 5, 6, and 7 goes in the bottom left cell of the 15(4) cage that straddles nonets 2 and 5. The 11(4) cage in nonet 3 is one of my “dead cert” combinations, {1235}. And so forth.

Once you’ve mastered the basics…

I hope this list of tips helps puzzlers hooked on Samunamupure/Killer Sudoku. Any corrections, comments or additions can be sent to me at ndorward at ndorward period com, or simply posted to this site via the comments on this thread.

There are countless other techniques to use in solving puzzles; the above rules will let you solve more or less everything that appears in The Times, but they may not be enough for harder puzzles. For more practice, try DJape’s Perfect Sudoku site or the Sudocue site. And if you feel like a real challenge try some of my own creations, which are mostly very hard indeed. To solve them you will need to master some of the strategies on my list of advanced solving techniques…