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   

XY-chain - apparently I don't understand this simple concept
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Jun 10, 2008 1:43 am    Post subject: XY-chain - apparently I don't understand this simple concept Reply with quote

Code:

53..971.2.1...5.7.....1..5....541398384962517159873264..31297.5.75...92129175..36

Board position after above with 2 locked candidate eliminations:
      reduce r23c1 by <8> and reduce r1c8 by <6>
 

5+        3+        68       |46        9+        7+       |1+        48        2+
469       1+        268      |2346      38        5+       |468       7+        39
4679      246       2678     |2346      1+        468      |468       5+        39
--------- --------- --------- --------- --------- --------- --------- --------- ---------
67        26        267      |5+        4+        1+       |3+        9+        8+
3+        8+        4+       |9+        6+        2+       |5+        1+        7+
1+        5+        9+       |8+        7+        3+       |2+        6+        4+
--------- --------- --------- --------- --------- --------- --------- --------- ---------
468       46        3+       |1+        2+        9+       |7+        48        5+
48        7+        5+       |346       38        468      |9+        2+        1+
2+        9+        1+       |7+        5+        48       |48        3+        6+


xy chains - processing chain starting r3c9 <39> ending r2c5 <38> - common bit <3>
xy chains - listing xy-chain size 3 r3c9 r2c9 r2c5
xy chains - reducing r3c4 <2346> by <3>

xy chains - processing chain starting r7c2 <46> ending r1c3 <68> - common bit <6>
xy chains - listing xy-chain size 5 r7c2 r7c8 r1c8 r1c4 r1c3
xy chains - reducing r3c2 <246> by <6>

I've been working on a C++ sudoku solver in my retirement for reasons best left unsaid.

I'm starting to add some of the more sophisticated algorithms, and I thought XY-chains seemed reasonably simply to code using STL maps and storing a 2 candidate pair (A/B) as 2 entries in the map:
key (A + index of A) data (B + index of B) paired with key (B + index of B) data (A + index of A)

This allows for a simple recursive search similar to the well-known subset search. My problem is that my program has identified two XY-chains that seem correct to me. The first starting at r3c9 is exactly an XY-wing (XY-chain length 3). But, the second one starting at r7c2 results in an illegal board position, so the reduction at r3c2 of <6> is invalid, but it certainly seems to fit the definition of of eliminating the common bit of the start/end cells from any cell that is a peer/buddy of both.

What am I missing here? Unless the start position of r7c2 needs to be back-tracked to start at cell r1c8? Is that what's wrong? I thought XY-chains could have arbitrary start/stop positions and length as long as the start/stop pairs shared a common candidate?

Thanks,

Paul
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Tue Jun 10, 2008 5:35 am    Post subject: Re: XY-chain - apparently I don't understand this simple con Reply with quote

PIsaacson wrote:
What am I missing here?

Code:
53..971.2.1...5.7.....1..5....541398384962517159873264..31297.5.75...92129175..36

 *-----------------------------------------------------------*
 | 5     3     68    | 46    9     7     | 1     48    2     |
 | 469   1     268   | 2346  38    5     | 468   7     39    |
 | 4679  246   2678  | 2346  1     468   | 468   5     39    |
 |-------------------+-------------------+-------------------|
 | 67    26    267   | 5     4     1     | 3     9     8     |
 | 3     8     4     | 9     6     2     | 5     1     7     |
 | 1     5     9     | 8     7     3     | 2     6     4     |
 |-------------------+-------------------+-------------------|
 | 468   46    3     | 1     2     9     | 7     48    5     |
 | 48    7     5     | 346   38    468   | 9     2     1     |
 | 2     9     1     | 7     5     48    | 48    3     6     |
 *-----------------------------------------------------------*

There are numerous sources for explanations on how an XY-Chain works. See www.Sudopedia.org to learn more.

Code:
Example 1: viewed as two alternatives, your chain fails to draw a conclusion

[r3c9]= 3                                      => [r3c4]<>3
[r3c9]<>3 => [r3c9]=9 => [r2c9]=3 => [r2c5]= 8 => doesn't help!!!

Code:
Example 2: same problem

[r7c2]= 6                                                          => [r3c2]<>6
[r7c2]<>6 => [r7c2]=4 => [r7c8]=8 => [r1c8]=4 => [r1c4]=6 [r1c3]=8 => doesn't help!!!
Back to top
View user's profile Send private message
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Tue Jun 10, 2008 7:16 am    Post subject: Reply with quote

Thanks!

