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   

XColors & 3D Medusa

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

Joined: 19 Jul 2007
Posts: 30
:

Items
PostPosted: Thu Aug 02, 2007 3:40 pm    Post subject: XColors & 3D Medusa Reply with quote

Hi,

Is it possible to combine single-cluster 3D Medusa (or whatever you call it, I'll stick to the wiki-names) with X-Colors? For example:

0. Select conjugate pair
1. Do all SC and Medusa colorings until no further candidate can be colored.
2. Expand the cluster (if possible) with rule 3.1 of X-Colors (the Exception cells)
3. Look for contradictions, if found set all true parities etc., else scan for normal eliminations.

I'm sure this would solve more situations than single-cluster 3D Medusa alone, what do you think?

I've implemented standard X-Colors into my solver, but it's quite slow compared to all other built-in techniques, and it doesn't find as much as expected, so I want to replace it with something more powerful, or expand it.

Another question: Does dual-cluster Medusa solve considerably more situations than the single one? I'm currently testing against the top870 and other files like that and every strategy I implement only yields a few more solved puzzles. I want a not-too-complicated human-style strategy that solves plenty situations, what should I look at next? XY-Chain?

Currently my solver knows the following: naked/hidden subsets, Locked candidates, basic fish, XY-wing, XYZ-Wing, BUG+1, XColors
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Aug 02, 2007 6:12 pm    Post subject: Reply with quote

When I want to solve a sudoku quickly without too much consideration for the elegance of the solving path, I often use the combination of 3D Medusa with X-Colors (or Weak Coloring as David Bird calls it).

It it probably faster and more effective than multi-cluster 3D coloring, but almost impossible to explain, because it's a very iterative process.

Ruud
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
whizter

Joined: 19 Jul 2007
Posts: 30
:

Items
PostPosted: Fri Aug 03, 2007 12:44 pm    Post subject: Reply with quote

Now I've implemented the single-cluster 3D Medusa strategy (which was quite a PITA btw, finally I did the colorings recursively), and interestingly if I only activate Medusa and no XColors I get fewer solved Grids than with XColors alone. But if I combine them, it's more effective than any of these strategies alone. Perhaps there's a bug somewhere in my algorithm which prevents the strategy from unfolding it's whole capabilities, but I don't have the time to recheck every single grid manually with sudocue for example. How do you verify your solver-results?

EDIT:

Here your Solver log says:
"All candidates which can see both colors of this cluster can be eliminated."

My solver does this:
"2 colors appear in a single multivalued cell. The uncolored candidates can be eliminated."

I think your rule is the same as mine? The output is a little bit misleading.

Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Aug 03, 2007 7:17 pm    Post subject: Reply with quote

It is the same ... and more. I'm using the abstract term "can see both colors of a cluster", because they do not need to be other candidates in the same cell.

A target candidate can "see" another candidate in 2 ways:
1. Another candidate in the same cell.
2. Another candidate for the same digit in the same row, column or box.

Also, I'm not limiting the effects of 3DMC to a single elimination. There could be multiple targets, each with a different "specific" situation. I like my hints to fit on a single line.

Ruud
Back to top
View user's profile Send private message 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