Killer Sudoku – September 27th

Many people have asked about the Killer Sudoku posted on September 27th. I haven’t tried to solve this Killer by hand but it is very much possible that it requires either a lot of math (the technique that I call “cage/fence splitting”, which will be explained in the next few days) or that it cannot be solved by “logic” alone, that it needs trial and error. What is certain is that it does have only one solution. Why did I post such a puzzle? Because as you might know, the first puzzle was published on September 26. At that time, the algorithm used for producing Killer Sudokus relied heavily on “backtracking”, or trial and error in plain words. So, one of these days I will try to solve it by “logic” (I think this term is improperly used in this context) and if I succeed I will post a step-by-step solution. If not, maybe someone will and we will be very thankful if they post their solution :).
Related Posts Plugin for WordPress, Blogger...
This entry was posted in General, Killer Sudoku, Solving tips and tagged , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

12 Comments

  1. ZD
    Posted October 7, 2005 at 5:00 am | Permalink

    Here’s as “far” as I got — I tried it a couple of times, but I can’t guarantee I got as far here as I did the first time…

    (In the following — T = Top, B = Bottom, L = Left, R = Right, C = Center)

    1’s in the TL and BR nonet are given.

    2 is in the BL of the CC nonet (using the rule of 45 on the LC nonet) — this gives us the corresponding 9 (11-2)

    4 is in the TR of the CC nonet (using the rule of 45 on the RC nonet) — this gives us the corresponding 9 (13-4)

    8 is in the UL square of the CC nonet, and 9 is in the CL square of the CC nonet. This is because a 2-cage summing to 17 is 98, and there already is a 9 in the 4th row.

    In the CC nonet, the 6-cage is 5+1 (only combination of numbers left in the nonet that sum to six). Based on the following reason, we know 5 is in the CR square and 1 is in the BR square:

    In the 4th row of the puzzle, we know the leftmost three squares are 123 (3-cage summing to 6). We also know the 8, 4, and 9 in that row. That leaves us with a 5, 6, and 7. Consider the last two squares in the 4th row; they total *at least* 11, meaning the last three squares in the 5th row total *at most* 7 (since the whole 5-cage totals 18). Three squares in one row totaling *at most* 7 must include both a 1 and a 2. Therefore, since we know there is a 1 in the 5th row in the CR nonet, we know there isn’t a 1 in the 5th row in the CC nonet. Hence, the cage summing to 6 in the CC nonet reads 51 from T to B.

    I think through a little trial-and-error, I was able to get the remaining three squares in the CC nonet to read 673 from T to B. We’re now also able to determine which row every number is in (for the CL and CR nonet).

    Someone who can explain it further — take over! 🙂

  2. udosuk
    Posted October 7, 2005 at 7:39 pm | Permalink

    You can work out R5C6=5 and R6C6=1 in a more obvious way… since R6C[7-9]=18, if 1 is in that cage then 9 must be too (18=1+8+9), but this is not possible because R6C3=9 already. And R6C1 & R6C2 cannot be 1 because the 1 in that box must be in row 4 (R4C[1-3]=6). All in all the 1 in row 6 must be in R6C6 only.

    To proceed from there, we need to use the following implied lines/cages:

    R[8-9]C9=7
    R[4-7]C9=20
    R[8-9]C3=9
    R[3-6]C1=16
    R[1-2]C7=7
    R3C[6-9]=17
    R7C[1-4]=16

    For example, since R[8-9]C9=7, the only pairs we need to consider are 2,5 & 3,4. So when working on R[4-7]C9=20 we must bare in mind that we must not use 2,3 or 2,4 or 3,5 or 4,5 together. That alone eliminates quite a few possibilities.

    I’ve only solved the puzzle by hand using trial and error. But still a lot of techniques need to be applied to get through it efficiently. So that’s it for now… more upon request…

  3. domt
    Posted October 8, 2005 at 1:25 pm | Permalink

    r[8-9]c9can be whittled down to two using the following logic. (bear with me)

    1. br square cages equal 18 leaving the others to sum 27.
    2. this can only be 9873 or 9864.
    3. r[8-9]c8 can only be 73 or 64 therefore (9and 8 must be in the other squares)
    4. this leaves the ‘7’ cage to be 5 and 2.

    Following this: (and assuming r[4,5,6]c5 is 673 top to bottom then this leaves r4,c9 as 7.

    we know now that r[5,6,7]c9 now must equal 13. so whichever combination you use with the options the 9 cannot be in r7,c9 – leaving it in r7,c8 definitely.

    Anyone care to continue?

    Dom

  4. ZD
    Posted October 8, 2005 at 10:06 pm | Permalink

    Not so fast, my friend…

    27/4 can also be 9765. So all we know is that 9 is in R7C[7-8].

    I’ve made (VERY little) progress in C1. Specifically, we know R3C1 is a 123, and we know the 16 in R[7-9] has a 123 (plus two larger numbers).

    In 2nd nonet news…we know that a 1 cannot be in R3C5. This uses the fact that R[1-3]C4 + R3C5 = 22, and the most you can get in R[1-3]C4 is 18. So we’re *almost* onto something there…

    Still, this is a real bear. Let’s keep the logic talk up here and see if we get anywhere.

  5. udosuk
    Posted October 9, 2005 at 6:33 pm | Permalink

    Good moves from ZD!

    To go a bit further, R3C1 can only be [23], because the 1 in that nonet is in R2C3. Of course you’ve eliminated 4 to 9 there with subtle consideration using the TL 13-cage.

    And R3C5 cannot be 1 or 2, leaving [4589] the only possible candidates left following ZD’s exact arguments.

    Now in that same nonet, we could conclude R1C5=[1245] and R1C6=[2678] working with the 11-cage.

    Another observation is one and only one from [789] could be in the 19-cage there. Although I couldn’t do much with this fact.

    The next step I went is putting 9 in R7C8 with very subtle reasoning that some might consider as T&E:

    1. Before that, the 9 in nonet-9 could only be in R7C[8-9] quite obviously.

    2. Since R[4-7]C9=20, if R7C9=9, then R[4-6]C9=11, leaving these 4 possibilities:
    5-2-4, 6-2-3, 6-1-4, 7-1-3
    The first 2 cases destroy the BR 7-cage and the last 2 cases violate the fact that the 5-cell 18-cage could only be [56]+[124] or [57]+[123].

    3. This leave R7C8 as the only possibility for 9 in nonet-9, making R7C7+R7C9+R9C7=18, further eliminating the 2’s in these cells.

    So the partially formed grid is like:
    …|…|…
    ..1|…|…
    …|…|…
    —+—+—
    …|8.4|9..
    …|9.5|…
    ..9|2.1|…
    —+—+—
    …|…|.9.
    …|…|1..
    …|…|…

    I’ve made a colourful presentation showing all candidates using Excel, but I don’t know how to post images in here. Maybe djape could help me out on how to upload stuffs here?

  6. Posted October 9, 2005 at 7:03 pm | Permalink

    udosuk, send the file you’d like posted to sudoku@djape.net and I’ll make sure it becomes available to everybody. Cheers mate!

  7. fred
    Posted October 11, 2005 at 2:59 pm | Permalink

    R4C[8-9] has to be [567] (1-4,8 and 9 already used in R4).
    This gives only 1+2+3+5+7 and 1+2+4+5+6 for the 18 (cannot be 1+2+3+4+8 !).

    Therefore no 8’s are possible in R5C[7-9]
    Consequently there has to be an 8 somewhere in R5C[1-3]
    Consequently there are no 8’s in R6C[1-2]

    If R4C[8-9] is two out of [567], the only possibilities for R5C[7-9] are 1,2,3,4 because they are the rest of the 18 (1+2+3+5+7 and 1+2+4+5+6 without 5+7 or 5+6).
    Hence we can remove all 6’s and 7’s from R5C[7-9]

  8. fred
    Posted October 12, 2005 at 1:33 pm | Permalink

    I can nail down the 1 in the TC nonet on R1C4!

    R1C5 cannot be 8. If it were 8, the rest of the 11 in R1C[5-7] would have to be 1+2, but there is already a 1 both in C6 (R6) and C7 (R8).

    As ZD already wrote R3C5 has to be [4589].
    So the 1 can only be in R1C4 or R1C5 or R3C4

    Some ‘small’ Trial and Error leading to contradictions for all other cases:

    Do not try that on your original work paper, because afterwards you have to undo all the assumptions that are proven wrong!

    Note that the L shape in R[1-3]C4+R3C5=22

    First part, let us assume R3C4 = 1

    R3C1 can only be 2 or 3 (see ZD and udosuk, by eliminating 4-9 against the 13 grid)
    There is only one 28 for 5 cells with a 1 and a [23], namely 1+3+7+8+9.
    This puts the 3 in R3C1 and 8 or 9 in R3C5.
    1.) if R3C5=8, then R[2-3]C4=13 (remainder of the L shape), requiring a 1 in R1C3 for the 14, but there is already a 1 in R2C3.
    2.) if R3C5=9, then R[2-3]C4=12 (remainder of the L shape), requiring a 2 in R1C3.
    If we now look at the 11 grid in R1C[5-7], there are no 1’s and 2’s any more, but all three cell sums for 11 contain a 1 or 2.

    Second part, let us assume R1C5 = 1

    For the 11 grid R1C[5-7] this means that the remaining fields have to be 6+4 or 7+3 or 8+2

    This leaves for R[1-3]C4+R3C5 the possibilities
    3469
    3478
    3568
    4567
    (all other 4 number sums of 22 contain a 1 or at least two out of [289], but these cannot be placed due to the [289] in R[4-6]C4)

    1.) 3469
    This gives either
    a.) for R1C6=7 and R1C7=3 and R2C7=4
    The remaining fields for the 19 in the TC nonet are 2+5+8 with the 5 in R2C5 and [28] in R[2-3]C6.
    This gives [369] for the remaining fields in R[7-9]C6.
    It has to be 3 in R7C6 and [69] in R[8-9]C6, requiring another 6 in the same grid to make 21.
    or
    b.) for R1C6=8 and R1C7=2 and R2C7=5 without any possible place for a 5 in the CC nonet.

    2.) 3478
    This leaves for R1C6=6 and R1C7=4 and R2C7=3
    The remaining fields for the 19 in the TC nonet are 2+5+9 with the 5 in R2C5 and [29] in R[2-3]C6.
    This gives [378] for the remaining fields in R[7-9]C6.
    It has to be 3 in R7C6 and [78] in R[8-9]C6, requiring 6 in R9C7 to make 21.
    The reverse L shape in R[7-9]C6+R7C5 has to be 68-45=23, this requires a 5 in R8C5, but there is already one in R2C5.

    3.) 3568
    This leaves for R1C6=7 and R1C7=3 and R2C7=4
    The remaining fields for the 19 in the TC nonet are 2+4+9, but without any possible place for the 4 in the TC nonet.

    3.) 3568
    This leaves for R1C6=7 and R1C7=3 and R2C7=4
    The remaining fields for the 19 in the TC nonet are 2+4+9, but without any possible place for the 4 in the TC nonet.

    4.) 4567
    This leaves for R1C6=8 and R1C7=2 and R2C7=5
    The remaining fields for the 19 in the TC nonet are 2+3+9
    This gives [23679] for the remaining fields in R[7-9]C6.

    a.) R[8-9]C6=[69]
    This requires another 6 in the same grid to make 21.

    b.) R[8-9]C6=[79]
    R9C7=5 to make the 21 collides with the 5 in R2C7.

    c.) R[8-9]C6=[67]
    R7C[5-6]=10 (rest of the reverse L), with the only possibility of 8+2.
    The remainder of the 29 grid (R7C7+R7C9) has to be 10 with [3467], the same for the 10 in R[8-9]C8 leaving [25] for R[8-9]C9.
    The 5 cannot be in R4C9, so it has to be in R4C8
    The 2 has to be in R5C8
    The 1 has to be in R5C9
    Going up to the 18 in R[1-3]C9 the only remaining possibility is 3+6+9.
    Hence R4C9=7 and R5C7=3
    R6C9=8 (only space for 8 in C9)
    R6C8 is either 4 or 6, that takes the [46] from R[8-9]C8 leaving [37] there.
    If we now look at the 7 in the BC nonet:
    We have 7’s in R8 and R9 (columns 6 and 8), so the 7 would have to go in field R7C4, but that removes the last possibilities for a 7 in the TC nonet.

    Some consequences:
    The 1 in the UR nonet has to be in R3C8 or R3C9.
    The 1 in the BC nonet has to be in R7C5 or R9C5.
    And it leaves [236] in R1C6 (no possibilities for 11 with a 7 or 8 without a 1)
    R1C3 has to be [678] and R2C4 has to be [567] (only remaining combinations for 14 with a 1)
    Taking the L shape in R[1-3]C4+R3C5=22 with a 1 in R1C4 we can reduce further:
    R[2-3]C3=[567], R3C5=[89] (no other possibilities for 4 sum 22 with a 1)

    Next steps: It should be possible to use similar logic to eliminate the 1 from R3C8 fixing the 1 in R3C9 (with R[12]C9 being [89] and a 1 in R5C8)

  9. Ronny
    Posted October 12, 2005 at 5:17 pm | Permalink

    fine analysis Fred!

    I follow you up to 4.c where u write ‘in R[1-3]C9 the only remaining possibility is 3+6+9’
    I suppose the 8 is no longer a possiblity there,
    but i seem to have missed the reason..

  10. Ronny
    Posted October 12, 2005 at 5:33 pm | Permalink

    sorry, i was too fast,the 9 has to be in R[1-3]..

  11. udosuk
    Posted October 12, 2005 at 7:00 pm | Permalink

    fred’s analysis is sound, but personally I think it’s too much to be called “small” T&E…

    I’m trying my best to use simple steps to make progress, and albeit some of them could still considered to be T&E, I regard them as minor ones when they just look 1 step ahead, unlike fred’s which branches too much…

    So I wouldn’t use fred’s result for now and will continue from the pic I posted to djape earlier:

    Using the “fence splitting” technique on column 6, we have

    R[1,2,7]C5=11
    R[3,8,9]C5=18

    So, R2C5={2458} (9 excluded), R8C5={4589} and R9C5={14589} (2 excluded).
    The 2 of row 7 is locked in nonet-8, so R7C[1-3] cannot be 2.

    Also, because R7C[7,9]+R9C7=18, and R9C7={45678}, R7C[7,9] ranges from 10 to 14 and this makes R7C[5,6] ranges from 6 to 10.
    So, R7C6 cannot be 3, because that will force R7C5=2 and R7C[5,6] will be 5, too small.

    Now the 3 on column 6 is locked in R[2,3]C6, within the 19-cage!
    We can immediately exclude 3 from R2C7 (same cage).
    Next, if R2C7=4, we must have R2C5 and one of R[2,3]C6 summed to 12, which force R2C5=5 and the R[2,3]C6={37}.
    Now R2C4 must be 6 (naked single) and R1C6={28} (6,7 excluded), then with R1C7=3 (7-cage) the 11-cage is impossible to make!

    This is an important result: R2C7={25}, which force R1C7={25} and we have a naked pair which will give us huge progress!

    I’ll send the update image to djape soon…

  12. fred
    Posted October 13, 2005 at 7:41 am | Permalink

    Error correction

    My very last argument
    “We have 7’s in R8 and R9 (columns 6 and 8 ), so the 7 would have to go in field R7C4, but that removes the last possibilities for a 7 in the TC nonet” is wrong, there is already a 7 in the TC nonet!

    We have to continue different from here!
    Reduce R6C7 and R6C9 and R7C7 and R7C9 to [46]
    This forces a 7 into R3C7 giving [148] for the rest of the 20 in the TR nonet.
    1 has to be R3, 8 has to be R2, 4 has to be R1.
    Now look at the 28 in R3C[1-5]
    R3C1 is [23], R3C5 is [45]
    The 28 in R3 has to contain a 8, a [23], and a [45], but must not contain a 1 and not a 7.
    The only possibility satisfying these restrictions is 2+4+5+8+9
    9 goes into R3C2, 8 into R3C3 leaving [45] for R3C4.
    [45] in R3C4 and R3C5 gives [67] for R[1-2]C4, but that requires another 1 in R1C3 to make 14.

    I hope there are no other errors in my chain of arguments.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  • Meta

eXTReMe Tracker
%d bloggers like this: