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 

Another interesting one
Goto page 1, 2  Next
 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Other puzzles
View previous topic :: View next topic  
Author Message
keith



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

PostPosted: Fri Jun 23, 2006 8:35 pm    Post subject: Another interesting one Reply with quote

This one was published some time ago on another site. I still don't think I have figured it all out.
Code:

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

There is some uniqueness stuff that I (and my solver) seem to be missing. I'd appreciate any insights.

Keith
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Sun Jun 25, 2006 5:31 am    Post subject: Reply with quote

Quote:
This one was published some time ago on another site. I still don't think I have figured it all out.

I don't know that I figured it out either, but I did solve it. After the basic stuff,
things came to a big halt. There were no X-Wings, strong links and the like that I could see. There was a 57 pair in c5 (I think it was c5) that had potential to be a rectangle with three different columns, but I couldn't do anything with it due to extra 57s in those other three columns.

So I turned to my "old faithful", the forcing chain. There was a cell that looked like it had potential and the first value I tested solved the whole puzzle.

Thus, I finished it off using either logic or trial and error, depending on where you stand on that contentious issue.
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Mon Jun 26, 2006 10:03 am    Post subject: Reply with quote

Hi Keith,

with 2 strong links (turbot fish) and xy-wing i came here.
I eliminated the 5 in r3c8 because of the strong link for 4 (c7) in the UR 45 in r34c78.
Then 14 from r3c1, because of the AUR 57 in r12c14 (r3c1=1 => r3c3=6 => r3c2=4 and r3c1=4 => r3c2=6 => r3c3=1), but it did not help.

Code:
457   9    3  |  57   2   1  | 6     457   8         
157   8    2  |  57   4   6  | 159   579   3         
1457  46   16 |  9    3   8  | 145   2457  25
----------------------------------------------     
2     3    16 |  8    9   7  | 45    45    16       
48    46   9  |  1    5   2  | 78    3     67       
18    7    5  |  4    6   3  | 2     89    19 
----------------------------------------------     
3     25   4  |  6    8   9  | 57    1     257       
9     1    8  |  2    7   5  | 3     6     4         
6     25   7  |  3    1   4  | 589   2589  259 

Then i eliminated the 2 in r9c8 by contradiction:
r9c8=2 => r9c7=8 => r9c9=9 => r6c9=1
r9c8=2 => r9c7=8 => r5c7=7 => r5c9=6 => r4c9=1

For the purists the same without contradiction:
r4c9=1 => r6c9=9 => r9c9<>9 => {r9c8=9 or r9c7=9 => r9c8=8} => r9c8<>2
r6c9=1 => r4c9=6 => r5c9=7 => r5c7=8 => r9c7<>8 => r9c8<>2

This brought me here:

Code:
45    9    3  |  57   2   1  | 6     47    8         
15    8    2  |  57   4   6  | 19    79    3         
7     46   16 |  9    3   8  | 14    2     5
----------------------------------------------     
2     3    16 |  8    9   7  | 45    45    16       
48    46   9  |  1    5   2  | 78    3     67       
18    7    5  |  4    6   3  | 2     89    19 
----------------------------------------------     
3     25   4  |  6    8   9  | 57    1     27       
9     1    8  |  2    7   5  | 3     6     4         
6     25   7  |  3    1   4  | 589   589   29 

To avoid a BUG, either r9c7 or r9c8 must be 5, so r9c2=2, which solved it.
[Edit:] Oops, this is wrong, either r9c7=5 or r9c8=9, which does not help directly Sad
So e.g. i had to eliminate the 9 first to get r9c7=5:
r9c8=9 => r6c8=8 => r6c1=1 => r2c1=5 => r1c1=4 => r1c8=7 => r2c8=9
Better is this one:
r2c8=9 (=> r9c8<>9) => r2c7=1 => r3c7=4 => r4c7=5 (=> r9c7<>5)
=> r2c8=7
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Mon Jun 26, 2006 6:49 pm    Post subject: Here's a way to use the "UR"s Reply with quote

The first time through this puzzle I used several double-implication chains to complete it. The second time through I found a relatively simple way to employ the "UR"s on {5, 7} to make a deduction that solved the puzzle immediately.
Code:
457   9    3  |  57   2   1  | 6     457   8         
157   8    2  |  57   4   6  | 159   579   3         
1457  46   16 |  9    3   8  | 145   2457  25
----------------------------------------------     
2     3    16 |  8    9   7  | 45    45    16       
48    46   9  |  1    5   2  | 78    3     67       
18    7    5  |  4    6   3  | 2     89    19
----------------------------------------------     
3     25   4  |  6    8   9  | 57    1     257       
9     1    8  |  2    7   5  | 3     6     4         
6     25   7  |  3    1   4  | 589   2589  259

This is the first position that Ravel posted above. Notice that there are only two places to fit a "4" in row 1, and that there are two potential "non-unique rectangles" in r12 c148. From here I reasoned as follows.

-- Suppose that r1c1 = 4. Then we must have r2c8 = 9, to avoid the "deadly pattern" in r12 c48.

-- r2c8 = 9 ==> r6c8 = 8 ==> {2, 5} pair in r9c28 ==> r9c9 = 9

-- r9c9 = 9 ==> r6c9 = 1 ==> r4c9 = 6 ==> r4c3 = 1 ==> r3c3 = 6

But this leaves no candidates at r3c2. So r1c1 = 4 is impossible, and we must have r1c8 = 4. That's enough to crack it wide open. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Tue Jun 27, 2006 4:13 am    Post subject: Re: Here's a way to use the "UR"s Reply with quote

Code:
-457   9    3  |  57   2   1  | 6    A457   8         
 157   8    2  |  57   4   6  |C159  B579   3         
 1457 J46   16 |  9    3   8  |-145  -2457  25
 ----------------------------------------------     
 2     3    16 |  8    9   7  | 45    45    16       
H48   I46   9  |  1    5   2  | 78    3     67       
G18    7    5  |  4    6   3  | 2    F89    19
 ----------------------------------------------     
 3     25   4  |  6    8   9  | 57    1     257       
 9     1    8  |  2    7   5  | 3     6     4         
 6     25   7  |  3    1   4  |D589 E2589  259


In addition to the aforementioned UR in r12c14 which can only be avoided if r1c3 = 57, there is also this DIC/AIC based on the UR in r12c48

4[r1c8] =UR= 9[r2c8] - 9[r2c7] = 9[r9c7] - 8[r9c7] = 8[r9c8] - 8[r6c8] = 8[r6c1] - 8[r5c1] = 4[r5c1] - 4[r5c2] = 4[r3c2]. Thus either r1c8 or r3c2 or both equals 4, therefore r1c1 & r3c78 <> 4.

Heh, this is pretty much the same thing David found, only formalized.

[edit] Not sure why I took such a round-about path. I could have went from cell B straight to cell F. Oh well.


Last edited by Myth Jellies on Tue Jun 27, 2006 7:43 am; edited 1 time in total
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Tue Jun 27, 2006 7:22 am    Post subject: Reply with quote

What i find quite interesting is that David had
r2c8 = 9 ==> r6c8 = 8 ==> {2, 5} pair in r9c28 ==> r9c9 = 9
while i read from MJ's AIC
r2c8 = 9 ==> r2c7 <> 9 ==> r9c7 = 9

So r2c7=9,which solves the puzzle :)

[Edit:] Can be done even shorter:
r9c7=9 => r2c7<>9 => r2c8=9
r9c7=9 => r9c8=8 => r6c8=9
As forcing chain:
r6c8=9 => r2c8<>9 => r2c7=9
r6c8=8 => r9c7<>8 => r9c6=8 => r2c7=9
Back to top
View user's profile Send private message
Chuck B



Joined: 24 Jun 2006
Posts: 24

PostPosted: Wed Jun 28, 2006 2:58 am    Post subject: Reply with quote

This was interesting!! I'm a little quirky, I guess, but I generally prefer not to assume a priori that a puzzle has a unique solution. If it does, that'll come out in the wash. Consequently, I don't use UR's, but tend to use implication chains more, instead.

So, here was my approach:

Basic stuff yields:
Code:
 457   39    39    | 57    2     1     | 6     457   8     
 157   8     2     | 57    4     6     | 1579  579   3     
 1457  467   16    | 9     3     8     | 1457  27    257   
-------------------+-------------------+-------------------
 2     36    136   | 8     9     7     | 45    45    16   
 478   4679  69    | 1     5     2     | 789   3     679   
 178   79    5     | 4     6     3     | 2     789   179   
-------------------+-------------------+-------------------
 3     25    4     | 6     8     9     | 57    1     257   
 9     1     8     | 2     7     5     | 3     6     4     
 6     25    7     | 3     1     4     | 589   2589  259   

the chain 42->53->13 => (12) != 3, followed by more basic stuff then yields:
Code:
 457   9     3     | 57    2     1     | 6     457   8     
 157   8     2     | 57    4     6     | 1579  579   3     
 1457  46    16*   | 9     3     8     | 1457# 27    257   
-------------------+-------------------+-------------------
 2     3     16    | 8     9     7     | 45#   45    16   
 48X   46    9     | 1     5     2     | 78X   3     67   
 18*   7     5     | 4     6     3     | 2     89    19   
-------------------+-------------------+-------------------
 3     25    4     | 6     8     9     | 57#    1     257   
 9     1     8     | 2     7     5     | 3     6     4     
 6     25    7     | 3     1     4     | 589   2589  259   

The massive interdependence of several bivalent cells in rows 3, 4, 5 & 6 was intriguing - establishing one of them would force the values of several others in an implication avalanche. Wink

At this point the *'d, #'d and X'd cells caught my eye. I noticed that the bivalent cells 33 and 61 must both be '1', or else take the value of their respective alternate candidates (6 or 8, respectively). (fraternal twins?)

So what happens if they are both '1'? Well, the #'d cells in c7 would then form a naked triple that would force (57) = 8. However, (61) = 1 => (51) = 8 ?! which would contravene the 8 we just forced in (57). Therefore 33 and 61 cannot contain one, and we know that (33) = 6 and (61) = 8.

After this, the puzzle collapsed immediately.

Being relatively new at this, I'm not sure of the proper terminology for this approach. Anyway, I hope it was interesting to someone. :)

Cheers!
Chuck

P.S. in case my shorthand wasn't obvious, '57' is short for r5c7, and (57) would refer to the contents of r5c7. '!=' means 'is not equal to' (yeah, I program in C++ instead of Basic. Very Happy )
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Wed Jun 28, 2006 8:04 am    Post subject: Reply with quote

Chuck B wrote:
Being relatively new at this, I'm not sure of the proper terminology for this approach.

A common way to denote your eliminations is as ALS:
Code:
 457   9     3     | 57    2     1     | 6     457   8     
 157   8     2     | 57    4     6     | 1579  579   3     
 1457  46    16-   | 9     3     8     | 1457B 27    257   
-------------------+-------------------+-------------------
 2     3     16A   | 8     9     7     | 45B   45    16   
 48A   46A   9     | 1     5     2     | 78B   3     67   
 18    7     5     | 4     6     3     | 2     89    19   
-------------------+-------------------+-------------------
 3     25    4     | 6     8     9     | 57B    1    257   
 9     1     8     | 2     7     5     | 3     6     4     
 6     25    7     | 3     1     4     | 589   2589  259   

A={1468}, B={14578}, x=8, z=1

If 1 is not in A (r4c3<>1), 8 is locked in A to r5c1, if 1 is not in B (r3c8<>1), 8 is locked in B to r5c7. So 1 can be eliminated from r3c3.

I never found an ALS, when i directly looked for one, but always in a way similar to yours. But once familiar with it is a rather good notation.

In this forum i would write it as elimination chain:
r3c3=1 => r4c3=6 => r5c2=4 => r5c1=8
r3c3=1 => triple 457 in r347c7 => r5c7=8
Back to top
View user's profile Send private message
Chuck B



Joined: 24 Jun 2006
Posts: 24

PostPosted: Wed Jun 28, 2006 1:59 pm    Post subject: Reply with quote

Many thanks, ravel!

The ALS reference was an interesting read, too.

