Super Tough Sudoku from Crazy Dad...would love just a nudge

Advanced methods and approaches for solving Sudoku puzzles

Super Tough Sudoku from Crazy Dad...would love just a nudge

Postby bathmatters » Wed Nov 16, 2005 7:34 pm

I would love a gentle hint. Have I missed something relatively basic, like a hidden triplet?

If I need to start using more advanced techniques, which one should I start with?

Started here:

7..2....9
....7.2.6
..83.....
3...9.5..
.4.....3.
..1.6...7
.....57..
4.3.1....
5....8..4


Have gotten here through basic techniques.
7{156} {456} 2 {458} {146} 3 {458} 9
{19} 3 {459} {14589}7 {149} 2 {458} 6
{269} {269} 8 3 {45} {69} {14} 7 {15}

3 {2678} {267} {1478} 9 {1247} 5 {1246} {128}
{2689} 4 {25679} {1578} {258} {127} {1689} 3 {128}
{289} {2589} 1 {458} 6 3 {489} {249} 7

{12689} {12689} {269} {469} {24} 5 7 {1269} 3
4 {2679} 3 {679} 1 {279} {689} {2569} {258}
5 {12679} {2679} {679} 3 8 {169} {1269} 4
bathmatters
 
Posts: 4
Joined: 14 November 2005

Postby CathyW » Wed Nov 16, 2005 8:33 pm

I think this is a tough one. Managed some more eliminations but then I got stuck ...

Locked candidates (6) column 6 - remove 6 from r8c6
Locked candidates (8) column 8 - remove 8 from r4,6,7,8c8
Locked candidates (8) row 8 - remove 8 from r8c2
Naked triple (1,4,5) in row 3 - remove those candidates from other cells in row 3.
Locked candidates (1) in row 3 - remove 1 from r1c8 & r2c8.

Hope someone else can progress further.
CathyW
 
Posts: 316
Joined: 20 June 2005

Super Tough Sudoku from Crazy Dad...would love just a nudge

Postby QJohnson » Thu Nov 17, 2005 9:40 pm

Crazy Dad,
There appear to me to be possible values of 1 that should be added to r1,c8 and r2,c8 or did I miss some elimination you found?

Cathy - re: your recommendation:
Naked triple (1,4,5) in row 3 - remove those candidates from other cells in row 3.

I don't see those values in other cells in row 3 of crazydad's offering. Do you?

Can you tell me where I might look up info on the topic "locked candidates?" I just found this board and have to get up to speed on the syntax.

Many thanks. (btw, I agree - this one's really tough. A guess seems to be required to continue, at least for me)

Q
QJohnson
 
Posts: 2
Joined: 17 November 2005

Re: Super Tough Sudoku from Crazy Dad...would love just a nu

Postby CathyW » Thu Nov 17, 2005 9:51 pm

QJohnson wrote:Cathy - re: your recommendation:
Naked triple (1,4,5) in row 3 - remove those candidates from other cells in row 3.

I don't see those values in other cells in row 3 of crazydad's offering. Do you?


Sorry - I pasted the puzzle into Sadman software. Crazydad had obviously already spotted that triple!

Still haven't progressed any further. It probably needs a forcing chain or something else that I haven't got the hang of yet.
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby CathyW » Thu Nov 17, 2005 10:02 pm

I just pasted it into Sudoku Susser as well. Having got to the same point I asked the program to solve the next step and the solver log talked about a contradiction after Nishio cycles. I didn't understand it at all but I believe Nishio basically means making a guess!
CathyW
 
Posts: 316
Joined: 20 June 2005

Super Tough Sudoku from Crazy Dad...would love just a nudge

Postby QJohnson » Thu Nov 17, 2005 10:24 pm

OK. That makes me feel a little better. At least I understand the notation in use to describe things.

I have no idea what programs you're talking about. I"m a programmer myself, but writing a program to solve these sure seems to take the fun out of working them out myself. I don't think I'd ever want to do that.

I'd rather follow the result of a guess and back-track if it's wrong. On very tough ones, I often have to guess at least once. I just always guess where a cell can have only one of two values so that the guess confirms one of them. Is this what they mean here in other messages by a "forcing chain?"

Again, I hate to ask anyone here to explain all this. I'd be happy to read about it and learn the syntax myself. Where can I go to find this sort of stuff?

Thanks again, Cathy.

Q
QJohnson
 
Posts: 2
Joined: 17 November 2005

Postby tso » Thu Nov 17, 2005 10:39 pm

CathyW wrote:I just pasted it into Sudoku Susser as well. Having got to the same point I asked the program to solve the next step and the solver log talked about a contradiction after Nishio cycles. I didn't understand it at all but I believe Nishio basically means making a guess!


Nishio isn't making a guess. It's asking the question, "Does placing a number in this cell allow the rest of this number to be placed?"

In this case:
Code: Select all
 *--------------------------------------------------------------------*
 | 7      156    456    | 2      458    146    | 3      458    9      |
 | 19     3      459    | 14589  7      149    | 2      458    6      |
 | 269    269    8      | 3      45     69     | 14     7      15     |
 |----------------------+----------------------+----------------------|
 | 3      2678   267    | 1478   9      1247   | 5      1246   128    |
 | 2689   4      25679  | 1578   258    127    | 1689   3      128    |
 | 289    2589   1      | 458    6      3      | 489    249    7      |
 |----------------------+----------------------+----------------------|
 | 12689  12689  269    | 469    24     5      | 7      1269   3      |
 | 4      2679   3      | 679    1      279    | 689    2569   258    |
 | 5      12679  2679   | 679    3      8      | 169    1269   4      |
 *--------------------------------------------------------------------*


If r8c2=2, we can make these deductions:

a) r8c2=2 => r6c2<>2
b) r8c2=2 => r3c2<>2 => r3c1=2 => r6c1<>2
c) r8c2=2 => r8c9<>2 => r79c8=2 => r6c8<>2

This leaves nowhere in row 6 to place a 2, therefore, r8c2<>2.

Although Nishio can be described as trial and error limited to a single digit, it is a very human implementable tactic, easier than some of the "acceptable" tactics to do in your head or on paper without filtering or even using an eraser.

In fact, you can often apply Nishio without entering any pencil marks.

See how easy it is to do it in your head in this case:

Code: Select all
 7 . . | 2 . . | 3 . 9
 . 3 . | . 7 . | 2 . 6
 . . 8 | 3 . . | . 7 .
-------+-------+------
 3 . . | . 9 . | 5 . .
 . 4 . | . . . | . 3 .
 . . 1 | . 6 3 | . . 7
-------+-------+------
 . . . | . . 5 | 7 . 3
 4 . 3 | . 1 . | . . .
 5 . . | . 3 8 | . . 4


It's only a little more difficult to visualize than the typical cross hatching.
tso
 
Posts: 798
Joined: 22 June 2005

Postby CathyW » Thu Nov 17, 2005 11:20 pm

Thank you Tso. Nishio can be considered a legitimate logical method for solving? A case of "If, then, so ..."? This sounds very similar to a forcing chain. What's the difference?

I should add that I normally much prefer to solve Sudokus with pen (or pencil) and paper. I tend to use the software when I've got stuck:!:
CathyW
 
Posts: 316
Joined: 20 June 2005

Re: Super Tough Sudoku from Crazy Dad...would love just a nu

Postby r.e.s. » Fri Nov 18, 2005 1:18 am

QJohnson wrote:On very tough ones, I often have to guess at least once. I just always guess where a cell can have only one of two values so that the guess confirms one of them. Is this what they mean here in other messages by a "forcing chain?"

No, it means something very different. There are various types of forcing chain -- here is an example of one in the present puzzle that has what are called "strong" links, and eliminates the '8' from r6c7:

r6c7-4-r3c7-1-r3c9-5-r8c9-8-r8c7-8-r6c7

where A-x-B means
1) cells A,B are in the same unit (row/column/box), *and*
2) candidate digit x occurs in both cells A,B, *and*
3) x occurs nowhere else in that unit (this is what makes the link "strong", because it implies that x must occur in exactly one of the two cells).

The chain refers to the stage of solution when the candidate grid is
Code: Select all
  7      156    456    | 2      458    146    | 3      458    9     
  19     3      459    | 14589  7      149    | 2      458    6     
  269    269    8      | 3      45     69     |[14]     7    [15]   
 ----------------------+----------------------+-------------------
  3      2678   267    | 1478   9      1247   | 5      1246   128   
  2689   4      25679  | 1578   258    127    | 1689   3      128   
  289    2589   1      | 458    6      3      |[489]    249    7     
 ----------------------+----------------------+-------------------
  12689  12689  269    | 469    24     5      | 7      1269   3     
  4      2679   3      | 679    1      279    |[689]   2569  [258]   
  5      12679  2679   | 679    3      8      | 169    1269   4     

