Killer Sudoku Online Weekly No. 371 - Mind Bending and Then Some Walkthrough by metzomagic.com

Killer Sudoku Online Weekly No. 371 - Mind Bending and Then Some

Walkthrough by Steve Metzler (2013)

Last updated: 11th May, 2013

Introduction
My hobby and, nominally my forte, is helping gamers to get through challenging computer role-playing and adventure games. This exercise is a bit of a departure from those genres, into the realm of pure mathematical puzzling. Most of you are undoubtedly familiar with sudoku puzzles, whereby you need to fill in a 9 x 9 grid with numbers such that each row, column, and each of the nine 3 x 3 sub-grids (nonets) contain the numbers 1 through 9, with no repeats. But unbeknownst to many, there are further levels of sudoku puzzling that go way beyond that. Namely, there is 'killer sudoku'. Gaze in awe at the beast:

Figure 1: Killer Sudoku Online Weekly No. 371 - Mind Bending

The first thing you will notice is that, unlike with classical sudoku puzzles, the starting board is bereft of any numbers, save for the ones telling you how much the numbers in each cage must add up to. A cage is delineated by dotted lines and, since the world is not a fair place, cages can cross over those things we call nonets (the nine 3 x 3 sub-grids that I referred to earlier). This little twist can make it particularly difficult to solve a puzzle, though it can also serve as an essential aid, once you know how to take advantage of it. But I digress already. The rules of killer sudoku are the same as in normal sudoku: you need to fill in the 9 x 9 grid with numbers such that each row, column, and each of the nine nonets contain the numbers 1 through 9, with no repeats. So once you get a few definite cell values established, you can use normal sudoku techniques to help you complete the puzzle. There is one additional rule though, and it is a necessary one to make these solvable: a number cannot be repeated in a cage, even if the cage spans multiple rows, columns, or nonets. We need to define a few notational conventions before we go any further. 'r' is an established abbreviation for row, and 'c' for column. Also, the nonets are referred to, left to right and top to bottom as: A through I. So: r5c2 is in nonet D, as highlighted below:

Fig. 2: baby steps

I took the liberty of filling in some possibilities for a few of the cells there in nonet H. The rationale is explained below. Now before we dive into the solution proper, a few disclamers:

