The New Sudoku Players' Forum

[re'born]

What am I missing? Am I allowed to work right to left as well? That is can I write:
{9 3} - {3 7} - {7 9} - {9 8 (7#6)} - {8 7 (9#3)} - {7 9}

No, this is not an xyt-chain. 9#3 in cell 5 is OK, but 7#6 is not allowed in cell 4. If this is the pattern you use in your elimination, I'm very curious to know how you can justify it without Hinges.

Thank you for clarifying. The justification for adding the 7 is quite simple (once you grasp subset counting). Without the 7, one can at most put two 7's in the six cells. Adding the 7 to r3c9 does not change this.

The pattern for an xyt-chain of length 6 is:
{1 2} - {2 3} - {3 4 (2#1)} - {4 5 (2#1)(3#2)} - {5 6 (2#1)(3#2)(4#3)} - {6 1 (2#1)(3#2) (4#3) (5#4)},
from which you see that you can only work from left to right.

So it seems that your xyt-chains are slightly more restrictive than what I'm trying to get at.

It may be the case that one will prove some day that a known technique subsumes (i.e. is more general than) xyt-chains, but this has not yet been done and, as long as this hypothetical technique is more complex than xyt-chains, I don't think it will be a sufficient reason for forgetting about xyt-chains.

Without understanding xyt-chains I only say this as speculation, but I think that a technique that subsumes xyt-chains is subset counting. aeb's extended subset principle gives a very short proof of what I do in my thread and it extends quite easily to xy-chains (discontinuous or continuous) with repeated links.

I don't know if subset counting subsumes xyt-chains, but, if such was the case, you'd still have to show that it is not more complex if you want to have it replace xyt-chains.
For the player (and this is the Players Forum), more general very rarely means better.

As evidenced by my other posts, I have no desire to replace xyt-chains. As has been known around here for some time, although the principles of subset counting are ALS are easy to understand, spotting times when they apply is drastically more difficult. Any pattern that can help me find more, I am very happy to study, use and promote.

[ronk]

r9c2-9-r9c7-6-r8c8-7-{ALS:r8c23}-9-r9c2, implies r9c2<>9

ALS are not in general simpler than xyt-chains, even though the present case is comparable.

I agree that use of one or more ALSs is not always an alternative to your xyt-chain but when it is, it's just as simple IMO.

IMO you'll need to point to a better example.

I don't miss examples.
How do you eliminate 3 from R5C1 in the following: ...

Because the ALS is in two boxes instead of one it's a little trickier, but otherwise it's the same as the prior example -- one ALS (set A) and two bivalues.

Code: Select all

 269   7     8     | 4     3569  569   | 23    1     359
 4     569   2569  | 7     3569  1     | 238   359   3589
 1     59    3     | 8     2     59    | 6     4579  4579
-------------------+-------------------+------------------
 8     1369  679   | 1359  35679 45679 | 347   3479  2
 679-3 2     4     |*39    3679  679   | 5     8     1
 5     139   79    | 1239  8     2479  | 347   3479  6
-------------------+-------------------+------------------
A237   358   1     |A25    4    A257   | 9     6     3578
 279   589   2579  | 6     1     3     | 478   457   4578
 3679  4     5679  |*59    579   8     | 1     2     357

 r5c1-3-r5c4-9-r9c4-5-{ALS:r7c46=5|3=r7c1}-3-r5c1, implies r5c1<>3

The ALS "r7c46=5|3=r7c1" notation merely means at least one of r7c46=5 and r7c1=3 must be true, which is analogous to the behavior of a bivalued cell.

[re'born]

r9c2-9-r9c7-6-r8c8-{ALS:r8c23}-9-r9c2, implies r9c2<>9

ALS are not in general simpler than xyt-chains, even though the present case is comparable.

IMO you'll need to point to a better example.

I don't miss examples.
How do you eliminate 3 from R5C1 in the following:
.784...1.
4..7.1...
1.382.6..
8.......2
.24...581
5...8...6
..1.4.96.
...613...
.4...812.

Well, one can use the ALS xz-rule:
A={2,3,5,7} on r7c146,
B={3,5,9} on r59c4
x=5
z=3
=>r5c1<>3.

[Edit: I see ronk beat me to it.]

or there is the xyt-chain
{3 9} - {9 5} - {5 2} - {2 7 (5#2)} - {7 3}

or the way I think about it you almost have an xy-chain

Code: Select all

 *--------------------------------------------------------------------*
 | 269    7      8      | 4      3569   569    | 23     1      59     |
 | 4      569    2569   | 7      3569   1      | 238    35     589    |
 | 1      59     3      | 8      2      59     | 6      47     47     |
 |----------------------+----------------------+----------------------|
 | 8      1369   679    | 1359   5679   45679  | 347    3479   2      |
 | 3679-  2      4      |*39(5)  679    679    | 5      8      1      |
 | 5      139    79     | 1239   8      2479   | 347    3479   6      |
 |----------------------+----------------------+----------------------|
 |*37(2)  358    1      |*25(79) 4     *27(5)  | 9      6      3578   |
 | 279    589    2579   | 6      1      3      | 478    457    4578   |
 | 367    4      567    |*59(2)  579    8      | 1      2      357    |
 *--------------------------------------------------------------------*


and you could

-add a 2 to either r7c1 or r9c4 (but not both)
-add a 5 to either r5c4 or r7c6 (but not both)
-add a 7 to r7c4
-add a 9 to r7c4

because none of these would change the multiplicites of these numbers in a solution.

[Edit: I deleted an extraneous addition, above]

[udosuk]

I have no interest to join in the argument among you guys, simply because I'm never a big fan of xy-chains and nice loops. People who've seen my solving would know that I mostly use ALS rules to crack hard puzzles. That said, I'd like to see what you guys can do on this puzzle posted by danlm a fortnight ago:

http://forum.enjoysudoku.com/viewtopic.php?t=5534

... which I've cracked using a very complicated generalised ALS-rule involving 3 ALSs with 2 of them having 2 degrees of freedom.

I truly hope you guys can find a more elegant nice-loop-with-ALS or xyt-chain route to work it out.

[denis_berthier]

... it obscures the fact that A is linked to B, B to C,…

No, when you filter out the multiple inferences
A-2(-2-C)(-2-D)(-2-E)(-2-F)-B
you have the link
A-2-B.
Maybe there is also a shortcut for writing (-2-C)(-2-D)(-2-E)(-2-F), i am not sure.

Well, if you have to filter the notation before you can see anything,…

[denis_berthier]

So it seems that your xyt-chains are slightly more restrictive than what I'm trying to get at.
(…)
As evidenced by my other posts, I have no desire to replace xyt-chains. As has been known around here for some time, although the principles of subset counting are ALS are easy to understand, spotting times when they apply is drastically more difficult. Any pattern that can help me find more, I am very happy to study, use and promote.

Then I think we agree. There's a price to pay for generality.

[denis_berthier]

I have no interest to join in the argument among you guys, simply because I'm never a big fan of xy-chains and nice loops. People who've seen my solving would know that I mostly use ALS rules to crack hard puzzles. That said, I'd like to see what you guys can do on this puzzle posted by danlm a fortnight ago:

http://forum.enjoysudoku.com/viewtopic.php?t=5534

... which I've cracked using a very complicated generalised ALS-rule involving 3 ALSs with 2 of them having 2 degrees of freedom.

I truly hope you guys can find a more elegant nice-loop-with-ALS or xyt-chain route to work it out.

i've just posted a partial solution, with a hidden xyt-chain (hxyt) in the thread you are mentioning.

[denis_berthier]

How do you eliminate 3 from R5C1 in the following:
.784...1.
4..7.1...
1.382.6..
8.......2
.24...581
5...8...6
..1.4.96.
...613...
.4...812.

Well, one can use the ALS xz-rule:
A={2,3,5,7} on r7c146,
B={3,5,9} on r59c4
x=5
z=3
=>r5c1<>3.

or there is the xyt-chain
{3 9} - {9 5} - {5 2} - {2 7 (5#2)} - {7 3}

That seems to be an interesting example of the simplicity of xyt-chains compared to ALS.

[ronk]

i've just posted a partial solution, with a hidden xyt-chain (hxyt) in the thread you are mentioning.

row R5 : hxyt7-cn-chain on cn-cells C4N2*, C7N2, C1N2, C3N2, C3N5, C3N9 and C3N3* with rows R5, R6, R7, R3, R8, R9 and R7
==> R5 eliminated from the cn-candidates for C4N3
i.e. 3 eliminated from the candidates for R5C4

For those who like to see pencilmarks ...

Code: Select all

   | c1    c2    c3   | c4      c5     c6    | c7    c8      c9
---+------------------+----------------------+------------------
r1 | 9     5     4    | 7       2      13    | 8     13      6
r2 | 678   3     18   | 1689    168    5     | 4     179     2
r3 | 2678  1678  128  | 13689   1368   4     | 5     1379    1379
---+------------------+----------------------+--------------------
r4 | 34    2     7    | 1345    134    9     | 6     1345    8
r5 | 348   18    138  | 23456   3467   367   | 9     23457   3457
r6 | 5     9     6    | 2348    1348   37    | 27    12347   1347
---+------------------+----------------------+--------------------
r7 | 2367  4     239  | 136     5      1367  | 27    8       79
r8 | 1     67    25   | 46      9      8     | 3     24567   457
r9 | 3678  678   3589 | 346     3467   2     | 1     45679   4579



   | c1    c2    c3   | c4      c5     c6    | c7    c8     c9
---+------------------+----------------------+--------------------
n1 | 8     35    235  | 2347    2346   17    | 9     12346   36
n2 |A37    4    A378  |*56      1      9     |A67    568     2
n3 | 4579  2    B579  | 34679-5 34569  1567  | 8     13456   356
---+------------------+----------------------+--------------------
n4 | 45    7     1    | 45689   4569   3     | 2     45689   5689
n5 | 6     1    B89   | 45      7      2     | 3     4589    589
n6 | 2379  389   6    | 235789  2359   57    | 4     89      1
---+------------------+----------------------+--------------------
n7 | 2379  389   4    | 1       59     567   | 67    235689  356789
n8 | 2359  359   2359 | 236     236    8     | 1     7       4
n9 | 1     6    B79   | 23      8      4     | 5     239     379

n3c4-5-n2c4-6-{ALS A:n2c137=6|8=n2c3}-8-{ALS B:n359c3}-5-n3c4, implies n3c4<>5

Although boxes are shown, deductions dependent upon them are not valid in cn-space.

[edit: added rc-space pencilmarks]

[daj95376]

How do you eliminate 3 from R5C1 in the following:
.784...1.
4..7.1...
1.382.6..
8.......2
.24...581
5...8...6
..1.4.96.
...613...
.4...812.

Code: Select all

[r5c1]-3-[r5c4]-9-[r9c4]-5-[r7c4]-2-[r7c6]-7-[r7c1]-3-[r5c1]
 *-----------------------------------------------------------------------*
 |  269    7      8      |  4      3569   569    |  23     1      59     |
 |  4      569    2569   |  7      3569   1      |  238    35     589    |
 |  1      59     3      |  8      2      59     |  6      47     47     |
 |-----------------------+-----------------------+-----------------------|
 |  8      1369   679    |  1359   5679   45679  |  347    3479   2      |
 |  3679   2      4      |  39     679    679    |  5      8      1      |
 |  5      139    79     |  1239   8      2479   |  347    3479   6      |
 |-----------------------+-----------------------+-----------------------|
 |  37     358    1      |  25     4      257    |  9      6      3578   |
 |  279    589    2579   |  6      1      3      |  478    457    4578   |
 |  367    4      567    |  59     579    8      |  1      2      357    |
 *-----------------------------------------------------------------------*


[Edit: removed comment and expressed chain better. (I hope)]

[ravel]

Code: Select all

*--------------------------------------------------------------------*
 | 269    7      8      | 4      3569   569    | 23     1      59     |
 | 4      569    2569   | 7      3569   1      | 238    35     589    |
 | 1      59     3      | 8      2      59     | 6      47     47     |
 |----------------------+----------------------+----------------------|
 | 8      1369   679    | 1359   5679   45679  | 347    3479   2      |
 | 3679   2      4      |*39     679    679    | 5      8      1      |
 | 5      139    79     | 1239   8      2479   | 347    3479   6      |
 |----------------------+----------------------+----------------------|
 |*37     358    1      | 25     4      25#7   | 9      6      3578   |
 | 279    589    2579   | 6      1      3      | 478    457    4578   |
 | 367    4      567    |#59    #579    8      | 1      2      357    |
 *--------------------------------------------------------------------*


When you notice the strong links for 7 and 9 in box 8, you have the "extended" xy-chain
either r7c1=3
or (r7c1=7 => r9c5=7 => r9c4=9 =>) r5c4=3
For this deduction the cells in box 8 can have all additional candidates but 7 and 9.
I never understood, why bilocation links are not allowed in xy-chains. When you study a puzzle for a while (or eventually with a marking system), you know where they are.

[re'born]

So it seems that your xyt-chains are slightly more restrictive than what I'm trying to get at.
(…)
As evidenced by my other posts, I have no desire to replace xyt-chains. As has been known around here for some time, although the principles of subset counting are ALS are easy to understand, spotting times when they apply is drastically more difficult. Any pattern that can help me find more, I am very happy to study, use and promote.

Then I think we agree. There's a price to pay for generality.

Yes, though there is sometimes a price to pay for avoiding it. For instance,

Code: Select all

   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   * |   .  79  789
   .   .   . |   .   .   . |   .   .  89
 ------------+-------------+------------
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
 ------------+-------------+------------
   .   .   . |   .   .  37 |   .   .  79
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .  39 |   .   .   .


an xyt-chain will see that r2c6<>9, but

Code: Select all

   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   * |   .  79  78
   .   .   . |   .   .   . |   .   . 789
 ------------+-------------+------------
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
 ------------+-------------+------------
   .   .   . |   .   .  37 |   .   .  79
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .  39 |   .   .   .


I don't think it will catch the same exclusion here.

[denis_berthier]

So it seems that your xyt-chains are slightly more restrictive than what I'm trying to get at.
(…)
As evidenced by my other posts, I have no desire to replace xyt-chains. As has been known around here for some time, although the principles of subset counting are ALS are easy to understand, spotting times when they apply is drastically more difficult. Any pattern that can help me find more, I am very happy to study, use and promote.

Then I think we agree. There's a price to pay for generality.

Yes, though there is sometimes a price to pay for avoiding it. For instance,

Code: Select all

   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   * |   .  79  789
   .   .   . |   .   .   . |   .   .  89
 ------------+-------------+------------
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
 ------------+-------------+------------
   .   .   . |   .   .  37 |   .   .  79
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .  39 |   .   .   .


an xyt-chain will see that r2c6<>9, but

Code: Select all

   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   * |   .  79  78
   .   .   . |   .   .   . |   .   . 789
 ------------+-------------+------------
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .   . |   .   .   .
 ------------+-------------+------------
   .   .   . |   .   .  37 |   .   .  79
   .   .   . |   .   .   . |   .   .   .
   .   .   . |   .   .  39 |   .   .   .


I don't think it will catch the same exclusion here.

It is the example for which I already said the 7 in R2C9 prevents the sequence from being an xyt-chain.
So what? Did I say that xyt-chains are a panacea?
The problem with such isolated (part of an) example is that it gives the illusion that finding the pattern you display is obvious. BTW, what exact general pattern are you invoking? And what is the real complexity of finding it in the full grid? Do you have a method for finding it?
If you post the real puzzle from which you got this part, I can tell you if other rules from my set apply in this case.

[gsf]

well blow me down

here is the first xyt-chain example posted by Denis, with pm grid at the main sticking point (at least for my solver):

Code: Select all

  9    4    6  |  5    1    2  |  7    3    8
  5    2    8  |  6   37   37  |  1    9    4
  1   37   37  |  8    4    9  |  2    5    6
---------------+---------------+---------------
  2    8    1  |  4   379   5  | 69   67   379
 37    5    4  | 379 2369  367 |  8    1   239
 37    6    9  |  1   237   8  |  5    4   237
---------------+---------------+---------------
  6    1    5  | 79    8    4  |  3    2   79
  8   379  37  |  2   369   1  |  4   67    5
  4   379   2  | 379   5   367 | 69    8    1


it looks like XY-cycles should make progress here but they don't

the xyt-chain hilighted by Denis can be viewed as combining two separate XY-chains, on two separate values, to form a hybrid cycle,
but my XY-cycle formulation is restricted to one value

one simple insight, ~2 years in waiting, opens up the XY-cycle method to handle the xyt-chain example and many more puzzles
that used to require contradiction chains (y-knots in my solver) to crack

the insight is: y-edges (2-edges in the monoid terminology) need not be undirected in all cases (reversible in the alternate universe)
a directed y-edge can be part of an XY-cycle as long as it is not collapsed in the process of finding active tri-cycles
(all defined in the url above)

the upshot is that this puzzle now cracks with one y-cycle (from -O -d2 output in my solver):

Code: Select all

y-cycle  1  9  3d [85]-[74]>[82]


y-cycle #1 on value (color) 9, size 3 (3 edges)

Code: Select all

[85]-[74]  (1-edge)           [85]=9 => [74]^9 and [74]=9 => [85]^9
[74]>[82]  (directed 2-edge)  [74]^9 => [82]=9
[82][85]   (3-edge)           [82]=9 <=> [85]^9 and [82]^9 <=> [85]=9


where [74]>[82] is composed of

Code: Select all

[74]^9 [79]=9 [88]=7 [83]=3 [82]=9


the y-cycle trivially collapses to a 123 tri-cycle, which yields [82]=9, after which the puzzle falls to box-line, pairs, and singles

with this insight my solver now handles 9830/10000 of Denis' sudogen0 puzzles with XY-cycles or less
3 still require guessing, 167 require y-knots (contradiction chains)

so thanks Denis for the example

[denis_berthier]

the xyt-chain hilighted by Denis can be viewed as combining two separate XY-chains, on two separate values, to form a hybrid cycle,
but my XY-cycle formulation is restricted to one value
[…]
one simple insight, ~2 years in waiting, opens up the XY-cycle method to handle the xyt-chain example and many more puzzles
that used to require contradiction chains (y-knots in my solver) to crack
so thanks Denis for the example

gsf, that's great. I'm happy that the simplest example of xyt-chains inspired you the solution to such a long quest. May the more complex ones inspire you as well!
Isn't the purpose of these forums that we build on each others advances?