Cheers!
Chuck
Back to top
View user's profile Send private message
David Bryant



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

PostPosted: Wed Jun 28, 2006 2:59 pm    Post subject: Uniquity Reply with quote

Chuck B wrote:
I'm a little quirky, I guess, but I generally prefer not to assume a priori that a puzzle has a unique solution.

I feel the same way, Chuck. In case you haven't read all his posts, Keith is an expert on the "UR" techniques. Since he was looking for a way to use the "UR"s in this puzzle, I looked for a way to employ them.

The subject of "uniquity" has been extensively discussed in this forum -- you might find this post of some interest.

I would call the technique you employed a "double-implication chain." There are two chains of inference sprouting out of r3c3:

A. r3c3 = 1 ==> r4c3 = 6 ==> r5c2 = 4 ==> r5c1 = 8
B. r3c3 = 1 ==> {4, 5, 7} triplet in column 7 ==> r5c7 = 8

You can find a lot of references to "double-implication chains" in this forum by running a search on the word "constellation."

Interestingly, the value you excluded ("1" in r3c3) is the value that can be placed (at r2c1) by utilizing the unique rectangle that emerges at r12 c14. This illustrates a rule of thumb I've worked up -- if I see a "UR" and I want to solve the puzzle without assuming that there's a unique solution, a search for a forcing chain that commences with one of the cells that's conjugate to the cell whose value would be forced by the "UR" is usually fruitful. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Wed Jun 28, 2006 6:16 pm    Post subject: Re: Uniquity Reply with quote

David Bryant wrote:
... a rule of thumb ...

I suppose that this puzzle is an exception to your rule of thumb. maria45 solved it without UR (the solution with UR is trivial), but she needed 12 forcing chains, and did not eliminate the numbers killed by the UR.
Back to top
View user's profile Send private message
Chuck B



Joined: 24 Jun 2006
Posts: 24

PostPosted: Wed Jun 28, 2006 6:56 pm    Post subject: Reply with quote

Thanks for the additional info, David, and especially for that rabbit hole on "uniquity". 'Iniquity' came to my mind, too. Scary! Laughing

I''m also beginning to recognize you 'old hands' and deep thinkers here, and I certainly don't expect to contribute anything groundbreaking; at best, I'm just trying to adapt your insights into my own (fossilized?) way of thinking.

And it''s fun to reinvent a wheel or two on your own. 8)

Good stuff!

Cheers!
Chuck
Back to top
View user's profile Send private message
Marty R.



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

PostPosted: Wed Jun 28, 2006 10:26 pm    Post subject: Reply with quote

What's up with this business of not assuming uniqueness? You already know the puzzle has a unique solution, so why assume otherwise? Is this just another way of saying that you prefer to solve puzzles without using URs, or is there something that I'm missing?
Back to top
View user's profile Send private message
Chuck B



Joined: 24 Jun 2006
Posts: 24

PostPosted: Wed Jun 28, 2006 11:59 pm    Post subject: Reply with quote

Marty R. wrote:
What's up with this business of not assuming uniqueness? You already know the puzzle has a unique solution, so why assume otherwise? Is this just another way of saying that you prefer to solve puzzles without using URs, or is there something that I'm missing?


Not to be a royal PITA, but in a strict sense, I can't say that I really *know* that. Unlikely though it may be, people can conceivabley err in creating or transcribing a puzzle. So an allegation of uniqueness isn't quite a guarantee of it.

I don't mean to make a big deal of it, though, and certainly don't disparage the idea. I just prefer not to assume something that can be proved or disproved. It's an acquired character defect I blame on my math profs. ;)

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



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

PostPosted: Thu Jun 29, 2006 2:41 am    Post subject: My Mother-In-Law Reply with quote

I only came into becoming an "expert" at UR methods, because it turned out there were still solution methods to be discovered.

(And, I can only say, discovered among the people I know. This may be old hat to the Japanese. I work for General Motors. Never underestimate the Japanese.)

Anyway, I cannot understand the issue of not wanting to assume uniqueness, among people who do not want to solve non-unique puzzles. Chuck, et al: Try the following thread: http://www.sudoku.com/forums/viewtopic.php?t=3071

