| View previous topic :: View next topic |
| Author |
Message |
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
 Posted: Sat Sep 23, 2006 12:03 pm Post subject: DB Saturday Puzzle - September 23, 2006 |
 |
|
| Code: | Puzzle: DB092306 ******
+-------+-------+-------+
| . . 2 | . . . | 3 9 . |
| . 4 . | . . . | 8 5 . |
| . . . | . 4 9 | 6 . 1 |
+-------+-------+-------+
| 2 . 6 | 8 . . | . 3 . |
| . . . | 6 . 3 | . . . |
| . 8 . | . . 2 | 9 . 6 |
+-------+-------+-------+
| 7 . 4 | 3 8 . | . . . |
| . 2 3 | . . . | . 4 . |
| . 9 8 | . . . | 7 . . |
+-------+-------+-------+ |
|
|
| Back to top |
|
 |
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sat Sep 23, 2006 3:58 pm Post subject: |
|
|
After the usual stuff plus a not-very-helpful XY-Wing, I reached this position, with its glut of 1-2-5-6-7s. It's easily solvable with a chain based in r5c7 (and probably other cells), but there might be a more sophisticated solution which eludes me. There's that almost rectangle in boxes 4&6, but I can't do anything with it, perhaps because box 4 has no bi-value cells.
| Code: | -------------------------------------------------
|156 1567 2 |157 15 8 |3 9 4 |
|9 4 17 |127 3 6 |8 5 27 |
|8 3 57 |257 4 9 |6 27 1 |
-------------------------------------------------
|2 157 6 |8 9 15 |4 3 57 |
|4 157 9 |6 157 3 |12 8 257 |
|3 8 157 |4 57 2 |9 17 6 |
-------------------------------------------------
|7 156 4 |3 8 15 |125 126 9 |
|15 2 3 |9 6 7 |15 4 8 |
|156 9 8 |15 2 4 |7 16 3 |
------------------------------------------------- |
|
|
| Back to top |
|
|
TKiel
Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI
|
| Posted: Sat Sep 23, 2006 4:53 pm Post subject: |
|
|
| There are a few colouring & multi-colouring exclusions at this point. |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Sat Sep 23, 2006 8:00 pm Post subject: Look at "Nishio" / "Empty Rectangle" |
|
|
| Marty R wrote: | | ... but there might be a more sophisticated solution which eludes me. |
At this point in the puzzle there are a couple of "Nishio" moves that will solve it.
| Code: | *-----------------------------------------------------------*
| 156A 1567 2 | 157 15B 8 | 3 9 4 |
| 9 4 17 | 127 3 6 | 8 5 27 |
| 8 3 57 | 257 4 9 | 6 27 1 |
|-------------------+-------------------+-------------------|
| 2 157 6 | 8 9 15 | 4 3 57 |
| 4 157 9 | 6 157 3 | 12 8 257 |
| 3 8 157B | 4 57 2 | 9 17 6 |
|-------------------+-------------------+-------------------|
| 7 156 4 | 3 8 15 | 125 126 9 |
| 15 2 3 | 9 6 7 | 15 4 8 |
| 156 9 8 | 15A 2 4 | 7 16 3 |
*-----------------------------------------------------------* |
Notice the "strong links" in rows 6 & 9, on digit "5".
A. r1c1 = 5 ==> r9c4 = 5 ==> can't place a "5" in box 2.
B. r1c5 = 5 ==> r6c3 = 5 ==> can't place a "5" in box 1.
So we can eliminate "5" at r1c1, and at r1c5, and the rest of the puzzle is straightforward.
Oh -- I think of this as "Nishio" because placing the "5" in either r1c1 or r1c5 renders the puzzle unsolvable. I think this sort of formation has more recently gained the sobriquet "empty rectangle". I'm having a hard time understanding the explanations of the "ER" in other forums -- I have to turn them around and think of the contradiction. Maybe my head's in a rut ... dcb  |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sat Sep 23, 2006 8:26 pm Post subject: |
|
|
Tracy,
Multi-coloring is something that I've never understood, maybe I'm too dense to grasp it, maybe I haven't seen an explanation of the type that I can understand. At any rate, can you point out one or two of the simple colorings that you found?
David,
I've read definitions of "Nishio" and I'm not sure I have an understanding of that either. But in my little world, any time a cell is tested for a particular value to see what happens falls into my very broad definition of chains.
What is there about unconnected strong links in rows 6 and 9 that triggered you to do something, specifically test some values in row1? |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Sep 23, 2006 8:29 pm Post subject: Strong links |
|
|
It seems that Tracy and I have similar soultions:
In the position posted by Marty, note the two strong links on <1> originating in box 4. The one in R4 can be extended down C6 and across box 8. The net result is a multicoloring "fork" which eliminates <1> in R2C4.
Using almost the same cells, you can do multicoloring on <5> to eliminate <5> from R3C4, which solves the puzzle. (There is a X-wing on <7> which does not immediately solve it.)
Keith |
|
| Back to top |
|
|
ravel
Joined: 21 Apr 2006
Posts: 536
|
| Posted: Sat Sep 23, 2006 8:50 pm Post subject: |
|
|
| Marty R. wrote: |
What is there about unconnected strong links in rows 6 and 9 that triggered you to do something, specifically test some values in row1? |
To say it from the Empty-rectangle-POV:
| Code: | *-----------------------------------------------------------*
|-156 1567 2 |+157 15 8 | 3 9 4 |
| 9 4 17 | 127 x3 x6 | 8 5 27 |
| 8 3 57 | 257 x4 x9 | 6 27 1 |
|-------------------+-------------------+-------------------|
| 2 157 6 | 8 9 15 | 4 3 57 |
| 4 157 9 | 6 157 3 | 12 8 257 |
| 3 8 157 | 4 57 2 | 9 17 6 |
|-------------------+-------------------+-------------------|
| 7 156 4 | 3 8 15 | 125 126 9 |
| 15 2 3 | 9 6 7 | 15 4 8 |
|#156 9 8 |#15 2 4 | 7 16 3 |
*-----------------------------------------------------------*
|
You can spot the strong link in row 9. You could spot the ER (can only be in boxes 12 or 13) marked with x. This means, if r9c4=5, then r1c5 (in other cases maybe also r1c6) must be 5. So r1c1 could not be 5.
But when r9c4 is not 5, then r9c1 and r1c1 cannot be 5 either.
Expressed as chain:
Either r9c1=5 => r1c1<>5
or r9c4=5 => r13c4<>5 => r1c4=5 => r1c1<>5 |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Sep 23, 2006 9:07 pm Post subject: Empty Rectangle: Hinge |
|
|
David,
The original name for the "empty rectangle" was "hinge", which I think is more descriptive. You will find more by searching on "hinge" and "sudoku", particularly on the British sites.
Let me try to explain:
You need to find a box where the all candidates for a particular value lie only in one row AND one column. The "pivot" cell is the intersection of the row and column. Also, you need a strong link, one end of which is aligned with the pivot cell.
| Code: | +-------+-------+-------+
| * * * | . . @ | . . . |
| . . * | . . . | . . . |
| . . * | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . # | . . @ | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+ |
The hinge is * in box 1. The pivot cell is R1C3. The strong link is @ - @ in C6. The candidate value can be eliminated in the cell #. The logic is quite simple:
If the lower @ is true, # cannot be.
If the upper @ is true, the candidates in box 1 are all in C3, and # cannot be.
The "empty rectangle" is the block of four cells in box 1 which do not contain the candidate value. I find it much easier to look for the row and column comprising the hinge.
Note that all the cells defining the hinge do not have to contain the candidate. For example, the following works:
| Code: | +-------+-------+-------+
| . . . | . . . | . . . |
| * . * | . . @ | . . . |
| . . * | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . # | . . @ | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+ |
and other variations are possible.
Keith
(edited for clarity 5:40 EST 9/23)
Last edited by keith on Sat Sep 23, 2006 9:39 pm; edited 1 time in total |
|
| Back to top |
|
|
TKiel
Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI
|
| Posted: Sat Sep 23, 2006 9:09 pm Post subject: |
|
|
Marty R.,
Here is a simple colouring chain on digit 5 that excludes 5 in r1c5.
| Code: |
*-----------------------------------------------------------*
| 156 1567 2 | 157 15 8 | 3 9 4 |
| 9 4 17 | 127 3 6 | 8 5 27 |
| 8 3 57A | 257a 4 9 | 6 27 1 |
|-------------------+-------------------+-------------------|
| 2 157 6 | 8 9 15 | 4 3 57 |
| 4 157 9 | 6 157 3 | 12 8 257 |
| 3 8 157a | 4 157A 2 | 9 17 6 |
|-------------------+-------------------+-------------------|
| 7 156 4 | 3 8 15 | 125 126 9 |
| 15 2 3 | 9 6 7 | 15 4 8 |
| 156 9 8 | 15 2 4 | 7 16 3 |
*-----------------------------------------------------------*
|
Lets pretend the cells in row 3 are not strongly linked. We would have two seperate chains (A,a) and (B,b), which are connected by a weak link in row 3. We know that A & B both can't be 5, so at leat one of a & b must be. Any cell that 'sees' a & b can't be 5. That's multi-colouring.
| Code: |
*-----------------------------------------------------------*
| 156 1567 2 | 157 15 8 | 3 9 4 |
| 9 4 17 | 127 3 6 | 8 5 27 |
| 8 3 57A | 257a 4 9 | 6 27 1 |
|-------------------+-------------------+-------------------|
| 2 157 6 | 8 9 15 | 4 3 57 |
| 4 157 9 | 6 157 3 | 12 8 257 |
| 3 8 157B | 4 157b 2 | 9 17 6 |
|-------------------+-------------------+-------------------|
| 7 156 4 | 3 8 15 | 125 126 9 |
| 15 2 3 | 9 6 7 | 15 4 8 |
| 156 9 8 | 15 2 4 | 7 16 3 |
*-----------------------------------------------------------*
|
From the same position in the puzzle, there is multi-colouring on 1 that excludes 1 from r1c2 and r6c3. Two chains weakly linked in column 4 with b & a, so at least one of A & B must be 1.
| Code: |
*-----------------------------------------------------------*
| 156 1567 2 | 157 15 8 | 3 9 4 |
| 9 4 17B | 127b 3 6 | 8 5 27 |
| 8 3 57 | 257 4 9 | 6 27 1 |
|-------------------+-------------------+-------------------|
| 2 157A 6 | 8 9 15a | 4 3 57 |
| 4 157 9 | 6 157 3 | 12 8 257 |
| 3 8 157 | 4 157 2 | 9 17 6 |
|-------------------+-------------------+-------------------|
| 7 156 4 | 3 8 15A | 125 126 9 |
| 15 2 3 | 9 6 7 | 15 4 8 |
| 156 9 8 | 15a 2 4 | 7 16 3 |
*-----------------------------------------------------------*
|
From the same position, here is Keith's multi-colouring that excluded 1 from r2c4. Two chains weakly linked in box 4 with A & B, so at least one of a & b must be 1.
| Code: |
*-----------------------------------------------------------*
| 156 1567 2 | 157 15 8 | 3 9 4 |
| 9 4 17b | 127 3 6 | 8 5 27 |
| 8 3 57 | 257 4 9 | 6 27 1 |
|-------------------+-------------------+-------------------|
| 2 157A 6 | 8 9 15a | 4 3 57 |
| 4 157 9 | 6 157 3 | 12 8 257 |
| 3 8 157B | 4 157 2 | 9 17 6 |
|-------------------+-------------------+-------------------|
| 7 156 4 | 3 8 15A | 125 126 9 |
| 15 2 3 | 9 6 7 | 15 4 8 |
| 156 9 8 | 15a 2 4 | 7 16 3 |
*-----------------------------------------------------------*
|
|
|
| Back to top |
|
|
TexCat
Joined: 07 Jul 2006
Posts: 32
|
| Posted: Sat Sep 23, 2006 10:34 pm Post subject: |
|
|
I love these Saturday puzzles. I always finish them by trial and error (or maybe I should say chains or coloring???). It's always interesting though to see how to do them with more logic and less trial and error.
Could someone point me to an explanation of strong links and/or weak links? They keep coming up, and I keep getting lost.
Thanks.
Cathy |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sat Sep 23, 2006 10:58 pm Post subject: Strong Links |
|
|
Cathy,
Havard wrote the definitive explanation of strong links:
http://www.sudoku.com/forums/viewtopic.php?t=3326
I am still learning, but I have the firm opinion: Understand strong links, and you will be at a new level in solving Sudoku!
Keith |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Sun Sep 24, 2006 12:00 am Post subject: What an interesting thread! |
|
|
Wow! We have a very good discussion going this time. Thanks for posting this puzzle, Keith.
| Keith wrote: | | The original name for the "empty rectangle" was "hinge", which I think is more descriptive. You will find more by searching on "hinge" and "sudoku", particularly on the British sites. |
Not to put too fine a point on it, Keith, but I don't think so. The original name was "nishio", coined in Japan years before the sudoku craze got started in Australia and the UK. But "nishio" got a bad reputation fairly early, as being a form of trial and error.
I've read a lot of posts in other forums, and it appears to me that several special forms of "nishio" have now been incorporated into many automated solvers as "positive" rules. Some instances of "almost locked sets", plus every instance of the "empty rectangle" or "hinge", spring to mind. I learned to recognize this particular pattern before the "hinge" was named (by Rod Hagglund. in December, 2005). See this post and the definition of "Nishio" I presented on page 2 (it's a long topic). 
| Marty R wrote: | | I've read definitions of "Nishio" and I'm not sure I have an understanding of that either. But in my little world, any time a cell is tested for a particular value to see what happens falls into my very broad definition of chains. |
I think that "Nishio" is a form of a chain. But it's a particular type of chain, involving only a single digit, and relying entirely on the pattern of cells in which that particular digit can be placed.
| Marty R wrote: | | What is there about unconnected strong links in rows 6 and 9 that triggered you to do something, specifically test some values in row1? |
I didn't rely on the strong links to recognize this pattern. That's just a convenient way to explain the logic. What I looked at was the pattern of possible placements for the digit "5".
| Code: | *-----------------------------------------------------------*
| 5? 5? x | 5? 5? x | x x x |
| x x x | x x x | x *5* x |
| x x 5? | 5? x x | x x x |
|-------------------+-------------------+-------------------|
| x 5? x | x x 5? | x x 5? |
| x 5? x | x 5? x | x x 5? |
| x x 5? | x 5? x | x x x |
|-------------------+-------------------+-------------------|
| x 5? x | x x 5? | 5? x x |
| 5? x x | x x x | 5? x x |
| 5? x x | 5? x x | x x x |
*-----------------------------------------------------------* |
In this form I think the fact that "5" can be excluded from r1c1 and from r1c5 is immediately apparent, by simple cross-hatching. This is the distinctive feature of all "nishio" moves -- we can spot them by preparing a table (what RubyLips called the "Number State grid") that simply shows where each instance of a particular unplaced digit might possibly appear. The digit can be eliminated from cells that would cause a contradiction if the target digit were placed there.
If r1c1 = 5 I'll have to place a "5" at r3c4 (to fit one in box 2) and also at r9c4 (to fit one in row 9).
If r1c5 = 5 I'll have to place a "5" at r3c3 (to fit one in box 1) and also at r6c3 (to fit one in row 6).
| TexCat wrote: | | Could someone point me to an explanation of strong links and/or weak links? They keep coming up, and I keep getting lost. |
Here's a definition in a nutshell, TexCat.
Two cells that might contain the same target digit "x" are strongly linked if that digit has to appear in one or the other of them. For instance, if there are only two cells left in row 6 that can contain a "5", then there's a strong link between those two cells.
Two cells that might contain the same target digit "x" are weakly linked if there are more than two possible placements for "x" within a "house" (that is, in the same column, or row, or 3x3 box). So in the grid above, the possible "5"s in box 1 (that is, at r1c1, r1c2, and r3c3) are connected by weak links -- if I know that r1c1 = 5 I can be sure that r1c2 is not 5, but if I know that r1c2 is not 5, I cannot conclude that r1c1 is 5. dcb |
|
| Back to top |
|
|
Steve R
Joined: 24 Oct 2005
Posts: 289
Location: Birmingham, England
|
| Posted: Sun Sep 24, 2006 12:14 am Post subject: |
|
|
Any argument which solves a puzzle is quite good enough for me but I cannot resist mentioning an alternative found after others had done the work: in Marty’s grid 1 may be placed in r1c5 using the fork for 5 based on rows 3 and 6.
Steve |
|
| Back to top |
|
|
Marty R.
Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA
|
| Posted: Sun Sep 24, 2006 2:14 am Post subject: |
|
|
Thank you everybody, I've got a lot of material to try and digest. I should have caught that fork on "5" in rows 3 and 6, because I specifically look for that stuff.
A comment about Empty Rectangles. I read and printed out the dissertation on same, maybe another one of Havard's posts. After that, I looked for them for awhile, but never came close to scoring. I just stopped looking after awhile, as it seemed a very low probability type of thing.
Months elapsed and I never saw the term used in the forum, now I've seen it a couple of times in the last week. Maybe I should revisit it.
I'll probably be back after with more questions after studying some of this stuff. Thanks again. |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Sep 24, 2006 3:08 am Post subject: |
|
|
Wow! What a thread!
I was born and raised on the explanations of Robert Woodhead ("Mad Overlord") and his excellent solver, "Sudoku Susser". He says that Nishio is a form of "Structured Guessing".
If the Hinge is a case of Nishio, I have much to learn. I never paid much attention to Nishio, I thought it was for computers, not for human solvers using pencil & paper.
Keith
Last edited by keith on Sun Sep 24, 2006 3:21 am; edited 1 time in total |
|
| Back to top |
|
|
TKiel
Joined: 22 Feb 2006
Posts: 292
Location: Kalamazoo, MI
|
| Posted: Sun Sep 24, 2006 3:09 am Post subject: |
|
|
I looked at the 'this post' link in David Bryant's post above and just for kicks I had a go at the puzzle under discussion. I got it to this point:
| Code: |
*--------------------------------------------------*
| 1 2 3 | 8 4 5 | 9 7 6 |
| 57 8 57 | 9 6 2 | 1 4 3 |
| 6 9 4 | 7 3 1 | 2 8 5 |
|----------------+----------------+----------------|
| 29 7 126 | 56 8 49 | 45 3 12 |
| 389 4 18 | 35 2 79 | 58 6 17 |
| 238 5 268 | 36 1 47 | 48 9 27 |
|----------------+----------------+----------------|
| 27 1 9 | 4 57 3 | 6 25 8 |
| 4 6 27 | 1 57 8 | 3 25 9 |
| 58 3 58 | 2 9 6 | 7 1 4 |
*--------------------------------------------------*
|
It appears that there is an ER in box 7 with all the candidate 2's in row 7 and column 3, which would make r7c3 the pivot. R7c8 & r8c8 are strongly linked and r7c8 is aligned with the pivot. Does that mean that the 2 can be excluded from r8c3? |
|
| Back to top |
|
|
Myth Jellies
Joined: 27 Jun 2006
Posts: 64
|
| Posted: Sun Sep 24, 2006 7:09 am Post subject: |
|
|
The original description/method of nishio is the following:
For a grid focused on a single digit.
Assume that digit occupies a certain start cell.
If, from that assumption, you cannot then place that digit in every group, then you can remove that digit as an option from that start cell.
From this description, it is easy to see why nishio is considered a brute force or T&E method.
The logic behind hinges can be used by nishio, but they can also be accomplished via simple grouped coloring or multi-coloring, and thus can be used without ever assuming any digit occupies a particular cell so long as you don't ever assume a particular color represents true or false. Therefore, hinges, per se, are not nishio.
To further confuse the issue, there are ways to accomplish all nishio, or single-digit reductions using templating which also does not make any assumptions about any cell containing or not containing a digit. These templating methods are not related to hinges either. Since no assumptions are made, some believe that these templating nishio methods are not as brute force/T&E as the original nishio is. |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Sep 24, 2006 1:28 pm Post subject: |
|
|
Tracy wrote:
| Quote: | | Does that mean that the 2 can be excluded from r8c3? |
Tracy,
No. The cell in which the elimination occurs needs to lie outside the box containing the hinge.
Keith |
|
| Back to top |
|
|
TexCat
Joined: 07 Jul 2006
Posts: 32
|
| Posted: Sun Sep 24, 2006 2:33 pm Post subject: TY |
|
|
| Thanks for the link, Keith, and the explanation, dcb. A little bit more is making sense to me now. |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Sun Sep 24, 2006 6:53 pm Post subject: In defense of "nishio" |
|
|
"A rose by any other name would smell as sweet."
| Myth Jellies wrote: | | The original description/method of nishio is the following: For a grid focused on a single digit. Assume that digit occupies a certain start cell. If, from that assumption, you cannot then place that digit in every group, then you can remove that digit as an option from that start cell. From this description, it is easy to see why nishio is considered a brute force or T&E method. |
With all due respect, MJ, I don't think this is easy to see, at all. Consider the following example.
| Code: | . . . . . . . . .
. . . . . . . 7? .
. 7? . . . . . 7? .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . . |
Now, the thought process that says "If I place a "7" at r3c8, I will not be able to complete the puzzle, so the "7" in column 8 must appear in row 2" fits the definition of nishio exactly as you gave it. Does that thought process constitute "trial and error"? I submit that it does not constitute T&E. It's entirely logical, it works just as well as saying "The possible '7' at r2c8 is unique in row 2" and, depending on the image of the grid that exists in the mind of the solver, it may be easier to see.
| Myth Jellies wrote: | | The logic behind hinges can be used by nishio, but they can also be accomplished via simple grouped coloring or multi-coloring, and thus can be used without ever assuming any digit occupies a particular cell ... |
It's not that the "logic behind hinges" can be used by nishio -- it's the exact same logic in either case. The solver who employs nishio says "If I place this digit here, I can't complete the puzzle." The solver who recognizes the "hinge pattern" in effect says "I know that somebody used a proof by contradiction to show that I can't place this digit here." The "hinge" is just a black box that conceals the reductio ad absurdum from the innocent.
| Myth Jellies wrote: | | Therefore, hinges, per se, are not nishio. |
Yeah, right. Hinges are not nishio, just like trout are not fish, and humans are not mammals. The "hinge" is a special case of nishio, just like the X-Wing and the swordfish are special cases. Moreover, the distinction you're attempting to draw lacks substance. Formal logic tells us that the statements "A" and "not(not A)" always have the same truth value. A proof by contradiction is just as good as any other.
| Myth Jellies wrote: | | To further confuse the issue, there are ways to accomplish all nishio, or single-digit reductions using templating which also does not make any assumptions about any cell containing or not containing a digit. These templating methods are not related to hinges either. Since no assumptions are made, some believe that these templating nishio methods are not as brute force/T&E as the original nishio is. |
Imho, anybody who believes that needs a refresher course in Boolean Algebra. All that a "templating method" accomplishes is to hide the details of the proof by contradiction inside a black box.
I'm not really interested in reopening the "T&E" debate. That's been done to death already. What I am interested in is understanding how to solve these puzzles quickly and easily. And that means concentrating on the simple logic that underlies the process. Two useful considerations spring to mind.
The first one is that computers don't work the same way the human mind does. A digital computer is a serial processor -- its program has to operate one step at a time. Even the modern "parallel processing" or "massively parallel" machines can't break this rule -- they're just able to run many linked serial processes simultaneously. But the human mind can keep several different facts in view all at once. Too often our internal logic runs in fits and starts. But it doesn't have to. Sometimes a flash of insight can fuse several different facts into one almost instantaneous conclusion. (I don't have time to get into it right now, but the human mind can perform a type of "combinatorial sorting algorithm" that would beat all existing automated sorting algorithms hands down if only the machine could be made to "see" the entire list all at once. I'll write about that another day.)
The second consideration is that rules for solving sudoku puzzles should be operationally useful. The "nishio" technique is useful to human solvers. It's easier to apply than many of the canned templates that have been getting all the fancy names lately. So why not use it when the opportunity arises?
Here's an example that illustrates my point rather beautifully. It's drawn from Ruud's nightmare puzzle for today, Sunday, 24 September, 2006.
| Code: | 8? . 8? . . . 8? 8? .
. 8S 8S . . . 8S 8F .
. . . . *8* . . . .
. 8S . . . . 8S . .
8? . 8? 8? . . 8? 8? .
. 8? 8? 8? . . 8? 8? .
. 8S 8S . . . . . .
. . . . . *8* . . .
. . . . . . . . *8* |
I've marked the "finned swordfish" in the grid above. Either the "fin" at r2c8 is true, or else there's a "swordfish" pattern in rows 2, 4, and 7. Either way, there cannot possibly be an "8" at r1c7.
What does it look like from the nishio point of view? Here's the same grid.
| Code: | 8? . 8? . . . 8N 8? .
. 8? 8? . . . 8? 8? .
. . . . *8* . . . .
. 8N . . . . 8? . .
8? . 8? 8? . . 8? 8? .
. 8? 8? 8? . . 8? 8? .
. 8? 8N . . . . . .
. . . . . *8* . . .
. . . . . . . . *8* |
r1c7 = 8 ==> r4c2 = 8 ==> r7c3 = 8 ==> box 1 cannot be completed.
Which pattern is easier to spot? To get to either one we must first notice where the "8"s can fit in this puzzle. I submit that the "nishio" pattern is easier to see and easier to understand than the finned swordfish -- it only involves three critical "target" cells to pick it out, while the finned swordfish involves eight cells (plus a ninth, from which "8" can be eliminated).
It appears to me that the "nishio" elimination is, in this instance at least, operationally more useful to a human solver. Why let some high-flown rhetoric about "brute force" stand between the solver and an elegant solution? 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
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