I greatly mis-interpreted the concept of a common candidate shared by the start/end cells. I assumed (incorrectly) that by linking the pairs, the shared common candidate could be excluded from any cells common to both the start/end houses. Thanks for showing me, and forcing me to re-examine the definition of XY-chain. I changed my code to trace the true/false paths and their implications. I'm rather disappointed that after all this work, when I check for how often XY-chains advance difficult puzzles, it seems like I've spent a lot of time coding something that rarely occurs after coloring. Even when I place it before coloring, it seems like a lot of wasted effort. Is there some list of the "best" in terms of bang-for-the-buck algorithms? Currently I execute
1: Naked/Hidden singles etc.
2: Row/Col/Box intersections/restrictions
3: Subsets naked/hidden
4: Fishy sets (non-finned) based on subset recursion (X-wing ...)
5: ALS sets XY-Wing XYZ-Wing ... based on subset recursion
6: XY-chains (new and improved model!)
7: Coloring - (based on X-colors instead of ultra/3d-medusa/multi)
8: Nishio
9: Trebor tabling
10: Dancing links for when all else fails

This is pretty much that same logic order I apply when I manually solve the most difficult puzzles, but with X-coloring following subsets since it seems to offer lots of bang-for-the-buck results. Since XY-chains seemed so simple to find/setup, I was disappointed that it doesn't seem to really advance that many puzzles. Any suggestions as to where to look next?

Thanks again,
Paul
Back to top
View user's profile Send private message
humble_programmer

Joined: 27 Jun 2006
Posts: 69
:
Location: Colorado Springs, USA

Items
PostPosted: Tue Jun 10, 2008 12:41 pm    Post subject: Reply with quote

How about Unique Rectangles and/or BUG/BUG-Lite (Bi-value Universal Grave)? Both of those are farily straight forward to code, although URs come with a "taint of controversy" because the logic is only valid if the puzzle is already known to have a single unique solution...
_________________
Cheers!
Humble Programmer
,,,^..^,,,
www.humble-programmer.com
Back to top
View user's profile Send private message Visit poster's website
Sisophon2001

Joined: 05 Mar 2008
Posts: 32
:
Location: Cambodia

Items
PostPosted: Tue Jun 10, 2008 1:11 pm    Post subject: Reply with quote

Hi,

I recently implemented 3d-medusa, and I also felt disappointment in how little difference it made in terms of more puzzles solved to the battery of tests I run, so I understand your disappointment with XY-Chains. But I think the issue may be in how the puzzles are generated. My generator makes too many xy-chains and forcing chains, and I find they tend to spoil the puzzle when over done. I can adjust my generator to favour the methods I want to find, (I plan to add more code to make this user configurable) so perhaps you should think about doing something like this, or at least thinking about how the generator can be used to mould the puzzles it creates.

While I have implemented more methods than you list, it seams you are more professional in your methods. I just sit down and start endlessly deep nested loops, or reinvent methods to find the shortest loop in xy-chains.

To answer your question, I think sue-de-coq is worth looking at. You will need to first study the basic methods as described in the original description, here:

http://www.sudoku.com/boards/viewtopic.php?t=2033

And then read this thread

http://www.sudoku.org.uk/SudokuThread.asp?fid=4&sid=8198&p1=1&p2=1#post1844

paying particular attention to Obiwahn posts, and finally have a look at hobiwan post here

http://www.setbb.com/phpbb/viewtopic.php?mforum=sudoku&t=1432&postdays=0&postorder=asc&start=420&mforum=sudoku

Good luck

Garvan
Back to top
View user's profile Send private message Send e-mail Visit poster's website
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Tue Jun 10, 2008 4:01 pm    Post subject: Reply with quote

PIsaacson wrote:
Is there some list of the "best" in terms of bang-for-the-buck algorithms?

Everyone has their own preferences for the hierarchy of applying techniques. However, everyone seems to agree that Singles should come first, but there are those who apply Hidden Singles before Naked Singles because they are easier to find when playing manually.

The suggestion to implement BUG+1 and (at least some) Unique Rectangles seems good. However, I would suggest that you consider Remote Pairs, Skyscrapers, and 2-String Kite. These are all easy but occur often. If you're lazy like me, then implement finned fish -- through Franken -- and it will catch these and a few others.

Still, the most bang-for-the-buck is (probably) to implement Colors and Multiple Colors.
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Jun 10, 2008 6:47 pm    Post subject: Reply with quote

daj95376 wrote:
However, I would suggest that you consider Remote Pairs, Skyscrapers, and 2-String Kite.

