Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Hand Medusa

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Thu Nov 24, 2005 7:37 pm    Post subject: Hand Medusa Reply with quote

I'm finally getting around to actually USING this Medusa business when hand-solving Sudoku puzzles, and I'm finding it lots of fun. Fun---I presume that is THE reason anyone solves Sudoku puzzles by hand, so I offer these insights:

When I know I'm working with a difficult puzzle, I start marking early on.
When I start marking, I generally go numerically 1-9 and then block by block. (Others may differ, I'm sure.) So I do 1s in block 1, 1s in block 2, ... 1s in block 9, 2s in block 2, ....

Now, someone in this forum pointed out that it's hard to see what I was calling "blades" or are also called "conjugate pairs" -- exactly two possible locations for a specific number in a given row, column, or block. Here's a trick I've just found incredibly useful:

1) If there are only two places for a number in a given block, instead of just marking it with a "." I mark it with a small circled number. I draw a tiny dash off the circle pointing to the other member of the pair.

2) When I'm done, I scan rows and columns and look for unnumbered or UNDASHED conjugate pairs. I write the circled number over the mark and add my pointer dash. The mark just gets absorbed into the circled mark. No erasing. Often I can see the X-wings and swordfish building at this point.

3) I also then look for cells with only two candidates. For these, I write the numbers in over the marks -- with NO circle.

So at this point I have three kinds of marks -- this is my insight --

"." these are nonchain nodes.
"n" these are just short single-cell strong chain nodes.
"(n)" these are the conjugate-pair strong chain nodes.

What's interesting is that I now have a full record of the strong chains. And it's very easy to check for locked candidates, because they are always two circled pairs in a single row or column of a single block. Very easy to spot!

Even better, when I start finding eliminations, my little pointers allow me to charge through the solution instantly setting the pairs.

When I get stuck, what I do is connect my dashes with lightly drawn curves. What I'm noticing is that it is quite satisfying to then actually SEE the chains and how they interact. I can often see that "this group over here does nothing -- it just goes along for the ride." That can help focus on the real issue -- What NON-chain marks are causing a problem? There aren't usually many of them.

It's interesting how something like

Code:

[78] .... [48]
 .          .
 .          .
[68] .... [58]


works. The set of four 8s -- a little cleared out X-wing -- acts to join any strong chains that might involve the other four digits. Really quite fascinating.

Finally, if I'm REALLY stuck, I start labeling each chain every other node with a dot. This is the parity. If two of these dots from the same chain end up in the same row or column or block, we can eliminate the entire set of that "parity" of nodes for that chain.

By the way -- I agree completely that checking for uniqueness can be a great shortcut. What a great idea!

Here's an example:

...3.486.
83..961.7
5..71832.
983641572
..78.9413
....73986
.1.43..98
4.896..31
3291876..

000304860830096107500718320983641572007809413000073986010430098408960031329187600

Code:

...|3.4|86.
83.|.96|1.7
5..|718|32.
---+---+---
983|641|572
..7|8.9|413
...|.73|986
---+---+---
.1.|43.|.98
4.8|96.|.31
329|187|6..


What would you do with this? Here's the possibilities table:

Code:

   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |   127 |    79 |    12 ||     3 |    25 |     4 ||     8 |     6 |    59
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |     8 |     3 |    24 ||    25 |     9 |     6 ||     1 |    45 |     7
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |     5 |   469 |    46 ||     7 |     1 |     8 ||     3 |     2 |    49
   |       |       |       ||       |       |       ||       |       |       
===========================||=======================||=======================
r4 |     9 |     8 |     3 ||     6 |     4 |     1 ||     5 |     7 |     2
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |    26 |    56 |     7 ||     8 |    25 |     9 ||     4 |     1 |     3
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |    12 |    45 |  1245 ||    25 |     7 |     3 ||     9 |     8 |     6
   |       |       |       ||       |       |       ||       |       |       
===========================||=======================||=======================
r7 |    67 |     1 |    56 ||     4 |     3 |    25 ||    27 |     9 |     8
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |     4 |    57 |     8 ||     9 |     6 |    25 ||    27 |     3 |     1
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |     3 |     2 |     9 ||     1 |     8 |     7 ||     6 |    45 |    45
   |       |       |       ||       |       |       ||       |       |       
-----------------------------------------------------------------------------


and here it is with the chains marked. (This isn't a logical implications table -- the letters refer to strong chains. The first chain is AaAaAa..., the second BbBb..., etc.

Code:

3 strong chains are labeled A-C, with alternating parity shown using lowercase.

   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |   127 |    79 |    12 ||     3 |    25 |     4 ||     8 |     6 |    59
   |   A B |    bB |    aA ||       |    Bb |       ||       |       |    Bb
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |     8 |     3 |    24 ||    25 |     9 |     6 ||     1 |    45 |     7
   |       |       |    Bb ||    bB |       |       ||       |    Bb |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |     5 |   469 |    46 ||     7 |     1 |     8 ||     3 |     2 |    49
   |       |   Cbb |    bB ||       |       |       ||       |       |    bB
===========================||=======================||=======================
r4 |     9 |     8 |     3 ||     6 |     4 |     1 ||     5 |     7 |     2
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |    26 |    56 |     7 ||     8 |    25 |     9 ||     4 |     1 |     3
   |    Bb |    bB |       ||       |    bB |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |    12 |    45 |  1245 ||    25 |     7 |     3 ||     9 |     8 |     6
   |    aA |    cC |  A Cb ||    Bb |       |       ||       |       |       
===========================||=======================||=======================
r7 |    67 |     1 |    56 ||     4 |     3 |    25 ||    27 |     9 |     8
   |    Bb |       |    Bb ||       |       |    Bb ||    bB |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |     4 |    57 |     8 ||     9 |     6 |    25 ||    27 |     3 |     1
   |       |    bB |       ||       |       |    bB ||    Bb |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |     3 |     2 |     9 ||     1 |     8 |     7 ||     6 |    45 |    45
   |       |       |       ||       |       |       ||       |    bB |    Bb
-----------------------------------------------------------------------------

If you connect the dots, you see that in that bottom right hand block there iis what initally appears to be two totally independent chains. But really they are all part of a huge, sprawling Chain B.

Can you see the problem? It's in r3c2. The next step is to take out BOTH of these "b" marks and, with them, EVERY "b" 'in the table. And I get to set every "C" in the table as TRUE as a bonus.

But there's more: Take a close look at r1c1 and r6c3. Here we have an "A" with both a "B" and a "b". Then "A" can't be true -- we would have to eliminate all of B and b -- an impossibility. So, we can also eliminate all "A" marks. Well, that's essentially the whole puzzle! The solution is just "aBC".

I'm showing this as a computer-generated table, but that's just because I wanted to show this in the forum. Really this is done by hand.

Cool, huh?

Caveat: This amounts to going through the "Medusa/strong only" or maybe the "Medusa+weak" and a touch of "Medusa+proof" but there are definitely puzzles that take even more than that.

Chain tables courtesy of http://www.stolaf.edu/people/hansonr/sudoku
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Nov 24, 2005 11:21 pm    Post subject: Reply with quote

when it can be done so easily by hand, then it should also be
fast by conputer !?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Fri Nov 25, 2005 11:04 am    Post subject: Reply with quote

Sure, I suppose so. Are you trying to make a specific point here? I think evidence is that there are faster methods of going about it by computer that no human would want to try because they are not fun. I mean, for instance, who wants to hand-solve a Sudoku using purely backtracking methods?

Right?

Anyway, the essence of my post is just a suggestion about a method that I'm finding works especially well for me specifically for hand-solving Sudoku puzzles. No implication for computer methods.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Nov 25, 2005 11:17 am    Post subject: Reply with quote

>Sure, I suppose so. Are you trying to make a specific point here?

just wondering whether they could speed up computer solvers
for larger sudokus and maybe QWHs

>I think evidence is that there are faster methods of going
>about it by computer

maybe they can be improved or mixed. You would probably only
do some medusa when there are no easy other strategies in sight

>that no human would want to try because they are not fun.

that depends.

>I mean, for instance, who wants to hand-solve a Sudoku
>using purely backtracking methods?

maybe those participating at sudoku-solving-contests

>Right?
>
>Anyway, the essence of my post is just a suggestion about
>a method that I'm finding works especially well for me
>specifically for hand-solving Sudoku puzzles.
>No implication for computer methods.

OK, but what do you think/estimate ? You should know it better
than me, I never tried it while you presumably spent lots of time
on implementing it.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Fri Nov 25, 2005 11:57 am    Post subject: Reply with quote

Ah, contests. That I hadn't thought about. Right -- my guess is there that the very best know how take an educated risk and to guess VERY well. I'd be interested in having someone who has won these tell us their marking method. Probably quite ingenious.

As for computer programs, I don't know. There are some people working on implementing this in C++, but since I'm sticking to JavaScript these days (because it's fun and requires no special download or trust level), I don't know how it would stack up. I'm TOLD it would be very slow and inefficient. And I think that's probably true.

Basically, I think any puzzle that goes beyond the strong/weak chain idea that can be checked out this way should be introduced for hand solvers with the warning:

You are probably going to have to guess at some point in the solution to this puzzle, because it most likely requires trial-and-error search.

My problem is that now that I KNOW that such puzzles exist, I'm worried that I might be solving one by hand! But my experience is that the ones in the papers are not even close to this level.

Be interesting to see what people think is the hardest Sudoku published in a newspaper.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Peter

Joined: 18 Dec 2005
Posts: 2
:
Location: San Diego

Items
PostPosted: Sun Dec 18, 2005 1:59 am    Post subject: to Bob Hanson [on Hand Medusa] Reply with quote

I'm just starting out on these puzzles and I like your tips page.
I spent about an hour contemplating your diagram and have some questions. In r1c1 you have:
127
A B
why don't you have any letter under the 2?
If I were trying to do what you did, I would blindly put some letter -- like D -- under the 2 and then "d" under the 2 in r1c3. Is it because there are three 2s in that block? What is the thought process?
Then why in r1c3 is an A under the 2 but in r1c5 there is a B under the 2?
~Peter
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Mon Dec 19, 2005 2:58 am    Post subject: Reply with quote

Right, the 2 isn't in a chain.

I must say, I'm quite disappointed with how these tables wrap. I'm going to try an experiment.

Code:

..........................................................................................

_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Peter

Joined: 18 Dec 2005
Posts: 2
:
Location: San Diego

Items
PostPosted: Wed Dec 21, 2005 1:29 am    Post subject: Reply with quote

I just used your method and solved a supposedly very difficult puzzle. Thank you. Evidently the idea is to draw conclusions from various pairs of suspects.
Obviously being a chemistry professor, you have an inate familiarity with chains. Carbon has 4, Nitrogen has 3, Oxygen has 2 and Hydrogen has 1. Hence, CH could combine with three more hs and create methane [CH4] or combine with another CH and create Acetylene [C2H2]. Enough of my knowledge or organic chemistry but you have an unfaur advantage.
I did note that in your example in the first post that the "4" in r2c3 has a small "b" and so does the "4" in r3c3. Would that also serve to disqualify all the small "b"s?
~Peter
The magic number is 45.
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Wed Dec 21, 2005 2:01 am    Post subject: Reply with quote

Peter,

I'm glad this worked for you. It's really quite easy to mark. I taught a friend to do this, and she started doing the "fiendish" puzzles almost instantly. (Unfair, I say!) The key then is patience and VERY careful marking.

About those "b"s. Right, one can often find more than one inconsistency. Whatever you notice first will work in this case. Any two "b"s in the same row, column, or block for the same candidate value or any two "b"s in the same cell knock out all "b"s.

Definitely a chemistry connection here. You are the first to notice, I think, that chemistry also has to do with 3D chains. I happen to think there might be quite an analogy to protein folding. But I'm still ruminating on that one.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku 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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron