The New Sudoku Players' Forum

by **Bud** » Thu Mar 19, 2009 11:58 pm

This thread is about expanding XY-Chains into more complex solving patterns. This post focuse on using a 4 cell XY-chain pattern to derive not only WXYZ-Wing patterns but aalternate patterns that are even more powerful. The root XY-chain is shown in the diagram below. The key to expanding this pattern is the fact that the wxyz cells in row 3 can be combined into an ALS, and the pattern becomes an ALS-XZ with common restricted digit w and common digit Z. Thus any ALS digit except W can be added to the cells in row 3 without changing the fact that it is still an ALS.

Root XY-Chain

Code: Select all: |-----------------+-----------------+-----------------| | . . . | . . . | . . . | | . . . | . wz . | * * * | | . . . | * * wx | xy . yz | |-----------------+-----------------+-----------------| | . , , | . . . | . . . | | . . , | . . . | . . . | | . . . | . . . | , . . | |-----------------+-----------------+-----------------| | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | |-----------------+-----------------+-----------------|

If I add yz to r3c6 as shown in the diagram below, the resultant pattern is that of a WXYZ-Wing and some of the call eliminations are lost.

WXYX-Wing

Code: Select all: |-----------------+-----------------+-----------------| | . . . | . . . | . . . | | . . . | . wz . | . . . | | . . . | * * wxyz | xy . yz | |-----------------+-----------------+-----------------| | . , , | . . . | . . . | | . . , | . . . | . . . | | . . . | . . . | , . . | |-----------------+-----------------+-----------------| | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | |-----------------+-----------------+-----------------|

On the other hand if I add digits as shown in the diagram below, it gives the same eliminations as the root XY-chain. From my experience I run into patterns like this more oten than what the WXYZ-patterns. This of course includes variations in both of these patterns.

Alternate Pattern #1

Code: Select all: |-----------------+-----------------+-----------------| | . . . | . . . | . . . | | . . . | . wz . | * * * | | . . . | * * wxy | xyz . xyz | |-----------------+-----------------+-----------------| | . , , | . . . | . . . | | . . , | . . . | . . . | | . . . | . . . | , . . | |-----------------+-----------------+-----------------| | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | |-----------------+-----------------+-----------------|

The question is should both of these patterns be considered WXYZ-Wings since both can be derived from the same XY-chain. The exact defination of a WXYZ-Wing is fuzzy

by ab » Fri Mar 20, 2009 3:14 am

I think most people would call this an ALS. If you could give some examples of generalisations to longer xy chains, then people might consider renaming them, but I think they rely on the whole chain lying in the same band - certainly in this case - so it makes sense to leave them as ALS for now :!:

by **PIsaacson** » Sat Mar 21, 2009 5:06 am

Bud,

You should probably review Denis Berthier's discussions of hxyzt chains, the predecessor of his nrczt chains.

Here's just one of the threads: http://forum.enjoysudoku.com/viewtopic.php?t=5555

His book, "The Hidden Logic of Sudoku (Second Edition)" covers hxyzt extensively, nrczt less so. He greatly expanded nrczt chains with whips/braids and I retro-fitted whips into my hxyzt engine since I had already coded it in my nrczt chains.

The solving power of hxyzt is much greater than standard xy chains, but that's an unqualified statement and I should back it up with statistics. I'll try to "dumb down" my hxyzt engine to act like standard xy chains and report the results. I limit my chains on the number of inferences/links instead of cells, so may I presume that 4 cells equates to a maximum of 8 inferences?

Cheers,
Paul

by **PIsaacson** » Sat Mar 21, 2009 5:52 am

Quick and dirty testing:

Code: Select all: Using the royle17 36628 puzzle collection ecp - 5306 unsolved in 24.299 seconds xy engine - 2697 unsolved in 26.716 seconds hxyzt engine - 178 unsolved in 28.235 seconds nice-loops engine - 228 unsolved in 72.686 seconds Using Hodoku for comparison ecp+xy - 2602 unsolved in 216.105 seconds ecp+NL - 164 unsolved in 474.125 seconds

I'm investigating why hobiwan's HoDoKu and my solver disagree on the xy counts. I've compared ecp (everything in HoDoKu selected through Jellyfish) results and we agree on those 100%. There must be some subtle difference in the XY chain processing that lets HoDoku solve an additional 95 puzzles that I'm missing. What's interesting, and I need to investigate further, is why hxyzt outperforms my nice-loops. I suspect it's due to my addition of whips and the fact that the zt promotion allows for inference branches that would otherwise be skipped/invalid in nice-loops.

by **Bud** » Sat Mar 21, 2009 8:58 pm

Hi ab & Paul
First of all I am totally ignorant of the chains that you mentioned. My main purpose for using this thread is that it has helped me identify simple ALS-XY chain patterns and I made this post because I thought it might be helpful for others who are just beginning to use these chains. Here is a simple example of a powerful 6 cell XY-chain which can be expanded into a a 5 set ALS-XY chain which is equally powerful. Note that the only digit that can be added to this chain is x since all of the other digits are restricted common.

6 cell XY-Chain

Code: Select all: |-----------------+-----------------+-----------------| | . . . | * . . | . . . | | . . . | * ux . | . . . | | . . . | * . uv | vw . . | |-----------------+-----------------+-----------------| | . , , | . * . | . . . | | . . , | yz * . | wy . . | | . . . | zx * . | , . . | |-----------------+-----------------+-----------------| | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | |-----------------+-----------------+-----------------|

Here is the expanded pattern. Note this is the simplest 5 set ALS-XY chain possible since it contains only one multicell ALS in box 5.

5 set ALS-XY-Chain

Code: Select all: |-----------------+-----------------+-----------------| | . . . | * . . | . . . | | . . . | * ux . | . . . | | . . . | * . uv | vw . . | |-----------------+-----------------+-----------------| | . , , | . * . | . . . | | . . , | yzx * . | wy . . | | . . . | zx * . | , . . | |-----------------+-----------------+-----------------| | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | |-----------------+-----------------+-----------------|

by **PIsaacson** » Sat Mar 21, 2009 10:58 pm

I used to believe that XY chains and ALS chains were significantly different until I modified the RCD rules to allow ALS chains to (mostly) duplicate XY chains, but not hxyzt chains. I am still trying to locate the final piece of the puzzle to have ALS chains fully subsume XY chains, but that's another issue.

I'm not sure I'm following your concepts here, so let me paraphrase what I think you are proposing:

1) Locate an XY chain.
2) See if you can combine cells to form larger ALSs.
3) Reconstruct it into an ALS chain.
4) ???

It's step 4 that is confusing me. If the XY chains are expanded into ALS chains that are "equally powerful", I have to ask: To what end??? Unless there are additional eliminations produced by the combining/expanding, once you have an XY chain, why go through this process at all?

On the other hand, for your examples that contain cells other than bi-values, it's not clear to me how these would be considered during XY chain discovery. Only hxyzt chains allow additional candidates that are nrc linked to either the z candidate, or any prior right hand side of a conjugate pair. The preceding sentence only makes sense if you understand Denis' zt concepts. Regardless, your prior examples don't admit to zt analysis, but they do construct nicely into simple ALS chains.

I would have described your prior examples with the following 2 ALS chains:

For your first set of examples:
r2c5 {wz} -w- r3c679 {wxyz} => r2c789 <> z, r3c45 <> z

The WXYX-Wing contains z in r3c6 which precludes r2c789 <> z

For your second set of examples:
b2x59 {uvx} -v- r35c7 {vwy} -y- r56c4 {xyz} => r123c4 <> x, r456c5 <> x

If that's your intention, then I "get it", but you might want to clarify and expand your process of combining into larger ALSs.

by **Bud** » Sun Mar 22, 2009 3:27 am

Paul,
I don't add digits to a puzzle. I add digits to a diagram to find simple ALS-XZ patterns and then I look for and find these patterns in puzzles. In the case of the ALS-XY-Chains I look for patterns which are almost XY-chains which are already in the puzzle. Let me demonstrate on the actual puzzle
below. Note the 5 cells in the grid marked by an asterisk. If the 3 in r7c1 were not there these cells would be an XY-chain which would eliminate 3 from r8c5. Since these cells are only in 2 columns, it is better to group all of the cells in column 1 into a 1359 ALS and the cells in column 5 into a 139 ALS. This is a doubly-linked ALS-XZ which is the most powerful ALS pattern. The restricted common digits are 1 and 9. In this case I can eliminate 1's from r7c39 and 3's from r1c1 and r8c5. One could say I should be able to find this pattern without finding the root XY-chain. Sometimes I can but in this case I didn't see it until I began looking for an almost XY-chain. I do not use software to find patterns simply because that wouldn't be any fun for me, but I don't have a problem with anyone else using it.

Doubly-Linked ALS-XZ Example

Code: Select all: |-----------------+-----------------+-----------------| | 1-39 5 137 | 47 8 379 | 2 6 347 | | 39* 2 6 | 457 39* 57 | 1 8 47 | | 4 37 8 | 1 6 2 | 57 357 9 | |-----------------+-----------------+-----------------| | 6 8 9 | 3 2 1 | 4 57 57 | | 7 1 2 | 6 5 4 | 3 9 8 | | 35* 34 345 | 9 7 8 | 6 1 2 | |-----------------+-----------------+-----------------| | 135* 3467-13457 | 8 13* 3567 | 9 2 -1357 | | 2 379 1357 | 57 1-39 3579 | 8 4 6 | | 8 3679 1357 | 2 4 45679 | 57 35 1357 | |-----------------+-----------------+-----------------|

The puzzle is Sudoku 9981 Extreme Book 49 #2. I used a 7 W-wing to get to this point in the puzzle.

by **ronk** » Sun Mar 22, 2009 4:58 am

Among other problems, there are two 5s in c5.

by **hobiwan** » Sun Mar 22, 2009 11:55 am

PIsaacson wrote:I limit my chains on the number of inferences/links instead of cells, so may I presume that 4 cells equates to a maximum of 8 inferences?

In an XY-Chain: 4 cells -> 7 inferences (4 within the cells, 3 between the cells). It wont make a difference though.

by **ronk** » Sun Mar 22, 2009 5:38 pm

hobiwan wrote:
PIsaacson wrote:I limit my chains on the number of inferences/links instead of cells, so may I presume that 4 cells equates to a maximum of 8 inferences?

In an XY-Chain: 4 cells -> 7 inferences (4 within the cells, 3 between the cells).

If only it were that simple. For example, is PIsaacson allowing for a continuous loop? Is he including the possibility for a useful discontinuous loop, but not counting the elimination cell?

by **Bud** » Sun Mar 22, 2009 5:42 pm

There is one more important point that I would like to make about my last example. At first glance it appears that the doubly-linked ALS-XZ gives more cell eliminations than the root XY-chain but this is not true. If 3 were missing from r7c1 then the root XY-chain would be present in the puzzle. But I can still combine the 5 cells in the pattern into a doubly-linked ALS-XZ and get the same cell eliminations. This particular XY-chain is more powerful than it looks.

Bud

by **aran** » Sun Mar 22, 2009 6:34 pm

Bud wrote:There is one more important point that I would like to make about my last example. At first glance it appears that the doubly-linked ALS-XZ gives more cell eliminations than the root XY-chain but this is not true. If 3 were missing from r7c1 then the root XY-chain would be present in the puzzle. But I can still combine the 5 cells in the pattern into a doubly-linked ALS-XZ and get the same cell eliminations. This particular XY-chain is more powerful than it looks.

Bud

Bud, I regard doubly-linked ALS as one of the most interesting objects out there.
Part of what you are saying is that under certain conditions, simple xy-chains are structured as D-L ALS's : as your effective example shows.
Those conditions might be that
1. there be 3 "arms" only
2. the first and last cells share a unit.
(but that needs more work).
So yes your chain is more powerful than it looks.

by **Bud** » Sun Mar 22, 2009 7:09 pm

Thanks again Aran
This proves that a useful pattern such as an XY-Wing can also be a more useful ALS pattern. I also am a big fan of the doubly-linked ALS-XZ and I have been finding a lot of them in my puzzles. I'd like to thank DonM for his ALS-XY tutotorial since I think this helped me a lot,

by **ronk** » Sun Mar 22, 2009 11:27 pm

Bud wrote:At first glance it appears that the doubly-linked ALS-XZ gives more cell eliminations than the root XY-chain but this is not true. If 3 were missing from r7c1 then the root XY-chain would be present in the puzzle. But I can still combine the 5 cells in the pattern into a doubly-linked ALS-XZ and get the same cell eliminations. This particular XY-chain is more powerful than it looks.

You make it sound as if the "extra power" comes from the ALS. That is just not true. The extra power comes from the continuous loop. Your example is a continuous loop even with r7c1 and r6c1 treated separately.

- r2c1 -9- r1c5 -3- r7c5 -1- r7c1 -5- r6c1 -3- r2c1 - continuous loop

by **PIsaacson** » Mon Mar 23, 2009 2:31 am

ronk wrote:If only it were that simple. For example, is PIsaacson allowing for a continuous loop? Is he including the possibility for a useful discontinuous loop, but not counting the elimination cell?

Because my XY engine is based on Denis Berthier's hxyzt chains/whips, the relationship between cells and candidate weak/strong inferences is especially fuzzy. I often find length 8 chains that involve as many as 7 cells. I just took a stab based on the initial 4 cell examples and figured that 8 sounded like a nice round number. Not very scientific -- sorry for that, my bad...

ronk wrote:The extra power comes from the continuous loop.

Being a devotee of ALS chains, I would have said, "The extra power comes from the continuous loop as well as the dual-linked ALS chain." or words to that effect (OWTTE for those who like acronyms or texting according to my tween daughter who thinks I'm like stone-age or something because I don't type with my thumbs!).

Cheers,
Paul

The New Sudoku Players' Forum

Expanded XY-Chain Patterns

Expanded XY-Chain Patterns

Expanded XY-Chain Patterns

Expanded XY-Chain Patterns

Expanded XY-Chains

Re: Expanded XY-Chains

Expanded XY-Wing Patterns

Re: Expanded XY-Chains