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 

Would USA Today run an unsolvable/multiple solution puzzle?

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



Joined: 29 Jan 2006
Posts: 1

PostPosted: Sun Jan 29, 2006 2:29 am    Post subject: Would USA Today run an unsolvable/multiple solution puzzle? Reply with quote

Hi! Love the site, first post....hope the code comes out right.

The following is USA Today's January 27th Sudoku. It's available online at this time.

r2c6 & r3c6 were the only cells I could complete.

Help me shed some light on this puzzzle, I've NEVER been this stumped by a legitimate puzzle.

Code:

+-------+-------+-------+
| . . . | . . 1 | 2 . . |
| . 3 . | . 2 4 | 5 . . |
| . 6 2 | . 5 7 | . . . |
+-------+-------+-------+
| 5 . . | . 6 . | . . 7 |
| 2 . . | . 4 . | . . 8 |
| 9 . . | . 3 . | . . 1 |
+-------+-------+-------+
| . . . | 4 . . | 1 9 . |
| . . 8 | 5 . . | . 6 . |
| . . 4 | 2 . . | . . . |
+-------+-------+-------+



Back to top
View user's profile Send private message
keith



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

PostPosted: Sun Jan 29, 2006 2:48 am    Post subject: Reply with quote

The puzzle is valid (it has a single, unique solution), but my software resorts to trial and error to solve it.

The url is

http://puzzles.usatoday.com/sudoku/index.html

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



Joined: 07 Aug 2005
Posts: 275
Location: Munich

PostPosted: Sun Jan 29, 2006 8:54 am    Post subject: Reply with quote

Hi,
This one is special ...
Code:
  . . . . . 1 2 . .
  . 3 . . 2 4 5 . .
  . 6 2 . 5 7 . . .
  5 . . . 6 . . . 7
  2 . . . 4 . . . 8
  9 . . . 3 . . . 1
  . . . 4 . . 1 9 .
  . . 8 5 . . . 6 .
  . . 4 2 . . . . .

Still the double implication technique is breaking it ...
First, just for the record:
- applying the "Row on 3x3 Block interaction" technique, you can exclude 9 from r9c5 and from r9c6.
- applying the "Column on 3x3 Block interaction" technique:
3 not in r7c3, 4 not in r1c2, 6 not in r7c3, 8 not in r1c2,
9 not in r1c2, 7 not in r9c8, 5 not in r9c8, 9 not in r3c7.
- now from a Hidden Pair 2 5 in r6c6 and r6c8:
4 not in r6c8 and 8 not in r6c6.
- a second Hidden Pair 4 8 in r4c2 and r6c2:
1 not in r4c2 and 7 not in r6c2.

Now all the standard tehcniques will (probable) not help, at least they did not for me. So, I applyed the secret weapon: "double implication chains", starting for a pair. As the first pair was in r1c2, I was successfull with digit 7 from it. I leave up to you to follow it, till you will find out that in cell r2c3 you have to set both digits: 1 and 9 - and this is a contradiction.

After excluding 7 from r1c2, we can set digit 5 in r1c2, r9c9 and r7c3.

And it's time again for the DIC (Double Implication Chains). The first pair of digits: 7 9 from cell r1c3. We have to follow both assumtions:
7 in r1c3 - which will lead us to 7 <> r7c2 and
9 in r1c3 - which will lead us also to 7 <> r7c2.
After the exclusion of 7 from r7c2, the rest is like running the last 100m of the marathon ...

hope I could help (and wake up the interest for the DIC technique),

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



Joined: 29 Jan 2006
Posts: 1
Location: northern Illinois

PostPosted: Sun Jan 29, 2006 6:43 pm    Post subject: USA Today 1/27/06 Reply with quote

I am fairly new to sudoku and this is my first post. I, like yossarian, was only able to fill in r2c6 & r3c6. Because I am new, I was not able to understand someone_ somewhere's explantion. Where can I find the meaning of the double implication technique? Wink
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Sun Jan 29, 2006 7:30 pm    Post subject: Here's another way to attack it. Reply with quote

Someone_Somewhere wrote:
- applying the "Row on 3x3 Block interaction" technique, you can exclude 9 from r9c5 and from r9c6.

I must be a little slow. I can't quite see how this works. The rest of what you said does make sense, someone.

After doing the obvious stuff I arrive at a matrix that looks like this.
Code:
 478  57    579 3689    89     1     2   3478 3469
 148   3    179  689     2     4     5    178  69
 148   6     2   389     5     7    348  1348  349
  5   48    13   189     6    289   349   234   7
  2   17   1367  179     4    59    369   35    8
  9   48    67    78     3    25    46    25    1
 367  257   57     4    78    368    1     9   235
 137 1279    8     5    179   39    347    6   234
1367 1579    4     2   1789  3689   378   38   35

What strikes me about this is the beginning of a BUG pattern in r1c2, r1c3, r7c2, and r7c3. Clearly, if the puzzle is to have a unique solution there must either be a "2" at r7c2, a "9" at r1c3, or both.

If we assume the solution is unique we can use this pattern to solve the puzzle right away.

r7c2 = 5 ==> r7c3 = 7 ==> r7c5 = 8 ==> r1c5 = 9 ==> pair {5, 7} interchangeable in r1 & r7.
r7c2 = 7 ==> r7c3 = 5 & r7c5 = 8 ==> r1c5 = 9 ==> pair {5, 7} interchangeable in r1 & r7.

So the only way there can be a unique solution is if r7c2 = 2, and this one additional value is enough to crack the rest of the puzzle wide open. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
keith



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

PostPosted: Sun Jan 29, 2006 7:33 pm    Post subject: Reply with quote

There are a number of pairs and row (column) block intersections you can use to get to this point given below: (These moves do not solve any further squares, they only reduce possibilities.)

Code:


+----------------+----------------+----------------+
| 478  57   579  | 3689 89   1    | 2    3478 3469 |
| 178  3    179  | 689  2    4    | 5    178  69   |
| 148  6    2    | 389  5    7    | 348  1348 349  |
+----------------+----------------+----------------+
| 5    48   13   | 189  6    289  | 349  234  7    |
| 2    17   1367 | 179  4    59   | 369  35   8    |
| 9    48   67   | 78   3    25   | 46   25   1    |
+----------------+----------------+----------------+
| 367  257  57   | 4    78   368  | 1    9    235  |
| 137  1279 8    | 5    179  39   | 347  6    234  |
| 1367 1579 4    | 2    179  369  | 378  38   35   |
+----------------+----------------+----------------+



Now what? Imho, you have to guess. For example, assume R9C9 is <3>. Then you can easily and quiclly follow one chain which solves Block 9, and another which goes via Row 6 to R7C3:

Code:


+----------------+----------------+----------------+
| 478  57   59   | 3689 89   1    | 2    347  469  |
| 178  3    19   | 689  2    4    | 5    17   69   |
| 148  6    2    | 389  5    7    | 38   134  49   |
+----------------+----------------+----------------+
| 5    48   13   | 189  6    289  | 39   234  7    |
| 2    1    136  | 179  4    59   | 39   35   8    |
| 9    48   7    | 8    3    25   | 6    25   1    |
+----------------+----------------+----------------+
| 367  257  5    | 4    78   368  | 1    9    5    |
| 137  179  8    | 5    179  39   | 4    6    2    |
| 16   159  4    | 2    19   69   | 7    8    3    |
+----------------+----------------+----------------+



There are now two 5's in R7, so R9C9 cannot be <3>, it must be <5> and the puzzle is solved.

Some people will object to this, but I can see no other way to solve this particular puzzle than to pick a trial value ("guess") in some square and see where it takes you.

Best wishes,

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



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

PostPosted: Sun Jan 29, 2006 7:58 pm    Post subject: Re: USA Today 1/27/06 Reply with quote

dalf wrote:
I am fairly new to sudoku and this is my first post. I, like yossarian, was only able to fill in r2c6 & r3c6. Because I am new, I was not able to understand someone_ somewhere's explantion. Where can I find the meaning of the double implication technique? Wink

You can read about the "4-star constellation" and also about the "5-star constellation" right here in this forum. Both of these are relatively simple applications of the "double-implication chain" technique.

The "double-implication chain" can arise in a couple of different forms. The simplest example is when a single cell can contain one of two values and we are able to reason that, no matter which one of those values is entered in that cell, a particular value must appear in some other cell. There's a pretty good example of that situation right here.

The form of "DIC" someone_somewhere seems to be most fond of draws on both the candidate list in each cell and on positional clues. For instance, if the only possibilities at r5c5 are (5, 7} and in addition there are only two places to put a "7" in row 5, then assuming that r5c5 = 5 not only starts a chain of implications by altering the candidate lists in row 5, in column 5, and in the middle center 3x3 box -- it also forces a "7" into the other possible spot where it can go, and that in turn has implications. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Henk



Joined: 31 Jan 2006
Posts: 3

