SudokuSolver Forum

A forum for Sudoku enthusiasts to share puzzles, techniques and software
It is currently Thu Mar 28, 2024 8:41 am

All times are UTC




Post new topic Reply to topic  [ 22 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
PostPosted: Mon Jun 02, 2008 3:44 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Mon Apr 21, 2008 10:32 am
Posts: 868
Hi Mike,
Good to see you in NON-Killer/Assassin mode. Perhaps too many victims on your conscious lately? ;)

mhparker wrote:
BTW, do we really have to switch to hidden text to discuss any of the techniques used?
Personally I do not really care, but thought it might spoil some of the fun for anyone wanting to solve theese Sudokus. Besides I was (as almost always) in a good mood and wanted to have some small fun with Matt.

mhparker wrote:
Firstly, I would advise against an over-reliance on a specific software solver, which especially applies in the case of JSudoku and advanced vanilla.
Know of any good alternatives, except SudokuSolver and SudoCue?

mhparker wrote:
But there are still some things I'm asking myself, like:
Why JSudoku places Skyscrapers so high in the default priority sequence, even above XY-Wings (for example)? I personally would expect most solvers to try XY-Wings first.
A personal choice I guess. Personally I find any Wing harder to spot than a Skyscraper or a 2-String Kite.

_________________
Quis custodiet ipsos custodes?
Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]


Top
 Profile  
Reply with quote  
PostPosted: Mon Jun 02, 2008 6:22 pm 
Offline
Expert
Expert

Joined: Sun Apr 27, 2008 10:44 am
Posts: 102
Location: Belgium
mhparker wrote:
Firstly, I would advise against an over-reliance on a specific software solver, which especially applies in the case of JSudoku and advanced vanilla. As enxio27 already pointed out somewhere on this forum, JSudoku was originally designed for solving Killers.
Correct, but vanilla techniques are also applicable to killer. I agree the ordering of some techniques may look strange for vanilla. For example I've put naked pairs and triples before intersections (locked candidates) because I find it makes more sense for killer of average difficulty which are typically solved by first determining combinations for cages yielding naked subsets and then determining the particular location of the digits in the cage. This is quite different from the way one solves vanilla sudokuy of average difficulty, where one typically focus on one digit at a time.

mhparker wrote:
Having said that, Jean-Christophe has clearly been working hard recently to iron out some of its weaknesses in this area (for example, by building in ALS-XZ, Sue de Coq, Finned X-Wing/Swordfish and Uniqueness Test solvers).
To come: 2-string kite, empty rectangle, remote pairs.

mhparker wrote:
But there are still some things I'm asking myself, like:

1.Why JSudoku places Skyscrapers so high in the default priority sequence, even above XY-Wings (for example)? I personally would expect most solvers to try XY-Wings first.
Not everybody will ever agree on a definitive sequence of techniques. I personally find it easier to spot skyscrapers than XY-Wings. Udosuk has no problems spotting naked quints, but find it hard to spot hidden pairs. Børge find 2 string kite easier to spot than skyscraper... That's why you may reorder the techniques to match your personal taste.

mhparker wrote:
2. I note that some Skyscrapers found by JSudoku are based on conjugate pairs all the way round (i.e. strong link used as weak link in the middle). AFAIAA, most vanilla solvers would report this as Simple Coloring.
There is no coloring at all in JSudoku, mainly because the UI was not designed with coloring in mind... JSudoku uses chains made of strong and weak links. AFAIK it yields the same eliminations as coloring, but using another method/paradigm. I could add some coloring, but the more techniques I add, the slower it will get. JSudoku already look too much "bloatware" for my taste...

mhparker wrote:
Lastly, how does one reset the solver sequence to default in JSudoku (I'm using version 1.3b1). I naiively expected to find something like a "Restore defaults" option on the context menu for the solver page.
It's now available in v. 1.3b2. It's in contextual menu for the solver page.

_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.


Top
 Profile  
Reply with quote  
PostPosted: Mon Jun 02, 2008 6:44 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Mon Apr 21, 2008 10:32 am
Posts: 868
Jean-Christophe wrote:
To come: 2-string kite, empty rectangle, remote pairs.
Thanks :santa:-Jean-Christophe :applause: :bouncy:

Jean-Christophe wrote:
Udosuk has no problems spotting naked quints, but find it hard to spot hidden pairs.
I also find spotting any Naked Subset easier than any Hidden Subset.

_________________
Quis custodiet ipsos custodes?
Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]


Top
 Profile  
Reply with quote  
PostPosted: Mon Jun 02, 2008 8:31 pm 
Offline
Expert
Expert

Joined: Mon Apr 21, 2008 6:23 am
Posts: 113
Location: Germany
I wrote:
What's a "Strong Wing"?

udosuk wrote:
Here is the link to the forum discussion I recently started:

Thanks for the link, Matt. Very interesting concept you introduced there! As far as I can see, Strong Wings seem to be the direct inverse of XY-Wings. With XY-Wing, all external (inter-cell) links are weak, and all internal (intra-cell) links are strong. In the case of Strong Wings, the roles are reversed: all external links being strong, and all internal links being weak (the latter implying that the cells involved may have more than 2 candidates, making the move harder to spot...). I wonder how often they crop up in practice?

Børge wrote:
Good to see you in NON-Killer/Assassin mode. Perhaps too many victims on your conscious lately?

Thanks for the welcome. From the response I've been getting on some of my recent puzzles, it looks like I have already killed most of my ex-victims off! :-) Just joking, of course... ;)

I wrote:
Firstly, I would advise against an over-reliance on a specific software solver, which especially applies in the case of JSudoku and advanced vanilla.

Børge wrote:
Know of any good alternatives, except SudokuSolver and SudoCue?

I personally use Andrew Stuart's online "Scanraid" Solver, which now comes with a "Grader" button. BTW, it grades the three puzzles you posted at the start of this thread as follows:

  1. Tough, 157
  2. Diabolical, 186
  3. Diabolical, 349

By contrast, the "current" (February 17!) Daily Nightmare over at sudocue.net grades as Extreme, 851.

Jean-Christophe wrote:
To come: 2-string kite, empty rectangle, remote pairs.

Sounds good! BTW, what about Aligned Pair Exclusion?

_________________
Cheers,
Mike


Top
 Profile  
Reply with quote  
PostPosted: Tue Jun 03, 2008 8:37 am 
Offline
Expert
Expert

Joined: Mon Apr 21, 2008 6:23 am
Posts: 113
Location: Germany
Jean-Christophe wrote:
There is no coloring at all in JSudoku, mainly because the UI was not designed with coloring in mind... JSudoku uses chains made of strong and weak links. AFAIK it yields the same eliminations as coloring, but using another method/paradigm.

Had another think about this and (now) agree with you. It indeed appears that the eliminations obtained from both Simple Coloring and Multi-Coloring (types I and II) can also be achieved by using 1 or more linear X-Cycles. Simple Coloring is of course based on only strong links (conjugate pairs), whereas Multi-Coloring lifts this restriction somewhat by effectively allowing a single weak link between the two clusters involved. Clearly, neither is as flexible as an X-Cycle, which can make use of alternating strong and weak links throughout.

This seems to also be reflected in practice. I've spent some time with Andrew Stuarts Scanraid solver with various tough grids, and (whilst I've seen Simple Coloring crop up a few times) have yet to see it make use of Multi-Coloring at all! I strongly suspect that the only way I'll get it to find an example of Multi-Coloring would be to first disable the X-Cycle solver, which ranks higher in the priority sequence. (Either that, or I'll get lucky and find an example of a Multi-Coloring elimination because the equivalent X-Cycle elimination exceeds some artificial limit he's imposed for the length of his X-Cycle chains). Likewise, his solver is finding examples of Simple Coloring only because this solver has a higher priority than the X-Cycle solver.

So, I now agree with you that Coloring would not help JSudoku find any new eliminations. Of course, the same applies to the other solvers you mentioned, namely 2-String Kite (= special case of X-Cycle), Empty Rectangle (= special case of grouped X-Cycle) and Remote Pairs (= special case of XY-Chain). Incidentally, that's why I mentioned Aligned Pair Exclusion, because (although I haven't analyzed it in detail yet) I thought it may be one of the few remaining mainstream vanilla techniques that stands a chance of catching some eliminations that might currently be missed.

So, going back to Coloring, why should we use it at all? I can only think of two reasons for now:

  1. It's (at least in the case of Simple Coloring) based on a simpler concept than AICs, and thus may correspond to the paradigm some users are applying in practice.
  2. As mentioned above, eliminations found by Coloring may also be found by using 1 or more linear X-Cycles instead. It's the "or more" bit that's important here. It means that there will be some cases where coloring is more powerful (i.e., finds more eliminations in a single step). Furthermore, the remaining eliminations may be "missed" (as far as the original move is concerned), because the first X-Cycle may be already enough to allow easier moves to be applied instead for subsequent steps.

_________________
Cheers,
Mike


Top
 Profile  
Reply with quote  
PostPosted: Tue Jun 03, 2008 10:30 am 
Offline
Expert
Expert

Joined: Sun Apr 27, 2008 10:44 am
Posts: 102
Location: Belgium
mhparker wrote:
So, I now agree with you that Coloring would not help JSudoku find any new eliminations. Of course, the same applies to the other solvers you mentioned, namely 2-String Kite (= special case of X-Cycle), Empty Rectangle (= special case of grouped X-Cycle) and Remote Pairs (= special case of XY-Chain).

And Skycraper = special case of X-Cycle, finned X-Wing = special case of grouped X-Cycle.
Theese all slow down the whole solving without any real benefit, except having pretty pattern names instead of generic ones.

mhparker wrote:
Incidentally, that's why I mentioned Aligned Pair Exclusion, because (although I haven't analyzed it in detail yet) I thought it may be one of the few remaining mainstream vanilla techniques that stands a chance of catching some eliminations that might currently be missed.


Not quite true... APE are already caught by ALS-XZ as explained in Sudopedia. Same story as coloring vs turbot or X-Chains...

If I want adding some real new techniques in JSudoku, then I would go for more complex ALS: ALS-XY-Wing, ALS-XY-Chain, Death Blossom... since they're extensions to the existing chain techniques already implemented.
And maybe BUG, but I don't understand it.

_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.


Top
 Profile  
Reply with quote  
PostPosted: Tue Jun 03, 2008 6:49 pm 
Offline
Grand Master
Grand Master
User avatar

Joined: Mon Apr 21, 2008 10:32 am
Posts: 868
Jean-Christophe wrote:
mhparker wrote:
So, I now agree with you that Coloring would not help JSudoku find any new eliminations. Of course, the same applies to the other solvers you mentioned, namely 2-String Kite (= special case of X-Cycle), Empty Rectangle (= special case of grouped X-Cycle) and Remote Pairs (= special case of XY-Chain).
And Skycraper = special case of X-Cycle, finned X-Wing = special case of grouped X-Cycle.
If you take these arguments about technique A being a subset of technique B to the extreme you can AFAIK eliminate most techniques as a subset of some Chain, except General ALS, Death Blossom and Sue de Coq, i.e. you do not need Naked/Hidden Subsets, Intersections, all kinds of Fish and Wings.

Jean-Christophe wrote:
Theese all slow down the whole solving without any real benefit, except having pretty pattern names instead of generic ones.
For most cases this is correct, but try in JSudoku to move all Chain solvers to the top and solve my puzzles, except Wizard editions, and the solving generally takes longer than using my default solver sequence.
I also assume that If I turn off Skyscrapers and 2-String Kites, but let Turbot Fishes on, Skyscrapers and 2-String Kites then will be caught as TF and that the solving speed will only be marginally slower than without having solvers for Skyscrapers and 2-String Kites at all. The extra time is the IF TEST checking if the Skyscrapers respectively 2-String Kites solver should be executed.

_________________
Quis custodiet ipsos custodes?
Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]


Top
 Profile  
Reply with quote  
PostPosted: Tue Jun 03, 2008 7:39 pm 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
mhparker wrote:
What's a "Strong Wing"?
udosuk wrote:
Here is the link to the forum discussion I recently started:

Thanks for the link, Matt. Very interesting concept you introduced there! As far as I can see, Strong Wings seem to be the direct inverse of XY-Wings. With XY-Wing, all external (inter-cell) links are weak, and all internal (intra-cell) links are strong. In the case of Strong Wings, the roles are reversed: all external links being strong, and all internal links being weak (the latter implying that the cells involved may have more than 2 candidates, making the move harder to spot...). I wonder how often they crop up in practice?

Just implemented it in SudokuSolver ready for the next release and ran a batch of Ruud's Top 10,000 through. I seem to find one every 5 or 6 puzzles, so they may be quite prevalent. Each one chops about 7 or 8 steps off the solving path.

Rgds
Richard


Top
 Profile  
Reply with quote  
PostPosted: Wed Jun 04, 2008 8:46 am 
Offline
Grand Master
Grand Master
User avatar

Joined: Wed Apr 23, 2008 5:29 am
Posts: 302
Location: Sydney, Australia
Thanks Richard! :thumbs:

Although a solver which picks up chains (e.g. JSudoku) can probably spot this move one way or another, it's still desirable to have it pointed out explicitly. :ugeek:

_________________
ADYFNC HJPLI BVSM GgK Oa m


Top
 Profile  
Reply with quote  
PostPosted: Wed Jun 04, 2008 10:50 am 
Offline
Site Admin

Joined: Sun Apr 13, 2008 1:50 pm
Posts: 191
Location: London
udosuk wrote:
Thanks Richard! :thumbs:

Although a solver which picks up chains (e.g. JSudoku) can probably spot this move one way or another, it's still desirable to have it pointed out explicitly. :ugeek:
Not necessarily. I have chains in Sudokusolver for X-Cycle, X-Chain, XY-Chain and Empty Rectangle. This type of closed loop isn't covered in the other types of analysis.


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 22 posts ]  Go to page Previous  1, 2, 3  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 5 guests


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 post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group