View previous topic :: View next topic |
Author |
Message |
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Mon Oct 17, 2005 6:23 pm Post subject: An example of "Nishio" |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Tue Oct 18, 2005 5:56 pm Post subject: Another example of "Nishio" |
|
|
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 |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Wed Oct 19, 2005 12:27 pm Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Wed Oct 19, 2005 3:16 pm Post subject: Defining the "Nishio" technique |
|
|
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 |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Wed Oct 19, 2005 3:30 pm Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Wed Oct 19, 2005 5:39 pm Post subject: It's not as clear as I'd like it to be |
|
|
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 |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Thu Oct 20, 2005 7:37 am Post subject: |
|
|
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
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Thu Oct 20, 2005 11:50 am Post subject: What's in a name? |
|
|
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 |
|
|
|
|
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
|