XY chain problem

Programs which generate, solve, and analyze Sudoku puzzles

XY chain problem

Postby Hajime » Mon May 11, 2020 2:57 pm

Method: An (naked) XYchain has bivalue cells and it has the same candidate k in the 2 endpoint cells of the chain.
Between the cells weak links are sufficient, linked cells have at least 1 candidate in common.
If that candidate k is ON in one endpoint and OFF in the other endpoint than all cells that 'see' the 2 endpoint cells can eliminate candidate k.

I want to check the puzzle below using the XYchain method
Code: Select all
 
+-----------+------------+-----------+
 |  1   8  4 |  5  79   3 |  69 67  2 |
 |  79  3  2 |  6   4   8 |  19 5  17 |
 |  579 57 6 |  2  79   1 |  4  3   8 |
 +-----------+------------+-----------+
 |  8   9  1 |  7   3   6 |  2  4   5 |
 |  2  67  5 |  9   8   4 |  36  1 37 |
 |  67  4  3 |  1   5   2 |  8  67  9 |
 +-----------+------------+-----------+
 |  56 56  8 |  3   1   9 |  7   2  4 |
 |  4   2  7 |  8   6   5 |  13  9 13 |
 |  3   1  9 |  4   2   7 |  5   8  6 |
 +-----------+------------+-----------+


Lots of bi-value cells and r3c1 has 3 candidates. The solution of the puzzle is known and r3c1 must be a 7.
But I can make a XYchain (57)r3c2-(79)r3c5-(97)r1c5-(69)r1c7-(76)r1c8-(67)r6c8-(76)r6c1.
r3c1 sees both end-cells of the chain and cannot be a 7 and so ruins the puzzle.
What is wrong here?
User avatar
Hajime
 
Posts: 1029
Joined: 20 April 2018
Location: Netherlands

Re: XY chain problem

Postby tarek » Mon May 11, 2020 3:28 pm

How did you link r1c5 with r1c7?

I think the issue could be here:
Hajime wrote:Between the cells weak links are sufficient, linked cells have at least 1 candidate in common.
you need to make sure that 3 successive cells are NOT using the same common candidate!

tarek
Last edited by tarek on Mon May 11, 2020 3:35 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 3759
Joined: 05 January 2006

Re: XY chain problem

Postby yzfwsf » Mon May 11, 2020 3:32 pm

XY-Chain:(5=7)r3c2-(7=9)r3c5-(9=7)r1c5-(7=6)r1c8-(6=7)r6c8-(7=6)r6c1-(6=5)r7c1 => r3c1<>5 r7c2<>5
yzfwsf
 
Posts: 601
Joined: 16 April 2019

Re: XY chain problem

Postby Hajime » Mon May 11, 2020 4:17 pm

tarek wrote:How did you link r1c5 with r1c7?

I think the issue could be here:
Hajime wrote:Between the cells weak links are sufficient, linked cells have at least 1 candidate in common.
you need to make sure that 3 successive cells are NOT using the same common candidate!

tarek


Aha, there is an extra rule that that 3 successive cells are NOT using the same common candidate!
Never read anything about that.
Thnx
User avatar
Hajime
 
Posts: 1029
Joined: 20 April 2018
Location: Netherlands

Re: XY chain problem

Postby Hajime » Mon May 11, 2020 4:18 pm

yzfwsf wrote:XY-Chain:(5=7)r3c2-(7=9)r3c5-(9=7)r1c5-(7=6)r1c8-(6=7)r6c8-(7=6)r6c1-(6=5)r7c1 => r3c1<>5 r7c2<>5

Your conclusion is what I want but ...
Why didn't you stop at r6c1? (the cell before your end-cell)
XY-Chain:(5=7)r3c2-(7=9)r3c5-(9=7)r1c5-(7=6)r1c8-(6=7)r6c8-(7=6)r6c1 => r3c1<>7 ??
AND you did not comply to tarek's rule about 3 successive cells not using the 7
User avatar
Hajime
 
Posts: 1029
Joined: 20 April 2018
Location: Netherlands

Re: XY chain problem

Postby tarek » Mon May 11, 2020 7:28 pm

Hi Hajime,

I said that 3 successive cells should not use the same common candidate. I didn’t say that they can’t contain the same candidate.

When you linked r3c5 to r1c5 to r1c7 you used 7 to link them successively which can’t happen.

Tarek
User avatar
tarek
 
Posts: 3759
Joined: 05 January 2006

Re: XY chain problem

Postby yzfwsf » Mon May 11, 2020 10:41 pm

Hajime wrote:Why didn't you stop at r6c1? (the cell before your end-cell)
XY-Chain:(5=7)r3c2-(7=9)r3c5-(9=7)r1c5-(7=6)r1c8-(6=7)r6c8-(7=6)r6c1 => r3c1<>7 ??
AND you did not comply to tarek's rule about 3 successive cells not using the 7

(5 = 7) r3c2 and (7 = 6) r6c1 are not in the same house, and the candidates(5 start/6 end) are not the same, so you cannot form any eliminations.
yzfwsf
 
Posts: 601
Joined: 16 April 2019

Re: XY chain problem

Postby Hajime » Wed May 13, 2020 3:06 pm

tarek wrote:When you linked r3c5 to r1c5 to r1c7 you used 7 to link them successively which can’t happen.

You mean "used 9" ? but I did not? I used 6
User avatar
Hajime
 
Posts: 1029
Joined: 20 April 2018
Location: Netherlands

Re: XY chain problem

Postby Hajime » Wed May 13, 2020 3:10 pm

yzfwsf wrote:(5 = 7) r3c2 and (7 = 6) r6c1 are not in the same house, and the candidates(5 start/6 end) are not the same, so you cannot form any eliminations.

Can XYchain not be reversed? So head/tail swapped? Than (7start/7 end)
User avatar
Hajime
 
Posts: 1029
Joined: 20 April 2018
Location: Netherlands

Re: XY chain problem

Postby tarek » Wed May 13, 2020 3:28 pm

Hajime wrote:XYchain (57)r3c2-(79)r3c5-(97)r1c5-(69)r1c7-(76)r1c8-(67)r6c8-(76)r6c1

In the 1st 3 nodes you started correctly by showing the link within the cell from left to right and then between the nodes from left to right 5 = 7 - 7 = 9 - 9 = 7 but then you go from there to - 6 = 9 - 7 = 6 - which is where the error is!
User avatar
tarek
 
Posts: 3759
Joined: 05 January 2006

Re: XY chain problem

Postby Hajime » Fri May 15, 2020 3:47 pm

Thank you tarek
Busy programming now.

Next question: is it possible during the build of an XYchain that you bump to the chain and that the on/off candidates are not in the right order in the bumped cell? So the whole chain is invalid and each first candidate per chain cell is invalid.?
User avatar
Hajime
 
Posts: 1029
Joined: 20 April 2018
Location: Netherlands

Re: XY chain problem

Postby nedBlake » Fri May 15, 2020 4:20 pm

Yesterday I happened to see this post while I was updating the post "Sudoku Fundamentals V3" quite close to it. The "XY chain" caught my eye. When I looked at, I thought I can use it to test a couple of my new V3 features. Namely the ability to import a text-graphic of a puzzle containing both solutions and candidates, and the visual aid that lets you draw chains. I had to show it off below.

The following has to do with what is wrong with this XY puzzle. I didn't look at all the answers, so probably the following is redundant.

When I was planning the chain visual aid, I wanted to avoid as much as possible different coding for each of the chain types. I decided that all useful chains have one thing in common, namely that they strongly linked their end points: One endpoint not being a solution implies that the other endpoint is a solution.

This implies that the chain must begin with a strong link and end with a strong link. And it also implies that every other link must be a strong link, in order to carry the implication through to the other end that it is a solution. You can see this is true if you look at any of the common chains, such as Y wing and X chains etc.

Given the above, I was able to use the same code for all the chain types, except for the code necessary to select the next link in a chain, which greatly simplified the coding.

I assumed this XY chain must begin with a naked pair, which from the description meant the first candidate was a 5. I didn't realize that the author was assuming it was the 7. But whether it is a proper XY chain or not, I did check to see if it had alternating chain types. And it did, but what keeps it from being a proper chain is that the first link is weak, because there are three 7's in the 3rd row.

The chain shown below begins with the 5 and ends with a 7. The 7 in r3c2 is a hit and can be eliminated because it sees the 5 in the beginning cell (it's in the same cell) and the 7 at the end of the chain (it's in the same column).

cropped XYchain.png
XY Chain Corrected
cropped XYchain.png (145.97 KiB) Viewed 431 times
nedBlake
2018 Supporter
 
Posts: 36
Joined: 08 May 2016
Location: New Bern, North Caroline

Re: XY chain problem

Postby Hajime » Fri May 15, 2020 6:37 pm

Nice chain length 7. Just like yzfwsf, other XYchain though. Actually a green 7 in r3c5 and a red 7 in r5c3 causes the 7 in r3c2 to be eliminated. The 5 is just superfluous (and the solution of the cell).
I have some unanswered questions in this topic. If you can answer them, I would be happy.
User avatar
Hajime
 
Posts: 1029
Joined: 20 April 2018
Location: Netherlands

Re: XY chain problem

Postby nedBlake » Sat May 16, 2020 1:16 am

Hajime, you are quite right in saying that the green 7 in r3c5 and the red 7 in r5c2 also show that the 7 can be removed.
When a new strong link is added, the code checks each subchain starting at a green entry along with the new red endpoint, to see if any candidate in the puzzle sees both of them.
It starts at the beginning of the chain, so the first "subchain" is the whole chain. So in this case that is when this hit was found. No other hits were found.
Checking all subchains each time a new endpoint is added is tedious and I think most don't do it. I made displaying hits found an option that defaults to YES. I thought some would think that it was too helpful and turn it off. I decided to leave it on myself - it's amazing what it turns up for hits.
You said you had a question. I certainly don't mind answering if I can.
nedBlake
2018 Supporter
 
Posts: 36
Joined: 08 May 2016
Location: New Bern, North Caroline

Re: XY chain problem

Postby yzfwsf » Sat May 16, 2020 2:18 am

Hajime wrote:Can XYchain not be reversed? So head/tail swapped? Than (7start/7 end)


XY-Chain:(5=7)r3c2-(7=9)r3c5-(9=7)r1c5-(7=6)r1c8-(6=7)r6c8-(7=6)r6c1-(6=5)r7c1 => r3c1<>5 r7c2<>5
xy-chain.png
xy-chain.png (35.66 KiB) Viewed 414 times



XY-Chain:(5=6)r7c1-(6=7)r6c1-(7=6)r6c8-(6=7)r1c8-(7=9)r1c5-(9=7)r3c5-(7=5)r3c2 => r3c1<>5 r7c2<>5
xy-chain_rev.png
xy-chain_rev.png (35.71 KiB) Viewed 414 times
yzfwsf
 
Posts: 601
Joined: 16 April 2019

Next

Return to Software