| View previous topic :: View next topic |
| Author |
Message |
yossarian
Joined: 29 Jan 2006
Posts: 1
|
 Posted: Sun Jan 29, 2006 2:29 am Post subject: Would USA Today run an unsolvable/multiple solution puzzle? |
 |
|
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 |
|
 |
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
|
| Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Sun Jan 29, 2006 8:54 am Post subject: |
|
|
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 |
|
|
dalf
Joined: 29 Jan 2006
Posts: 1
Location: northern Illinois
|
| Posted: Sun Jan 29, 2006 6:43 pm Post subject: USA Today 1/27/06 |
|
|
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?  |
|
| Back to top |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Sun Jan 29, 2006 7:30 pm Post subject: Here's another way to attack it. |
|
|
| 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 |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Sun Jan 29, 2006 7:33 pm Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Sun Jan 29, 2006 7:58 pm Post subject: Re: USA Today 1/27/06 |
|
|
| 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? |
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 |
|
|
Henk
Joined: 31 Jan 2006
Posts: 3
|
| Posted: Tue Jan 31, 2006 4:37 pm Post subject: |
|
|
It beat my solver allthough it supports forcing chains!  Think I have got some testing to do then.... |
|
| Back to top |
|
|
Henk
Joined: 31 Jan 2006
Posts: 3
|
| Posted: Tue Jan 31, 2006 4:51 pm Post subject: |
|
|
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 |
|
|
David Bryant
Joined: 29 Jul 2005
Posts: 559
Location: Denver, Colorado
|
| Posted: Wed Feb 01, 2006 4:45 pm Post subject: Here's what s_s meant |
|
|
| 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 |
|
|
someone_somewhere
Joined: 07 Aug 2005
Posts: 275
Location: Munich
|
| Posted: Sun Feb 05, 2006 10:54 am Post subject: |
|
|
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 |
|
|
|
|
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
