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 

Stumped

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



Joined: 12 Feb 2006
Posts: 5176
Location: Rochester, NY, USA

PostPosted: Tue Mar 07, 2006 10:16 pm    Post subject: Stumped Reply with quote

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
View user's profile Send private message
keith



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

PostPosted: Wed Mar 08, 2006 12:36 am    Post subject: Color me! Reply with quote

Marty,

Using usual techniques and one XY-wing, 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 XY-wing which solves the puzzle.

Nice one!!

Keith
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Wed Mar 08, 2006 12:41 am    Post subject: Did you get this far? Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
TKiel



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

PostPosted: Wed Mar 08, 2006 1:01 am    Post subject: Reply with quote

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 x-wing 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
View user's profile Send private message
keith



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

PostPosted: Wed Mar 08, 2006 1:15 am    Post subject: A unique rectangle Reply with quote

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 non-unique X Y pattern is that the top right square can be neither of <38>. (Edited 8:48 EST)

Keith
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Wed Mar 08, 2006 1:56 am    Post subject: An interesting twist on the "XY-Wing" Reply with quote

Hi, Marty! I hope you're getting enough help on this puzzle. Smile

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 "XY-Wing" that Keith mentioned is a little unusual.

-- There's an X-Wing 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 "XY-Wing" -- 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
View user's profile Send private message Send e-mail Visit poster's website
keith



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

PostPosted: Wed Mar 08, 2006 3:13 am    Post subject: Where from? Reply with quote

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
View user's profile Send private message
David Bryant



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

PostPosted: Wed Mar 08, 2006 4:44 pm    Post subject: DIC's can also work Reply with quote

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 "double-implication 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 "double-implication 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
View user's profile Send private message Send e-mail Visit poster's website
Marty R.



Joined: 12 Feb 2006
Posts: 5176
Location: Rochester, NY, USA

PostPosted: Wed Mar 08, 2006 8:04 pm    Post subject: Reply with quote

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.sudoku-puzzles.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
View user's profile Send private message
keith



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

PostPosted: Wed Mar 08, 2006 11:52 pm    Post subject: Coloring - getting started Reply with quote

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
View user's profile Send private message
TKiel



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

PostPosted: Thu Mar 09, 2006 12:57 am    Post subject: Reply with quote

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
View user's profile Send private message
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