Trust me, no one is interested in these puzzles. I have tried to start threads which analyze puzzles with multiple solutions a few times. No one cares.

And, my Mother-In-Law? She never goes anywhere that involves a left hand turn. She can go most places, it is sometimes just much harder to get there.

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



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

PostPosted: Thu Jun 29, 2006 3:02 am    Post subject: A good quote Reply with quote

Quote:
I just prefer not to assume something that can be proved or disproved.


Is there anything else?
Back to top
View user's profile Send private message
Chuck B



Joined: 24 Jun 2006
Posts: 24

PostPosted: Thu Jun 29, 2006 3:57 am    Post subject: Re: A good quote Reply with quote

keith wrote:
Quote:
I just prefer not to assume something that can be proved or disproved.


Is there anything else?


Yes.
http://en.wikipedia.org/wiki/Entscheidungsproblem
http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorem
http://en.wikipedia.org/wiki/Alan_Turing#University_and_his_work_on_computability
Back to top
View user's profile Send private message
Chuck B



Joined: 24 Jun 2006
Posts: 24

PostPosted: Thu Jun 29, 2006 4:44 am    Post subject: Re: My Mother-In-Law Reply with quote

keith wrote:
Anyway, I cannot understand the issue of not wanting to assume uniqueness, among people who do not want to solve non-unique puzzles.


De gustibus non est disputandum, I guess; I don't understand why some people boil spinach.

In this case it's a philosophical point that only a math geek would care about, and I'll leave it at that.

'nuff from me...

Ciao!

Chuck
Back to top
View user's profile Send private message
ravel



Joined: 21 Apr 2006
Posts: 536

PostPosted: Thu Jun 29, 2006 9:30 am    Post subject: Reply with quote

Just to throw in my two cents worth:

The main reason i use uniqueness is, that it makes solving more interesting to have also this method at hand, because many elegant solutions can be found with it, where otherwise only a couple of more or less disgusting chains help.

My argument for using them is, that it is common sense that a puzzle has to be unique.

But i also can construct this argument for not using them:
What is an accepted solution for a sudoku ? I can define it as a logical way, where every step - inserting a number - is proved. Otherwise the step would be guessed and no one likes that. Now if i make a guess and it solves the puzzle, the step is logically proved, since it must be true (and all other numbers false), because there is no other solution.
Back to top
View user's profile Send private message
Chuck B



Joined: 24 Jun 2006
Posts: 24

PostPosted: Thu Jun 29, 2006 2:48 pm    Post subject: Reply with quote

Well, I was gonna button my lip but I found another $.02 in my pocket...

Some people find snails disgusting; others consider them a delicacy. "De gustibus...", as I noted earlier. Why begrudge someone his or her poison of choice? (Not to toss in a red herring here, but I've been surprised that no one has taken issue with the non-symmetry of the puzzle in the original post. )

The arguments I've seen so far seem to belie a preference for visually cued patterns. There are, however, other patterns and structures that you can play "Where's Waldo?" with. MJ's molecular method, and Bob Hanson's "Medusa graphics" in the ALS discussion open an interesting perspective. They hint at abstract geometries, if you will, in which structure lies in the logical rather than physical relationships among cells. (math side note: The analogy here is of dual spaces in functional analysis.) Whether you find that hideous or delightful depends on the vision you choose to employ. Beauty is in the (virtual) eye of the beholder, indeed.

Anyway, for some of us, Sudoku is an interesting diversion that represents a recreational instance of more generalized analysis. One of the (admittedly anal, but sometimes necessary) customs in that larger world is to make no unnecessary assumptions. It's a principle that probably seems pointless, if not downright silly, to someone unused to formal analysis. There are more things in this world, Horatio...

And, in contrast with Keith's mother-in-law, I prefer to make only left-hand turns. It gives me a better view of the scenery along the way. It is, after all, about the journey, no? Othewise, why not just hit the "solve" button? You take the high road, and I'll take the low road... If you get there first, good on ya! As for me, I need the exercise.
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
Goto page 1, 2  Next
Page 1 of 2

 
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