View previous topic :: View next topic 
Author 
Message 
Marty R.
Joined: 12 Feb 2006 Posts: 5562 Location: Rochester, NY, USA

Posted: Tue Mar 07, 2006 10:16 pm Post subject: Stumped 


I've tried this about five times, each time backing myself into a corner with a duplicate number. I'm ready for a new eraser. If someone's willing to take a shot at it and let me know what techniques you used to solve it, that would give me more confidence to take a sixth shot at it. Thanks.
(Do others have this problem of not being able to let go of a puzzle?)
Code:  
 . 3 6  . 4 .  5 . . 
 2 . .  . . .  . . 3 
 4 . 7  . 2 .  . . . 

 7 . 2  4 . .  1 . . 
 . 6 .  . . .  . 4 . 
 . . 5  . . 6  3 . 9 

 . . .  . 1 .  7 . 6 
 5 . .  . . .  . . 8 
 . . 9  . 5 .  2 1 . 
 


Back to top 


keith
Joined: 19 Sep 2005 Posts: 3284 Location: near Detroit, Michigan, USA

Posted: Wed Mar 08, 2006 12:36 am Post subject: Color me! 


Marty,
Using usual techniques and one XYwing, I get to this point:
Code: 
++++
 89A 3 6  1789 4 1789  5 2789 27 
 2 1589 18  6 89a 5789  4 789 3 
 4 589 7  3589 2 3589  6 89 1 
++++
 7 89 2  4 3 89  1 6 5 
 19 6 3  125 79 125  8 4 27 
 18a 4 5  12 78A 6  3 27 9 
++++
 3 28 48  289 1 2489  7 5 6 
 5 127 14  27 6 247  9 3 8 
 6 78 9  378 5 378  2 1 4 
++++

Did you get this far?
Now, there is coloring on <8>. One of R1C1 or R2C5 is <8>. Therefore, R2C2, R2C3, R1C4, and R1C6 are not <8>. Continuing on, we get to:
Code: 
++++
 89 3 6  17 4 179  5 2789 27 
 2 59 1  6 89 5789  4 789 3 
 4 589 7  38 2 3589  6 89 1 
++++
 7 89 2  4 3 89  1 6 5 
 19 6 3  5 79 12  8 4 27 
 18 4 5  12 78 6  3 27 9 
++++
 3 2 8  9 1 4  7 5 6 
 5 1 4  27 6 27  9 3 8 
 6 7 9  38 5 38  2 1 4 
++++

Note the unique rectangle: R3C6 cannot be <38>. Then, after a few more moves, there is an XYwing which solves the puzzle.
Nice one!!
Keith 

Back to top 


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

Posted: Wed Mar 08, 2006 12:41 am Post subject: Did you get this far? 


Hi, Marty!
If I start a puzzle I always finish it. I might have to put it aside for a day or so, and take a fresh crack at it, but I don't give up on these things!
Presumably you got this far without any trouble, because all the steps I had to make up to this point were pretty simple.
Code:  . 3 6 . 4 . 5 . .
2 . . 6 . . 4 . 3
4 . 7 . 2 . 6 . 1
7 . 2 4 3 . 1 6 5
. 6 . . . . 8 4 .
. 4 5 . . 6 3 . 9
. . . . 1 . 7 5 6
5 . . . 6 . 9 3 8
6 . 9 . 5 . 2 1 4 
To get past this spot I had to resort to coloring. That's the toughest technique I had to use to finish the puzzle ... I'll post more in a little while. dcb 

Back to top 


TKiel
Joined: 22 Feb 2006 Posts: 292 Location: Kalamazoo, MI

Posted: Wed Mar 08, 2006 1:01 am Post subject: 


Marty R,
Right off the bat I placed 12 naked and hidden singles. Then, and I must admit I didn't notice this until my second time through in solving it, I spotted a naked quad in box 5 (needless to say I didn't spot the hidden triple in the same box, until I'd made the exclusions from the quad and it became a naked triple). Then there is an xwing that makes exclusions from 3 cells and that allows the placement of another single. After that I found locked candidates in box 5 that allowed an exclusion from one cell. That exclusion allowed the placement of two cells in a different digit.
After that, get out your colours. The remainder of the puzzle solves mainly with colouring, mostly one chain but sometimes two, except there is a hidden pair in box 2, that you will find after a 5 has been placed in r2c2. I'm tried not to give away too much so I tried to be as cryptic as possible in the description of what I did. If you want more detail, give a shout. 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3284 Location: near Detroit, Michigan, USA

Posted: Wed Mar 08, 2006 1:15 am Post subject: A unique rectangle 


Marty,
This Unique Rectangle is a little different from the one discussed yesterday, so let me expand.
In a solved puzzle, the pattern
Code: 
.. X . Y ..
.
.
.. Y . X ..

is not allowed, for then X can be interchanged with Y, and there is a second valid solution. I believe the corners of the rectangle must be within two blocks. Obviously, they are in two rows and two columns.
In this case, we have the possibilities
Code: 
 38 . 3589 
++
 38 . 38 
++

The only way to exclude the nonunique X Y pattern is that the top right square can be neither of <38>. (Edited 8:48 EST)
Keith 

Back to top 


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

Posted: Wed Mar 08, 2006 1:56 am Post subject: An interesting twist on the "XYWing" 


Hi, Marty! I hope you're getting enough help on this puzzle.
In comparing the position I had reached before I started using colors on this puzzle against the first position Keith posted I noticed something pretty interesting. The only difference is that Keith had a "3" in r7c1 and in r5c3, which I had not yet solved for. Here's the position as I posted it, with the candidate lists filled in.
Code:  189 3 6 1789 4 1789 5 2789 27
2 1589 18 6 89 15789 4 789 3
4 589 7 3589 2 3589 6 89 1
7 89 2 4 3 89 1 6 5
139 6 13 125 79 125 8 4 27
18 4 5 12 78 6 3 27 9
38 28 348 289 1 2489 7 5 6
5 127 14 27 6 247 9 3 8
6 78 9 378 5 378 2 1 4 
The "XYWing" that Keith mentioned is a little unusual.
 There's an XWing pattern in the "3"s, at r5c1&3 and r7c1&3.
 So if r7c1 = 3 we must have r5c3 = 3 (by positional logic).
 Also, if r7c1 = 8 then r6c1 = 1 and r5c3 = 3.
 So we must have r5c3 = 3, and r7c1 = 3 (positional logic again).
This is a pretty cute pattern and a little bit different from a regular "XYWing"  that's why I'm pointing it out. Keith's explanation of the "coloring" logic beyond this point is excellent  I can't improve on it. dcb 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3284 Location: near Detroit, Michigan, USA

Posted: Wed Mar 08, 2006 3:13 am Post subject: Where from? 


Marty,
Where did you find this puzzle?
David, thank you for the compliment(s). I thought this coloring is really cool. Otherwise, how would you solve the puzzle?
Keith 

Back to top 


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

Posted: Wed Mar 08, 2006 4:44 pm Post subject: DIC's can also work 


Keith wrote:  I thought this coloring is really cool. Otherwise, how would you solve the puzzle? 
Well, coloring is certainly the simplest way to go. But we could also use "doubleimplication chains" to make progress from this point. Here's the position, from your previous post.
Code:  ++++
 89 3 6  1789 4 1789  5 2789 27 
 2 1589 18  6 89 5789  4 789 3 
 4 589 7  3589 2 3589  6 89 1 
++++
 7 89 2  4 3 89  1 6 5 
 19 6 3  125 79 125  8 4 27 
 18 4 5  12 78 6  3 27 9 
++++
 3 28 48  289 1 2489  7 5 6 
 5 127 14  27 6 247  9 3 8 
 6 78 9  378 5 378  2 1 4 
++++ 
Let's concentrate on r8c3:
A. r8c3 = 1 ==> r2c3 = 8 ==> r2c5 = 9 ==> r5c5 = 7
B. r8c3 = 1 ==> {2, 7, 8} in c2r789 ==> r4c2 = 9 ==> r4c6 = 8 ==> r6c5 = 7
But we can't have two "7"s in the middle center 3x3 box, so r8c3 = 4. That's not enough to solve the puzzle, but it does allow further progress.
Generally speaking, when a "coloring" solution is possible there's a "doubleimplication chain" that will also work. The converse is not true  that is to say, sometimes the DIC's will work when coloring won't. The thing is, the "coloring" solutions are fairly easy to spot because they involve simple binary chains. I've been working on them for a while now, but I still think the DIC's are hard to find. dcb 

Back to top 


Marty R.
Joined: 12 Feb 2006 Posts: 5562 Location: Rochester, NY, USA

Posted: Wed Mar 08, 2006 8:04 pm Post subject: 


Quote:  Now, there is coloring on <8>. One of R1C1 or R2C5 is <8>. Therefore, R2C2, R2C3, R1C4, and R1C6 are not <8>. Continuing on, we get to: 
Keith,
I'm going to have to do some research on "coloring", as I don't understand it. How do you select those two cells as the "one or the other" when there are "8s" all over the place?
I'm also going to have to further study the unique rectangles some more. I'll be printing out much of this thread. As I've mentioned before, I'm lost on the deductive reasoning aspects of these puzzles.
However, seeing as how everyone solved it, I was inspired to go back and try it a sixth time, and this time I did it, with the help of a couple of forcing chains. If it's possible to generalize based on this puzzle, I would have to conclude that there is often more than one technique which can be used to solve a puzzle.
Keith, this was one of the puzzles graded "Very hard" from http://www.sudokupuzzles.net/
Finally, I'd like to thank everyone for the welcome I've received here since joining just over three weeks ago. In no particular order, to Keith, David, Tracy, Steve, Alan, and anyone I may have forgotten, I very much appreciate the time and effort you've put in trying to explain things. 

Back to top 


keith
Joined: 19 Sep 2005 Posts: 3284 Location: near Detroit, Michigan, USA

Posted: Wed Mar 08, 2006 11:52 pm Post subject: Coloring  getting started 


Marty,
I talked about coloring in the thread "Nightmare of Feb 28". Here is the essential method, with some further explanation:
How does (simple) coloring work? For any value of a possibility (the "coloring value"), look in each element (row, column, block) of the puzzle to find where the possibility occurs exactly twice. Draw a line connecting the two squares.
(Actually, I just use a separate piece of squared paper with a 9x9 empty grid to do this.)
When you are done, you may have a collection of "graphs", networks of lines that connect pairs of possibilities. Now, you can use two colors (say, red and green) to alternately label each square on the graph. Either the red squares have the possible value, or the green squares do.
Another convention is to label alternate nodes of the graph with upper and lower case letters. "A" and "a" for the first graph, "B" and "b" for the second, etc.
There are two implications to look for:
1. Two squares in the same element (row, column or block) have the same label, say "a". Then, the squares labelled "A" must be the coloring value.
2. Squares which are neighbors of both of any two squares labelled "a" and "A" cannot have the coloring value. This is what applies here.
So, coloring is a completely explainable technique. You do not need some sixth sense or special ability to spot patterns. In fact, the coloring process, of connecting the "conjugate" squares, will also help you to find swordfish, etc.
You can find more by searching on "sudoku coloring" on Google. Be sure to also search on the British spelling, "sudoku colouring". Personally, I found the explanation on the SadMan site to be the most helpful.
Best wishes,
Keith 

Back to top 


TKiel
Joined: 22 Feb 2006 Posts: 292 Location: Kalamazoo, MI

Posted: Thu Mar 09, 2006 12:57 am Post subject: 


Marty R,
One of the advantages of explaining a technique to someone else is it often helps to crystalize things in ones own mind, so it actually benefits both parties. Thanks for the kind words.
In regard to your question about colouring, the cells really select themselves. As I understand how it all came about, angus johnson (www.angusj.com) first called the technique colouring (which he acknowledges he did not first propose) because the puzzle generator he wrote allowed assigning different colours to particular cells, for purposes of identification. He used different colours to indicate the relationship between the cells and the technique became known as colouring.
Simple colouring refers to labeling cells that are conjugates of each other. Conjugate means they are the only two cells in a group (row, column or box) that have a certain digit as a candidate. Conjugate cells have a special relationship: not only is it a fact that if one is true, the other is false, it is also a fact that if one if false then the other is true. This is immensely powerful. If cell 1 & cell 2 are conjugates, if I prove cell 1 true, then I know that cell 2 is false. It's also true that if I prove cell 2 false, then I know that cell 1 is true. The end result is the same (cell 1 = true, cell 2 = false) but I have two ways to go about proving that, either by eliminating the possibility of cell 2 = true or by actually proving cell 1 = true.
Labeling one cell with one color and a conjugate cell with a different color implies nothing about which is those cells is true or false. It only allows the solver to see the relationship. When cells can be linked with alternating colours in such a manner it is called a conjugate chain or just a chain. All the cells marked with blue will end up being true or all the cells marked with green will end up being true; we just don't know which. When a cell that is not part of the chain shares a group (row, column or box) with a cell marked with each colour, we know that cell cannot possibly be true.
This grid is from the puzzle you posted at the top of this thread. Instead of colours, I've use (A) and (a) to indicate states of oppositeness.
Code: 
**
 189 3 6  1789 4 1789  5 2789 27 
 2 1589 18  6 89a 15789  4 789 3 
 4 589 7  3589 2 3589  6 89 1 
++
 7 89A 2  4 3 89  1 6 5 
 139 6 13  125 79 125  8 4 27 
 18a 4 5  12 78A 6  3 27 9 
++
 38 28 348  2389 1 23489  7 5 6 
 5 127 14  27 6 247  9 3 8 
 6 78 9  378 5 378  2 1 4 
**

Looking only at cells with candidate 8's, R4c2(A) is conjugate with r6c1(a) is conjugate with r6c5(A) is conjugate with r2c5(a). The 1st & 2nd cells share a box, the 2nd & 3rd share a row and the 3rd & 4th share a column and are the only cells in those respective groupings with 8 as a candidate. We know that either cells marked with (A) will end up being 8 or that cells marked with (a) will end up being 8. R2c2 has an 8 but it shares a row with r2c5(a) and a column with r4c2(A). One of those cells must be 8. We don't know which will be 8, but one of them must be, so the 8 in r2c2 can be excluded.
What happens if r2c2 is 8? Then r2c5 can't be 8, so r6c5 must be 8 and r4c2 can't be 8, so r6c1 must be 8. But that leaves us with two 8's (r6c5 & r6c1) in row 6, which we know is a contradiction. Therefore, we can exclude the 8 in r2c2. That is simple colouring using one conjugate chain. If there is an exclusion to be found, it doesn't matter where one starts the chain, as long as all the cells that could be included in the chain are included in the chain, the exclusion will be found. Keep in mind that every conjugate chain will not necessarily lead to an exclusion. 

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