PostPosted: Tue Jan 31, 2006 4:37 pm    Post subject: Reply with quote

It beat my solver allthough it supports forcing chains! Shocked Think I have got some testing to do then.... Wink
Back to top
View user's profile Send private message Visit poster's website
Henk



Joined: 31 Jan 2006
Posts: 3

PostPosted: Tue Jan 31, 2006 4:51 pm    Post subject: Reply with quote

someone_somewhere:
I cant follow your explanation. I got no furter then this. Is this puzzle solvable without backtracking? How?

[Editor's note: The link to this image is not working, so it has been deleted.]
Back to top
View user's profile Send private message Visit poster's website
David Bryant



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

PostPosted: Wed Feb 01, 2006 4:45 pm    Post subject: Here's what s_s meant Reply with quote

Henk wrote:
someone_somewhere:
I cant follow your explanation. I got no furter then this. Is this puzzle solvable without backtracking? How?

Hi, Henk!

Someone_Somewhere seems to be on vacation, or something. Here's an explanation.

After making the simple eliminations (row on block, hidden pairs) the puzzle looks like this.
Code:
 478  57    579 3689    89     1     2   3478 3469
 148   3    179  689     2     4     5    178  69
 148   6     2   389     5     7    348  1348  349
  5   48    13   189     6    289   349   234   7
  2   17   1367  179     4    59    369   35    8
  9   48    67    78     3    25    46    25    1
 367  257   57     4    78    368    1     9   235
 137 1279    8     5    179   39    347    6   234
1367 1579    4     2   1789  3689   378   38   35

Now Someone_Somewhere said "As the first pair was in r1c2, I was successfull with digit 7 from it. I leave up to you to follow it, till you will find out that in cell r2c3 you have to set both digits: 1 and 9 - and this is a contradiction."

Think about what will happen if you set r1c2 = 7. There are two chains of inference to follow:

A. r1c2 = 7 ==> {1, 4, 8} triplet in r1c1, r2c1, & r3c1 ==> r2c3 = 9 ("7" excluded by r1c2, "1" excluded by the triplet)

B. r1c2 = 7 ==> r5c2 = 1 ==> r4c3 = 3 ==> {6, 7} pair in r5c3 & r6c3 ==> r7c3 = 5 ==> r1c3 = 9 ==> r2c3 = 1 ("7" excluded by r1c2, "9" excluded by r1c3)

There are other ways to derive a contradiction that may seem clearer to you, Henk, but this is the contradiction s_s was talking about. Anyway, the point is that r1c2 <> 7, so we must have r1c2 = 5. Is that backtracking?

Oh -- to me, the easiest way to see this contradiction is by noticing that there are only two places to put a "5" in the top left 3x3 box. If r1c3 = 5 then r1c2 = 7, and following chain B above we see that r7c3 = 5 ... but we can't have two "5"s in column 3. So r1c3 can't be "5", and we must have r1c2 = 5.

Anyway, after we put the "5" at r1c2 and follow the implications of that move we quickly arrive at this position.
Code:
 478   5    79  3689    89     1     2   3478 3469
 148   3    179  689     2     4     5    178  69
 148   6     2   389     5     7    348  1348  349
  5   48    13   189     6    289   349   234   7
  2   17   1367  179     4    59    369   35    8
  9   48    67    78     3    25    46    25    1
 367  27     5     4    78    368    1     9   235
 137 1279    8     5    179   39    347    6   234
1367 1579    4     2   1789  3689   378   38    5

Now s_s said " ...it's time again for the DIC (Double Implication Chains). The first pair of digits: 7 9 from cell r1c3. We have to follow both assumtions: 7 in r1c3 - which will lead us to 7 <> r7c2; and 9 in r1c3 - which will lead us also to 7 <> r7c2. "

Translation: let's see what happens if we put a "7" at r1c3, and also what happens if we put a "9" at r1c3.

A. r1c3 = 7 ==> r5c2 = 7 (only spot left for a "7" in middle left 3x3 box) ==> r7c2 = 2.
B. r1c3 = 9 ==> r1c5 = 8 ==> r7c5 = 7 ==> r7c2 = 2

So no matter which value we place at r1c3 we must have r7c2 = 2, and the rest of the puzzle is straightforward. 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: Sun Feb 05, 2006 10:54 am    Post subject: Reply with quote

Thank you David. You can explain better than me.

P.S. I was in a project "on the field" in a different country, and I had no time except for sleeping and toilet. The rest was like solving Sudoku.
Now I am back.

still alive,
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