Isn't it so that Remote Pairs are completely covered by Simple Coloring ?
Never heard about Skyscrapers and 2-String Kite, sounds interresting, any links ? (i'm lazy too Smile )

daj95376 wrote:
Still, the most bang-for-the-buck is (probably) to implement Colors and Multiple Colors.

I've recently expanded my solver with Multiple Colors (update not available yet), and only 10 sudokus out of more than 500 could be re-leveled. I still have more than 20000 sudokus my solver can't solve with the implemented logic.

This is the order implemented in my solver:
- Hidden Single - Easy
- Naked Single - Easy
- Pointing Pair - Medium
- Box Line Reduction - Medium
- Naked/Hidden Subsets - Hard
- X-Wing - Crazy
- Swordfish - Crazy
- Multi-value X-Wing - Crazy
- Empty Rectangle - Crazy
- (X)Y-Wing - Insane
- XYZ-Wing - Insane
- Singles Chain (aka Simple Coloring) - Insane
- Multiple Colors - Insane
- Jellyfish - Kamikaze
- WXYZ-Wing - Kamikaze
- Finned X-Wing - Kamikaze
- (Extended) Aligned Pair Exclusion - Kamikaze
- (Extended) Aligned Triple Exclusion - Extreme
- XY-Chain - Extreme
- Only 1 Bifurcation - Mayhem
- Unsolveables by solvers logic - Outlaw

planned: Nice Loops - Extreme, Alternating Inference Chains - Extreme, ALS-xz - Extreme
Considering: SueDeCoq, Unique Rectangles and BUG
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Tue Jun 10, 2008 7:46 pm    Post subject: Reply with quote

Lunatic wrote:
Never heard about Skyscrapers and 2-String Kite, sounds interresting, any links ? (i'm lazy too Very Happy )

Skyscraper is a special variant of Sashimi X-Wing, 2-String-Kite is a short X-Chain in a special pattern. Links:

http://www.sudopedia.org/wiki/Skyscraper
http://www.sudopedia.org/wiki/2-String_Kite

However with the techniques you have already implemented I would not expect much progress from these two.
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Tue Jun 10, 2008 9:04 pm    Post subject: Reply with quote

hobiwan wrote:
However with the techniques you have already implemented I would not expect much progress from these two.

Thanks for the links, indeed the 2-String Kite is covered by single coloring except for the grouped version. The Skyscraper is covered by multiple coloring, but i could implement them anyway in lower levels.

Since this topic is about XY-chains:
I've noticed that i overlooked the fact that the chained candidates don't need to be a conjugate pair. Embarassed
So i'll have to rewrite my XY-chain routine. Sad
Actually, i was not satisfied with the result anyway... (to complex)
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Tue Jun 10, 2008 9:45 pm    Post subject: Reply with quote

Lunatic wrote:
daj95376 wrote:
However, I would suggest that you consider Remote Pairs, Skyscrapers, and 2-String Kite.

Isn't it so that Remote Pairs are completely covered by Simple Coloring ?
Never heard about Skyscrapers and 2-String Kite, sounds interresting, any links ? (i'm lazy too Smile )

Thinking of it, Remote Pairs will be caught by Simple Coloring, but limited to bi-value cells with the same 2 candidates. Strictly speaking you should color the two digits, but they will have the same coloring. Note: It's usually seen as particular case of an XY-Chain.

Skyscraper and 2-String Kite are special cases of Turbot fish. See http://www.sudoku.com/boards/viewtopic.php?t=3326
Note: Since you already have advanced coloring, your soft should already catch these.

Lunatic wrote:
- Multi-value X-Wing - Crazy

Never heard about this... Some pointers?

Lunatic wrote:
planned: Nice Loops - Extreme, Alternating Inference Chains - Extreme, ALS-xz - Extreme
Considering: SueDeCoq, Unique Rectangles and BUG

AFAIK Nice Loops and AIC follow the same logic, but uses different notations to represent chains/loops.

ALS-XZ should solve puzzles which you cannot solve now. Note: WXYZ-Wing and APE are particular cases of ALS-XZ...

SueDeCoq is also a particular case of ALS-XZ. It's indeed several ALS-XZ in one, allowing several eliminations in one go. Make sure you do not restrict yourself to the case initially given by Sue de Coq and read Obi-Wahn's explanations: http://www.sudoku.com/boards/viewtopic.php?p=43113#43113

URs should also solve puzzles which you cannot solve now. Most frequent/easy are UR1, UR2 and UR4. UR3 and Hidden UR are also frequent but harder. UR6 is two Hidden UR in one. UR5 is a rarity but easy to implement. Note: Sudopedia does not list all the cases. See also Mike Barker's post at player's forum:
http://www.sudoku.com/boards/viewtopic.php?p=26448#26448

BUG maybe, but I don't have it yet, since I've no idea on how to implement it. Can someone help me here?

I would suggest finned & sashimi sword & jelly. I implemented it using Ruud's method as described here:
http://www.setbb.com/sudoku/viewtopic.php?mforum=sudoku&p=5158#5158
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.
Back to top
View user's profile Send private message Visit poster's website
PIsaacson

Joined: 17 Jan 2006
Posts: 47
:
Location: Campbell, CA

Items
PostPosted: Wed Jun 11, 2008 8:54 am    Post subject: Reply with quote

I've been reading the finned fish topics and I'm wondering if I could look for finned sets using something similar to ALS and true subsets. The N cells N candidates for subsets vs N cells N+1 candidates for ALS appeals to me since I use the same recursion method for each. Currently I use subset recursion of digits/locations to locate regular X-Wing Swordfish Squirmbag patterns. Is it possible to relax my fishing to an N with N+1 digit coverage to locate finned patterns as well? If this is clear as mud, I can provide pseudo code (or actual code if anyone still uses C/C++).

I've also been examing nice loops which seems like a possible extension of my XY-wing tree walk (recursion again) algorithm. It's amazing what you can force a computer to do by simply calling yourself!

Since I'm trying to expand my manual techniques as well, finding finned fish or trying to really understand nice loops seems like a good next step.

Anyway, I want to thank all of the posters for their insights and suggestions. I'm humbled by the amount of expertise evident in these replies and this forum in general. It's like walking in the "Hall of Giants"!

Cheers all,

Paul
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Wed Jun 11, 2008 9:27 am    Post subject: Reply with quote

PIsaacson wrote:
I've been reading the finned fish topics and I'm wondering if I could look for finned sets using something similar to ALS and true subsets. The N cells N candidates for subsets vs N cells N+1 candidates for ALS appeals to me since I use the same recursion method for each.

I think I understand what you mean, but I am not sure if that is a good approach. For me, fishing is not about cells, its about houses. If you find a combination of N base houses and N different cover houses so that all candidates in the base set are part of the cover set you found a fish. If there are uncovered candidates in the base set you have a finned fish (of course you have to check for possible eliminations). If you code it that way, you can cover all varieties of fish by feeding different sets of houses to your search method. If you use bitmaps for the houses and the candidates this should work reasonably fast.

PIsaacson wrote:
I've also been examing nice loops which seems like a possible extension of my XY-wing tree walk (recursion again) algorithm. It's amazing what you can force a computer to do by simply calling yourself!

I assume that want to you start at a candidate and examine all possible links recursively until you have found a loop. I tried that, but it didn't work out. The problem is the large amount of possibilities (in one grid I found over 1 and half million possible chains - not all loops though).

An additional problem is that the number of possible chains/loops increases drastically when the number of unset cells decreases (this is due to the increasing number of strong links - less candidates means more strong links means more chains).

I had to restrict the length of the possible chains to get a fast response, which is why I switched over to Trebor's Tables not only for Forcing Chains but for Nice Loops too.
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Wed Jun 11, 2008 10:31 am    Post subject: Reply with quote

Jean-Christophe wrote:
Lunatic wrote:
- Multi-value X-Wing - Crazy

Never heard about this... Some pointers?

http://www.scanraid.com/Multivalue_X_Wing_Strategy
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Wed Jun 11, 2008 10:36 am    Post subject: Reply with quote

PIsaacson wrote:
I've been reading the finned fish topics and I'm wondering if I could look for finned sets using something similar to ALS and true subsets. The N cells N candidates for subsets vs N cells N+1 candidates for ALS appeals to me since I use the same recursion method for each. Currently I use subset recursion of digits/locations to locate regular X-Wing Swordfish Squirmbag patterns. Is it possible to relax my fishing to an N with N+1 digit coverage to locate finned patterns as well? If this is clear as mud, I can provide pseudo code (or actual code if anyone still uses C/C++).

I think I understand what you mean. I too use the very same subset finding routine for naked subsets, hidden subsets and regular fishes.

Using ALS+1 to find finned fishes might work, but you'll miss the case with 2 fins (extra cells). This case would require ALS+2 (N cells with N+2 candidates).

Ruud's algo for finned fishes is really elegant and simple. Using bitsets of 81 bits (3*32bits) for cells in houses, cells with candidate... make it easy to implement. And it's fast using bitwise arithmetic. In fact I use these bitsets for many techniques.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.
Back to top
View user's profile Send private message Visit poster's website
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Wed Jun 11, 2008 5:14 pm    Post subject: Reply with quote

Jean-Christophe wrote:
ALS-XZ should solve puzzles which you cannot solve now. Note: WXYZ-Wing and APE are particular cases of ALS-XZ...


I did some research about APE and Extended APE myself last year with THIS RESULT

And shortly before that i posted THIS as my first post on the Eureka forum, about APE & ATE. Well, i was just a newbie at that time, so a great part turned out to be kicking in open doors. Rolling Eyes
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
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 -> Programming sudoku 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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron