dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

An example of "Nishio"

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Mon Oct 17, 2005 6:23 pm    Post subject: An example of "Nishio" Reply with quote

Here's a very tough puzzle that requires use of the "Nishio" technique.
Code:

 .  .  6    .  2  .    7  .  5
 .  3  9    6  .  .    .  .  .
 8  .  .    .  .  .    .  .  .

 .  .  .    .  .  5    .  .  .
 .  .  2    .  1  .    6  .  .
 .  .  .    4  .  .    .  .  .

 .  .  .    .  .  .    .  .  4
 .  .  .    .  .  7    3  2  .
 7  .  8    .  9  .    1  .  .

Enjoy! dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Tue Oct 18, 2005 5:56 pm    Post subject: Another example of "Nishio" Reply with quote

Here's another puzzle that requires the "Nishio" technique. Here's a hint -- after 13 moves, analyze the possibilities for "2".
Code:

  .    .    5    2    .    .    .    .    4
  6    8    .    .    7    .    .    .    .
  .    .    .    .    .    .    .    1    5
  1    9    .    7    .    .    .    .    .
  .    .    .    4    3    1    .    .    .
  .    .    .    .    .    9    .    8    1
  8    6    .    .    .    .    .    .    .
  .    .    .    .    4    .    .    9    8
  2    .    .    .    .    8    6    .    .
Back to top
View user's profile Send private message Send e-mail Visit poster's website
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Wed Oct 19, 2005 12:27 pm    Post subject: Reply with quote

Hi,
For this last one I could make 14 moves:

8 in r5c3 - Unique Horizontal
8 in r4c5 - Unique Horizontal
8 in r1c7 8 in r3c4 - Unique Horizontal
6 in r1c8 - Unique in 3x3 block
7 in r3c7 - Unique in 3x3 block
3 in r1c6 - Sole Candidate
6 in r5c9 - Unique Horizontal
9 in r5c7 - Unique Horizontal
9 in r2c9 - Unique Vertical
7 in r5c8 - Unique in 3x3 block
5 in r5c1 - Sole Candidate
2 in r5c2 - Sole Candidate
2 in r3c3 - Unique Horizontal
3 not in r2c3, it is in r3c1 or r3c2 (Row on 3x3 Block interaction)
9 not in r7c5, it is in r7c4 or r9c4 (Column on 3x3 Block interaction)
9 not in r9c5, it is in r7c4 or r9c4 (Column on 3x3 Block interaction)

And now, as you have suggested, when analyzing the "2" and only the "2"s
we get quickly to the conclusion that "2" can't be in r7c6 and it can't be in r4c6. This last one implies that "2" must be in r6c5.

But, as much as I know, this is not Nishio, but "coloring" for the number "2". So, or so, I will not argue about the name of the technique.
(Nishio should involve more than one number ...).

BTW, I could find only cases to exclude one (or several) numbers by the coloring techniques only if the number of occurences was 15, 17 or 19.
In your example there where 15 occurences of "2"s.

Thank you for the nice example.

see u,
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Wed Oct 19, 2005 3:16 pm    Post subject: Defining the "Nishio" technique Reply with quote

Someone_Somewhere wrote:
But, as much as I know, this is not Nishio, but "coloring" for the number "2". So, or so, I will not argue about the name of the technique.
(Nishio should involve more than one number ...).

I don't want to argue, either. There seems to be quite a bit of confusion over terminology. Anyway, I saw this as a "Nishio" because I had to look at a particular placement of the value "2" and figure out that if I put the "2" there, I couldn't place all the rest of the "2"s in the puzzle (5 rows and columns without a "2" at that point, in this particular puzzle).

Was there another way to eliminate some of the "2"s? I'd like to understand that other method, if you can explain it a little bit.

Oh -- I found this definition of "Nishio" on the Sudoku Programmers bulletin board. I don't suppose that makes it right. But this definition doesn't say anything about more than one value. dcb

Sudoku Programmers BB wrote:
Definition:

Given a value and a candidate cell, the Nishio rule considers whether
the placement of the given value within the given cell would allow the
remaining instances of that value to be placed. The remaining
placements have be trivial, i.e. each value has to be placed in a row,
column or box where there exists just a single candidate cell - where
no trivial placement exists, the candidate move cannot be rejected.
When the remaining values cannot be placed, the initial candidate move
is eliminated.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Wed Oct 19, 2005 3:30 pm    Post subject: Reply with quote

Hi David,

I have reduced to the position:

Code:

79   17   5   2   19   3   8   6   4
6   8   14   15   7   45   23   23   9
349   34   2   8   69   46   7   1   5
1   9   346   7   8   256   2345   2345   23
5   2   8   4   3   1   9   7   6
347   347   3467   56   256   9   2345   8   1
8   6   13479   1359   125   257   12345   2345   237
37   1357   137   1356   4   2567   1235   9   8
2   13457   13479   1359   15   8   6   345   37


and have notice that number "2" occures 15 times.
So I am looking only at number "2":

Code:

.  .  .   .  .  .   .  .  .
.  .  .   .  .  .   2  2  .
.  .  .   .  .  .   .  .  .

.  .  .   .  .  2*  2  2  2
.  .  .   .  .  .   .  .  .
.  .  .   .  2  .   2*  .  .

.  .  .   .  2* 2   2  2  2
.  .  .   .  .  2   2  .  .
.  .  .   .  .  .   .  .  .


And using "colors" I quickly found out that the ones marked with "*" have to be eliminated.

Hope it is clear.

see u,


Last edited by someone_somewhere on Thu Oct 20, 2005 7:43 am; edited 1 time in total
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Wed Oct 19, 2005 5:39 pm    Post subject: It's not as clear as I'd like it to be Reply with quote

Someone_Somewhere wrote:
So I am looking only at number "2":

Code:

.  .  .   .  .  .   .  .  .
.  .  .   .  .  .   2  2  .
.  .  .   .  .  .   .  .  .

.  .  .   .  .  2*  2  2  2
.  .  .   .  .  .   .  .  .
.  .  .   .  2  .   2  .  .

.  .  .   .  2* 2   2  2  2
.  .  .   .  .  2   2  .  .
.  .  .   .  .  .   .  .  .

And using "colors" I quickly found out that the ones marked with "*" have to be eliminated.

Hope it is clear.


Well, I understand why there cannot be a "2" at either r4c6 or at r7c5. If either one of these cells contains a "2", then the other one must, because there are only two places to put a "2" in column 5, and in the middle center 3x3 box. But with "2" in both these spots, it becomes impossible to place a "2" in column 9. (Incidentally, there can't be a "2" at r6c7, either, for much the same reason -- r6c7 = 2 ==> r7c5 = r4c6 = 2 ==> no way to put the "2" in column 9.)

My problem is, I recognize this as a "Nishio," and I don't see how to color the cells alternately blue and green to reach this conclusion. It looks to me as if one must take the column 9 contradiction into account. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
someone_somewhere



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Thu Oct 20, 2005 7:37 am    Post subject: Reply with quote

Yes, you are right:

However you try to color the rest of the cells you will sooner or later came to a contradiction (the one of column 9 - is the shortes one).
And this means that the "initial" number (and some additional) can be excluded.

Now why do I use the word "coloring"? Because I simply isolate the graph with the number that occurs 15, 17 or 19 times in the candidate table and than start coloring from one of the numbers.
If the coloring leads to no contradiction, I take an other one (if possible not colored) and repeat the process.
It could be that every cell is in at least one coloring solution.
If I find a cell that leads to a contradiction (you called it Nishio, here) than I am happy and can take a look if he has not some relatives (conjugate cells) that can be shot too Wink
Sometimes I "see" just one cell that is not part of the colorings that I done till that point. So I take it as a candidate to be shoot.
If he is innocent (part of a valid coloring) I let him go.

That's what I am using. Examples will follow.

P.S. the 3 cells from the above examples are (probable) called conjugates and can be ALL eliminated together.

see u,
Back to top
View user's profile Send private message
David Bryant



Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado

PostPosted: Thu Oct 20, 2005 11:50 am    Post subject: What's in a name? Reply with quote

Someone_Somewhere wrote:

If the coloring leads to no contradiction, I take an other one (if possible not colored) and repeat the process.
It could be that every cell is in at least one coloring solution.
If I find a cell that leads to a contradiction (you called it Nishio, here) than I am happy and can take a look if he has not some relatives (conjugate cells) that can be shot too.

OK, we're doing the same thing and just referring to it by different names.

I thought that "coloring" was a slightly different process, akin to "X-Wing," where one marks cells in binary chains alternately blue and green -- if one can find a blue cell and a green cell "in line" with an uncolored cell, the uncolored cell can be eliminated as a candidate.

I guess there's more than one kind of "coloring." dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group