View previous topic :: View next topic |
Author |
Message |
keith
Joined: 19 Sep 2005 Posts: 3355 Location: near Detroit, Michigan, USA
|
Posted: Fri Jun 23, 2006 8:35 pm Post subject: Another interesting one |
|
|
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 |
|
|
Marty R.
Joined: 12 Feb 2006 Posts: 5770 Location: Rochester, NY, USA
|
Posted: Sun Jun 25, 2006 5:31 am Post subject: |
|
|
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 |
|
|
ravel
Joined: 21 Apr 2006 Posts: 536
|
Posted: Mon Jun 26, 2006 10:03 am Post subject: |
|
|
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
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 |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Mon Jun 26, 2006 6:49 pm Post subject: Here's a way to use the "UR"s |
|
|
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 |
|
|
Myth Jellies
Joined: 27 Jun 2006 Posts: 64
|
Posted: Tue Jun 27, 2006 4:13 am Post subject: Re: Here's a way to use the "UR"s |
|
|
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 |
|
|
ravel
Joined: 21 Apr 2006 Posts: 536
|
Posted: Tue Jun 27, 2006 7:22 am Post subject: |
|
|
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 |
|
|
Chuck B
Joined: 24 Jun 2006 Posts: 24
|
Posted: Wed Jun 28, 2006 2:58 am Post subject: |
|
|
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.
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. ) |
|
Back to top |
|
|
ravel
Joined: 21 Apr 2006 Posts: 536
|
Posted: Wed Jun 28, 2006 8:04 am Post subject: |
|
|
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 |
|
|
Chuck B
Joined: 24 Jun 2006 Posts: 24
|
Posted: Wed Jun 28, 2006 1:59 pm Post subject: |
|
|
Many thanks, ravel!
The ALS reference was an interesting read, too.
Cheers!
Chuck |
|
Back to top |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Wed Jun 28, 2006 2:59 pm Post subject: Uniquity |
|
|
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 |
|
|
ravel
Joined: 21 Apr 2006 Posts: 536
|
Posted: Wed Jun 28, 2006 6:16 pm Post subject: Re: Uniquity |
|
|
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 |
|
|
Chuck B
Joined: 24 Jun 2006 Posts: 24
|
Posted: Wed Jun 28, 2006 6:56 pm Post subject: |
|
|
Thanks for the additional info, David, and especially for that rabbit hole on "uniquity". 'Iniquity' came to my mind, too. Scary!
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 |
|
|
Marty R.
Joined: 12 Feb 2006 Posts: 5770 Location: Rochester, NY, USA
|
Posted: Wed Jun 28, 2006 10:26 pm Post subject: |
|
|
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 |
|
|
Chuck B
Joined: 24 Jun 2006 Posts: 24
|
Posted: Wed Jun 28, 2006 11:59 pm Post subject: |
|
|
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 |
|
|
keith
Joined: 19 Sep 2005 Posts: 3355 Location: near Detroit, Michigan, USA
|
Posted: Thu Jun 29, 2006 2:41 am Post subject: My Mother-In-Law |
|
|
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 |
|
|
keith
Joined: 19 Sep 2005 Posts: 3355 Location: near Detroit, Michigan, USA
|
Posted: Thu Jun 29, 2006 3:02 am Post subject: A good quote |
|
|
Quote: | I just prefer not to assume something that can be proved or disproved. |
Is there anything else? |
|
Back to top |
|
|
Chuck B
Joined: 24 Jun 2006 Posts: 24
|
|
Back to top |
|
|
Chuck B
Joined: 24 Jun 2006 Posts: 24
|
Posted: Thu Jun 29, 2006 4:44 am Post subject: Re: My Mother-In-Law |
|
|
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 |
|
|
ravel
Joined: 21 Apr 2006 Posts: 536
|
Posted: Thu Jun 29, 2006 9:30 am Post subject: |
|
|
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 |
|
|
Chuck B
Joined: 24 Jun 2006 Posts: 24
|
Posted: Thu Jun 29, 2006 2:48 pm Post subject: |
|
|
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 |
|
|
|
|
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
|