The New Sudoku Players' Forum

[filip_d]

while implementing XY-Chains in my solver, I made the horrible mistake of using Conjugate Pairs instead of DuoCells to make the links between the cells. To my amazement, this didn't result in errors but actually solved sudoku's, and quite a lot. I am using the about 50000 puzzles from the sudoku17 list as a testcase for my solver, and depending on where I apply this technique, it solves between 1000 and 3000 extra puzzles.

I know this is not a programmers forum, but I don't understand why this technique is working so that is why I am posting this question here. I have searched google, scanraid, sudopedia, this forum, ... and I couldn't find a similar technique. It is more than likely that what I am describing here was already found and simply has a different name.

So if anyone could help me by explaining what this is and how it works, I would be more than grateful.

This is how I implemented it :
- use a duocell as starting point (don't really know if that is necessary), but use only cells where at least 1 of it's candidates is part of a conjugate pair
- chain to the other cell of the conjugate pair (that cell does not have to be a duocell)
- in the other cell, switch candidates but only use candidates that are part of a conjugate pair
- keep chaining until you end up using the same candidate as you used to start the chain.

The 2 endpoints of this chain now form a remote pair (at least it looks like that)

Here are some examples :




Thanks in advance to anyone willing to take a look at this.[/img]

[Glyn]

filip_d Welcome to the forum.
What you have implemented is a more generalized technique, so some good news there . Plenty of reading on this can be found in Collection of Solving Techniques Thread.

Scroll down to Mike Barkers' post and have a look at the references on Nice Loops and AIC, that should explain everything and point the way towards further generalizations.

[daj95376]

while implementing XY-Chains in my solver, I made the horrible mistake of using Conjugate Pairs instead of DuoCells to make the links between the cells.

This is how I implemented it :
- use a duocell as starting point (don't really know if that is necessary), but use only cells where at least 1 of it's candidates is part of a conjugate pair
- chain to the other cell of the conjugate pair (that cell does not have to be a duocell)
- in the other cell, switch candidates but only use candidates that are part of a conjugate pair
- keep chaining until you end up using the same candidate as you used to start the chain.

The 2 endpoints of this chain now form a remote pair (at least it looks like that)

Welcome filip_d

There is nothing wrong with what you did. As you've shown, it does find eliminations. It's just the bilocation half of the more general nice loop bivalue/bilocation technique. (I think)

Withdrew comments because they weren't fully qualified.

Note: the ending cell of an XY-Chain does not have to see the starting cell of the XY-Chain. If it does, then it's an XY-Ring. (I think)

[filip_d]

Glyn and daj95376, thanks for the replies

at first I thought I understood what I did wrong : starting with the wrong number. If you take my first puzzle as an example and then using the remark of daj95376, the start of the chain can be rectified :
Instead of starting with a weak link on 8 from R1C1 ro R4C1, I can also start with a weak link on 3 between the same 2 cells (I notice now that my three examples al have the same starting condition: the second cell contains both candidates from the first cell, is there a pattern here?)

The chain in my first example would then become :
if R1C1 is 3 then R4C1 can't be
if R4C1 is not 3 then it can be 1 (or 3, but that 3 is not part of any confjugate pair)
if R4C1 is 1 then R3C1 can't be
if R3C1 is not 1 then it must be 2
if R3C1 is 2 then R3C5 can't be
if R3C5 is not 2 then it must be 1
if R3C5 is 1 then R9C5 can't be
if R9C5 is not 1 then it can be 8
if R9C5 is 8 then R1C5 can't be

I believe this can be written as :
[r1c1]-3-[r4c1]-1-[r3c1]-2-[r3c5]-1-[r9c5]-8-[r1c5]

but now I am unable to close the chain into a loop because there is no valid inference between R5C1 and R1C1 (I think) : if R1C5 is not 8 then it must be another one, but there is no other candidate that can close the loop

So I am still missing some pieces of the puzzle.


Now for another approach: I know that the other 8's on Row 1 can be removed, so that means that Theorem 4 was applied. For Theorem 4 to be valid, there should be 2 consecutive weak links with the same digit on that row. But this is not the case here.


Sorry for all these beginner questions, but I still don't understand why it is that removing these candidates are valid moves.

[ab]

look at r3c1. if it's 1 then r3c5 is 2 so r9c5 is 1 and r1c5 is 8
Alternatively r3c1 is 2 then r4c1 is 1 so r1c1 is 8

[Glyn]

filip_d No problem asking questions.

Firstly I am more familiar with Eureka notation so the chain you marked out in Diagram 1 would be written as:-
(8)r1c1=(8-1)r4c1=(1-2)r3c1=(2-1)r3c5=(1-8)r9c5=(8)r1c5 => r1c247<>8

As you have quoted Nice Loop notation here, this is the equivalent:

-[r1c1]=8=[r4c1]=1=[r3c1]=2=[r3c5]=1=[r9c5]=8=[r1c5]-8-[r1c1]=
For this continuous loop r1c247<>8 (by Theorem 2)
Also r4c1<>3,r9c5<>4,6,7 (by Theorem 1)

For Diagram 2 in Eureka notation
(2)r3c5=(2-1)r3c1=(1-5)r4c1=(5-2)r5c2=(2)r2c2 => r2c6,r3c1<>2
For Diagram 3 in Eureka notation
(7)r2c4=(7-9)r7c4=(9-6)r5c4=(6-9)r5c5=(9-7)r1c5=(7)r1c7 => r1c5,r2c7<>7

I leave at as an exercise to convert these to Nice loops and determine the eliminations.

Hope this helps.

[filip_d]

This helped a lot. I think I am beginning to understand nice loops. Now it is time for me to practice and then practice some more
Thanks again for the fast and accurate answers.

[daj95376]

The chain in my first example would then become :
if R1C1 is 3 then R4C1 can't be
if R4C1 is not 3 then it can be 1 (or 3, but that 3 is not part of any confjugate pair)

R4C1 can also be 8, so you've reached a dead end with two possibilities.

===== ===== ===== ===== =====

This should match or be fairly close to your first puzzle. I was unable to find an XY-Chain in it. There are many other chains -- including this very effective one.

Puzzle #1:

Code: Select all

 +--------------------------------------------------------------------------------+
 |  38      5689    35679   |  345678  45678   34567   |  3689    1       2       |
 |  4       2568    1356    |  3568    9       12      |  368     3678    3678    |
 |  12      689     3679    |  3678    12      367     |  3689    5       4       |
 |--------------------------+--------------------------+--------------------------|
 |  138     7       3459    |  2       456     34569   |  13568   3689    35689   |
 |  6       2589    1359    |  3579    57      3579    |  4       23789   135789  |
 |  23      459     3459    |  1       4567    8       |  2356    3679    35679   |
 |--------------------------+--------------------------+--------------------------|
 |  7       1       8       |  4569    2456    4569    |  2356    3469    3569    |
 |  9       46      46      |  58      3       12      |  7       28      158     |
 |  5       3       2       |  46789   14678   4679    |  168     4689    689     |
 +--------------------------------------------------------------------------------+
 # 163 eliminations remain

[r6c1]-3-[r1c1]-8-[r4c1]=8=[r5c2]=2=[r6c1] => [r6c1]<>3

Singles complete the puzzle


===== ===== ===== ===== =====

Your second puzzle is extremely similar to the first and uses identical logic in the same cells to crack it.

Puzzle #2:

Code: Select all

 +--------------------------------------------------------------------------------+
 |  35      4567    34679   |  36789   5689    356789  |  3578    1       2       |
 |  8       2567    1367    |  1367    4       23567   |  357     3579    3579    |
 |  12      57      379     |  3789    12      35789   |  3578    6       4       |
 |--------------------------+--------------------------+--------------------------|
 |  135     9       368     |  2       678     4       |  13567   3578    35678   |
 |  7       2568    168     |  3689    689     3689    |  4       2589    15689   |
 |  23      468     3468    |  5       6789    1       |  2367    3789    36789   |
 |--------------------------+--------------------------+--------------------------|
 |  9       1       5       |  4678    268     678     |  2367    3478    3678    |
 |  4       78      78      |  16      3       256     |  9       25      156     |
 |  6       3       2       |  4789    1589    5789    |  157     4578    578     |
 +--------------------------------------------------------------------------------+
 # 155 eliminations remain


[daj95376]

Congratulations, your third puzzle has an XY-Chain that cracks the puzzle. Unfortunately, it's not in the cells you marked. Check the cells marked (*) below ... and the eliminations resulting from it.

Puzzle #3:

Code: Select all

 +--------------------------------------------------------------+
 |  4     269   8     |  5     69-7  269   |  267   3     1     |
 |  27    5     1     | *67    8     3     |  267   9     4     |
 |  279   3     679   |  4     1     269   |  267   8     5     |
 |--------------------+--------------------+--------------------|
 |  6     1     5     |  3     2     7     |  9     4     8     |
 |  3     4     2     | *69   *69    8     |  5     1     7     |
 |  8     79    79    |  1     4     5     |  3     2     6     |
 |--------------------+--------------------+--------------------|
 |  1     67    4     |  69-7  3     69    |  8     5     2     |
 |  279   2679  679   |  8     5     1     |  4     67    3     |
 |  5     8     3     |  2    *67    4     |  1     67    9     |
 +--------------------------------------------------------------+
 # 38 eliminations remain

7-[r2c4]-6-[r5c4]-9-[r5c5]-6-[r9c5]-7  =>  [r1c5],[r7c4]<>7


BTW: These four cells also contain a W-Wing pattern: 7-[r2c4]-6-[r5c4]=6=[r5c5]-6-[r9c5]-7.

===== ===== ===== =====

Note: I start my XY-Chains with a cell not being a certain value -- 7-[r2c4] in this case -- and end my XY-Chains with that value being true in another cell -- [r9c5]-7 in this case.