This is about as difficult as this type of puzzle gets. That's why I've taken the trouble to document it, in order to demonstrate some of the more advanced techniques you need to employ in order to solve the Hard, Extreme, Outrageous, and Mind Bending puzzles. If you are just starting out with these puzzles, pay a visit to Killer Sudoku Online and read the Tips page. Then try some of the Easy ones in the archive (there's a separate archive for each year going back to 2006). Though if you've already progressed to Hard or above, stick around. You might learn some useful tricks here.
There may well be a quicker way to solve Weekly No. 371 than I have described below. If there is, I don't want to hear about it :-) Seriously. Enough sleep is lost over these things as it is. Invariably, we all crack these puzzles in slightly different ways. The aim here is show you a couple of good tricks from the experienced puzzle-solver's arsenal, and how to apply them.

And now, without further ado:

Weekly No. 371 - One possible solution technique
The only real 'gimme' in this puzzle is r9c4-5 being {12}, as that is the only way to obtain the cage total of 3. Also, the largest number that can be in a 9 x 3 cage is 6, and 1 and 2 are already present in this nonet, thus the {3456} in r7c4. Now it's time to break out the calculator, at least the mental one. Again, considering nonet H, the cages in it add up to: 18 + 13 + 3 = 34. That leaves 11 over to make 45, so the companions to {3456} must be {5678}:

Fig. 3: the hidden 11 x 2 cage in nonet H

By a similar calculation in nonet G (45 - (18 + 15)), we infer that r7c1 - c3 must add up to 12. Since the remaining two cells of the 9 x 3 cage that are in nonet G can only add up to 3, 4, 5, or 6, then that narrows down r7c1 to {6789}. We can further split r7 by noting that three cells from r8 and r9 overflow into it. The sum of the cages that touch r8 and r9 is: 13 + 18 + 31 + 18 + 15 + 14 + 3 = 112. Since the total of the cells in two rows must be 90, that leaves 22 overflowing into r7. And 22 x 3 is a pretty handy one, because it must contain a 9:

22 x 3
------
589
679

That means we can eliminate the 9 as a possibility for r7c1, which also eliminates the 6 in r7c4, and thereby the 5 that was paired with it in r9c6 it to make 11, so we now have:

Fig. 4: nonets G and H narrowed down

Killer Sudoku Online veterans will have noted that there is usually a symmetry to these puzzles, and this one is no exception. So let's turn our attention to the top of the board now, and work some similar magic on nonets B and C. The remainder of (45 - (21 + 18)) in nonet C is 6, so r3c7 - c9 can only be {123}. That overlaps with the 9 x 3 cage there, so r3c6 can only be {456}. And since there's a hidden 9 x 2 cage in nonet B (45 - (11 + 13 +12)), then r1c4 must be {345}. So that all looks like this:

Fig. 5: the low hanging fruit in nonets B and C

It was at this stage of solving the puzzle that I originally went off on a tangent and narrowed down the possibilities in nonets B and H :-\ But hindsight is 20/20, as they say, and the key to this whole puzzle turns out to be the interaction of the 21 x 3 cage in r4 with the 35 x 7 cage in the middle of the puzzle. Before we can make any headway there though, we need to chip away a bit at the edges of nonet D. Specifically, the scope of what can be in cells r4c3 and r6c3 needs to be reduced. So we run 31 x 5 through the Sum Calculator and find that:

Aha. The bit that overlaps with nonet D must have a 9 in it, so the {r4c3 r6c3} cage cannot have a 9 in it. What follows next is a neat trick I learned from fellow traveller Wo Mowoco that makes things a lot simpler than the way I had originally done it. If we add up all the cages that are completely contained within columns 1 to 3, we get: 135 - (19 + 24 + 31 + 18 + 15) = 28 left over. That's how much of the first three columns is 'in'. Note that the only cages that have cells both 'in' and 'out' of the first three colmuns are the 16 x 3 and 9 x 3 cages, which total 25. Since 28 - 25 = 3, that means: the two 'innies' r4c3 and r6c3 must be 3 more that the two 'outies', r1c4 and r7c4. Since we already know that r1c4 + r7c4 = 7, 8, or 9, that means that the {r4c3 r6c3} cage is restricted to the range 10 - 12. This turns out to be a very important restriction. Now let's figure out what possible values can be in the 35 x 7 and 21 x 3 cages:

21 x 3
------
489
579
678

Well, it's almost a direct hit. Because r3c4 cannot be a 9, that means that the 9 from either {489} or {579} in the 21 x 3 cage must be located inside nonet E (and also be on r4, which means the overflow cell from the 35 x 7 cage in r4c7 also cannot be a 9). Since r6c3 cannot be a 9, if the 21 x 3 cage is either {489} or {579}, then the 35 x 7 cage would have to be {2345678}. But that means we have to prove that the 21 x 3 cage cannot be {678}, or else that brings the 35 x 7 cage combos that include 9 back into consideration. If you haven't resorted to taking pen to paper yet, now is the time :-) We'll try to fit each possible 21 x 3 cage {678} combination with each 35 x 7 cage combination that contains a 9, and see if we can rule them all out. First we put a 6 in r4c3, and of course 7 and 8 go inside nonet E. That immediately rules out (1235789) because we can't keep both the 7 and the 8 out of nonet E to avoid conflict (and remember, r4c7 is part of the 35 x 7 cage, but it's on the same row as the 21 x 3 cage, so is completely ruled out). But that still leaves {1245689} and {1345679}. We can't put a 7 or an 8 in r6c3 because the max that hidden cage may contain is 12, from our earlier range calculations. In fact, no matter how we try to fit {678} into the 21 x 3 cage, the value of the {r4c3 r6c3} cage will always be > 12, which is prohibited!

So that rules out the possibility of the 21 x 3 cage being {678}, and it also tells us that the 35 x 7 cage can only be {2345678}. We can deduce a few other things from that. Have a look at the ways the 21 x 3 cage can be filled in now that we've excluded {678}:

21 x 3
------
r4c3
4   |89
5   |79
7   |59
8   |49

Since {2345678} contains all of {4578}, these numbers cannot be in nonet E, so they must reside in r6c3. In fact, that tells us that the {r4c3 r6c3} cage must be one of {48} or {57}, and that its value is 12 (according to our earlier innies and outies calculation it has to be in the range 10 - 12, and {47} is ruled out because there is then no way to fit {2345678}). Now we can calculate that the overflow from nonet E is: 21 + 35 + 9 - 45 = 20. So that means the hidden {r4c7 r6c7} cage in nonet F must total 20 - 12 = 8. We now have:

Fig. 6: beginning to take shape

You're probably wondering how we were abe to determine that r9c4 is a 1. Have a good look at c4. The only other place a 1 or 2 could exist in it is inside nonet E. And since we just proved that the 35 x 7 cage does not contain a 1, then it must be a 2. That also rules out r6c7 from being a 6, as there would need to be a 2 in the remainder of the 9 x 3 cage in nonet E. And since the only place a 1 can reside in nonet E is in the 9 x 3 cage, r6c7 cannot be a 1. Also, now that we know the {r4c3 r6c3} cage must total 12, that means that neither r1c4 or r7c4 can be a 3, and that r7c1 cannot be a 6. That last bit has a ripple effect all through the top of the puzzle. We can narrow down the 13 x 2 cage in nonet B, because {49} and {58} are ruled out. And that's how we wound up with what you see in Fig. 6.

That is huge progress in a puzzle that is this difficult, but there's still a ways to go. OK then... the 1 in nonet B has to be in the 12 x 3 cage in r2. And the only possible ways to make 12 that way that are left are {129} and {138}. That also determines what the possiblities are in the 11 x 2 cage. Then we can also fill in the rest of the possibilities for c4, and for the remainder of the 9 x 3 cage on r7. And hey, remember that hidden 22 x 3 cage on r7? It has to be one of {589} or {679}. The fact that there is a handy 13 x 2 cage in nonet H means that you can't put {58} or {67} in nonet H on r7. And that means that one of those cells must be the 9, which eliminates 9 being a possibility for r8c4. And thus, the 9 in the 21 x 3 cage must be in r4c4. Based on that, we can also put some possibilities in the 13 x 2 cage in nonet H. See Fig. 7 below.

Fig. 7: r4 is becoming manageable

Now if you look closely at c6, you will note that the only place a 9 can go is in r7c6. And that observation alone has a cascading effect that reduces the puzzle down to an easily solvable one:

Fig. 8: broken

I trust you can get down from there :-)