The reason for calling this a "forcing" chain, is that a pattern such as A-p-B-q-C-r-D-x-E-x-A "forces" the conclusion A<>x, as can be seen by breaking the chain into two segments at any chosen intermediate cell (say we pick the C cell to get segments A-p-B-q-C and C-r-D-x-E-x-A). Then ...
from A-p-B-q-C, going right-to-left, we get
C<>q => B=q => B<>p => A=p => A<>x
but from C-r-D-x-E-x-A, going left-to-right, we get
C=q => C<>r => D=r => D<>x => E=x => A<>x
Since it must be the case that either C<>q or C=q, and both cases lead to A<>x, it follows that A<>x.

I think it's important to note that it is not necessary to use any of the above logic in order to find the chain or to apply its "candidate elimination rule". This amounts to applying an established theorem without having to prove it every time.

(<rubylips' solver> solves this puzzle without Nishio, by finding lots of chains of different varieties.)
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby tso » Fri Nov 18, 2005 1:58 am

CathyW wrote:Thank you Tso. Nishio can be considered a legitimate logical method for solving? A case of "If, then, so ..."? This sounds very similar to a forcing chain. What's the difference?

I should add that I normally much prefer to solve Sudokus with pen (or pencil) and paper. I tend to use the software when I've got stuck:!:


The Nishio tactic pre-dates most of the advanced tactics discussed in this forum -- as well as the recent popularity of Sudoku.

In general, a forcing chain requires that each link is infered ONLY from the previous one and implies ONLY the next one. Otherwise it's refered to as a forcing NET. Nishio can be but is not usually a simple forcing chain. I this specific case, the Nishio can be defined as a relatively simple forcing chain:

If r8c2=2 => r3c2<>2 => r3c1=2 => r6c1<>2 => r6c8=2 => r789c8<>2 => r8c9=2 => r8c2<>2, which is a contradiction. Therefore r8c2<>2.


I think Nishio has fallen out of favor as many feel it is trial and error limited to a single digit, which I suppose is a fair argument if you are creating a software solution. But Nishio is a paper and pen solving method, one that can often be used before filling in every last pencil mark. To me, the line has always been: If I can do it in my head, it's a good tactic.
tso
 
Posts: 798
Joined: 22 June 2005

Thanks...and free puzzle site

Postby bathmatters » Fri Nov 18, 2005 3:55 am

Thank you all...I'm just relieved it wasn't something obvious like a hidden triplet!!!

My reference to "Krazydad" came from the krazy dad puzzles, found in free, untrammeled abundance at all different levels (including the super tough level of this current puzzle under discussion) at

http://krazydad.com/sudoku/books/

I am very grateful to all of you, BTW, and having a blast at this.

It is interesting that there are SO MANY LEVELS in which to participate. That is what makes it so appealing.

BTW--have any of you "topped out"--i.e. have gotten so proficient that it really isn't fun or challenging anymore?

Darreby
bathmatters
 
Posts: 4
Joined: 14 November 2005

more friendly url

Postby bathmatters » Fri Nov 18, 2005 3:58 am

Sorry--here's a more user-friendly way to get into Krazydad's site

http://www.krazydad.com/sudoku/
bathmatters
 
Posts: 4
Joined: 14 November 2005

Re: Thanks...and free puzzle site

Postby emm » Fri Nov 18, 2005 6:46 am

bathmatters wrote:BTW--have any of you "topped out"

I doubt that even years of practice will get me that proficient that the puzzles will be boring, but I do sometimes wonder if the lure will always be this strong. I’ve had a string of addictions over the years – some I can’t even remember what they were!

Somehow I think Sudoku is more likely to endure. There is a lot of variety in the Sudoku smorgasbord - levels of difficulty, different techniques, paper vs computer solving, candidate marking or not - plus all the variants.

Also there’s this forum. While it continues there are new ideas filtering through which raise the bar and heighten skill and understanding. My guess is the interest will endure - I s'pose time will tell.
emm
 
Posts: 987
Joined: 02 July 2005

Postby masb » Fri Nov 18, 2005 9:20 pm

According to my solver program (http://www.axcis.com.au/bb/viewtopic.php?t=25) you have to resort to trial and error to find that R7C5 is 4. From there it is solvable.
masb
 
Posts: 16
Joined: 17 November 2005

Postby r.e.s. » Fri Nov 18, 2005 9:37 pm

masb wrote:According to my solver program (http://www.axcis.com.au/bb/viewtopic.php?t=25) you have to resort to trial and error to find that R7C5 is 4. From there it is solvable.
That's not correct -- the forcing chain method I posted does not require T&E.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Next

Return to Advanced solving techniques