The New Sudoku Players' Forum

[surbier]

Hi,
The xyt chain seems to be one of the few methods in the 'collection of advanced solving methods' for which the corresponding thread does not provide any logical deduction or proof. I can follow the ALS logic which does the same for the particular examples as the xyt chain examples. Does anybody know how the deduction of xyt-chains work ?

Thanks in advance, surbier

[StrmCkr]

yes
there is several users on here that knows how they work,

i would recomend asking denis himself,
or your best bet is

PIsaacson
he has replicated alot of denises work...

perhaps he can show the examples your asking for.

i know bit s and pieces of that work.

i'll provide some insight best as i can....

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    3679   5   | 69  67  379  |
| 37  5    4  | 379  23679  367 | 8   1   2379 |
| 37  6    9  | 1    237    8   | 5   4   237  |
:-------------+-----------------+--------------:
| 6   1    5  | 79   8      4   | 3   2   79   |
| 8   379  37 | 2    3679   1   | 4   67  5    |
| 4   379  2  | 379  5      367 | 69  8   1    |
'-------------'-----------------'--------------'

given this grid denis mentions that the xyt-chain is:

[quote]number 9 : xyt4-chain on cells R9C7*, R8C8, R8C3 and R8C2* with numbers 9, 6, 7 and 3
==> 9 eliminated from the candidates for R9C2

which is a really ruff way of saying that there is a

Discontinuous Nice Loop r8c2 =9= r8c5 =6= r8c8 -6- r9c7 -9- r9c2 =9= r8c2 => r8c2<>3, r8c2<>7

instead of elimianting the cover digits as suggested by the loop,

denis mathmatically limits the placement of 9 to only 1 location with in the chain thus cannot be containted in r9c2.

the easiest way to see the proof for the self contained contradiction is the map the combinations of the cells out.

for example:

if
R9C7 is 9 then R9C2 <>9
|
R9C7 is 6 => R8C8 is 7 => R8C3 is 3 => R8C2 is 9 => R9C2 <>9

[aran]

Hi,
The xyt chain seems to be one of the few methods in the 'collection of advanced solving methods' for which the corresponding thread does not provide any logical deduction or proof. I can follow the ALS logic which does the same for the particular examples as the xyt chain examples. Does anybody know how the deduction of xyt-chains work ?

Thanks in advance, surbier

Surbier
I think that t in xyt is what I call (and maybe others) memory.
The idea is this : anything already placed in a developing chain can be remembered (if useful) further down the line in that chain.
Take the example which stm ckr used :
I'll put "t" beside re-used digits :
First though the chain as I would write it myself :
9r9c7=6r9c7-(6=7)r8c8-(7=3)r8c3-(37=9)r8c2 :=><9>r9c2.
Now using t
9r9c7=6r9c7-(6=7t)r8c8-(7=3)r8c3-(37t=9)r8c2 : =><9>r9c2.
In other words, it's nothing more than common sense and not an advanced technique.

[PIsaacson]

Surbier,

If you are interested in Denis Berthier's work, I highly recommend reading his book, "The Hidden Logic of Sudoku (Second Edition)". He presents his concepts in a series of well documented steps with numerous examples. I won't presume to describe the xyzt-chain in full, but some aspects of his theory involve always starting a chain from a potential CEC (the z target) and allowing z (the CEC value) and t (all prior right-hand linking candidates) candidates in a potential link of the chain to be ignored if they are nrc linked to the z/t candidates. Whew! Let's go over that again slowly.

The CEC (z target) is always the implicit start of any of Denis's chains and is assumed true. After that, the chain consists of a series of conjugate pairs (left hand and right hand linking candidates) that are strong linked within the pair, and weak linked to each other. Think of this as an AIC chain with each conjugate pair the strong linked parts. So, as the chain is developed, if you have a weak-linked conjugate pair whose excess candidates (those preventing if from being a strong linked pair) can all be "ignored" due to being nrc linked (think peers of) to either the z target or any prior true (right hand side of a conjugate pair - remember it's strong linked so the left hand is explicitly false) t candidate, then it is, in my words, "promoted" to a strong linked conjugate pair and the chain can continue to be formed.

That's about as concise and accurate as I can get. Denis has many posting on this and I recommend that you carefully read them in order to fully understand all the implications of this. One important one is that any z/t promotion precludes using the chain in a bi-directional fashion, so the usual eliminations that might result from loop formation are not permissible. The z target is a crucial element of these chains. This can be relaxed somewhat, but I'm not prepared to explain that in detail here. Suffice it to say that you can develop a chain and discover multiple resulting eliminations without having to re-discover the chain as in (from your example PM):

Code: Select all

do_xychains - reducing r5c4.<379> by <9>
do_xychains - reducing r8c5.<3679> by <9>
do_xychains - xyt-chain[5] 9=[r7c4]=7=[r7c9]=9=[r9c7]=6=[r9c6]=3=[r9c4]=9

Excuse the notation - this is really old code so read it as:
Each cell has a left-hand false condition with a right-hand true condition 9=[r7c4]=7 means if r7c4<>9 then r7c4=7

The above 2 eliminations both result from a single 5 cell xyt chain. r9c6 and r9c4 are tri-value cells that would not normally be allowed in a standard xy-chain, but in this chain r9c6 and r9c4 are t promoted because the excess {7} in each cell is covered by [r7c4]=7.

Hope this helps,
Paul

[aran]

Paul
Regarding your post :
1. it depends on whether Surbier is asking in the context of a resolution-by-rules solution to the puzzle (let's call that a computer solution, even if the term isn't quite accurate) or from a human solver's point of view (I imagine the latter but may be wrong)
2. he mentioned xyt chains and not xyzt
That established :
My own reply was in relation to xyt and not xyzt chains (which I'll come to in a minute).
In xyt and from a human solving perspective : t is just memory and it's common sense : if you have placed something in a chain it can be remembered later on subject to
i) being appropriate : ie it must be in a peer relationship : ie r1c1=7 can't be remembered in r4c4
ii) being useful : eg r1c1=7 can be remembered in r1c9 but that won't be useful if there is no 7 in r1c9.
Now xyzt :
the nuance here is that given a target CEC with z, then any z peers of zCEC can be ignored in the chain seeking to eliminate zCEC.
I'm not sure whether those zs-in-the-chain are referred to as "z" or as "t".
I rather think as "z" though.
In which case t is just memory, as described above.

I do want to underline that :
- in human solving the t concept is just "common sense"
- memory is not an advanced technique

To be noted that Denis restricts memory to a certain configurations within the puzzle in line with resolution rules etc.
The human solver isn't constricted in that way and he can use memory as he pleases.

[surbier]

Thanks all,

The idea is this : anything already placed in a developing chain can be remembered (if useful) further down the line in that chain.
Take the example which stm ckr used :

If it is ony on carrying memory, then I would understand the principle. But I think, that in a chain, the memory of already placed digits becomes only useful, when one of the folllow up nodes can 'see' one of the previously placed/assumed digit, that generates the constraint.
I thought that in a xyt-chain a node does not need to see the overnext node, only the direct neighbor. In so far the two example xyt chains in the mentioned thread (e.g. the one obove with more than 2 nodes in row 8) are slightly misleading.

The xyt-chain claims, afaik, however the chains goes around (whether it matches a constraint set by an 'earlier' link of the chain or not) the so-called right linking candidate of a previous cell does not destroy the conjugate character (the strong links) of the xy-chain and eliminations are preserved.

An xyt-chain example, where not more than two cells are in one unit would be very helpful, at least for me.

[ronk]

An xyt-chain example, where not more than two cells are in one unit would be very helpful, at least for me.

Here's a hypothetical, where an ALS won't also do the job.

Code: Select all

 .   .   .   | .   .   . 
 .   12  .   | .   .   . 
 .   .   23  | .   34  . 
-------------+------------
 .   .   135 | .   45  . 
 .   -1  .   | .   .   . 
 .   .   .   | .   .   . 

The "t-link" is r3c3 -3- r4c3.

[aran]

Code: Select all

 .   .   .   | .   .   . 
 .   12  .   | .   .   . 
 .   .   23  | .   34  . 
-------------+------------
 .   .   135 | .   45  . 
 .   -1  .   | .   .   . 
 .   .   .   | .   .   . 
The "t-link" is r3c3 -3- r4c3

Using Ronk's example : that chain could be written
1r2c2=2r2c2-(2=3t)r3c3-(3=4)r3c5-(4=5)r4c5-(3t5=1)r4c3 :=><1>r456c2
In other words, 3 placed in the chain at r3c3 is remembered in r4c3 :
- appropriately (it sees r4c3) and
- usefully (r4c3 has 3 as a candidate)

[DonM]

Surbier,

If you are interested in Denis Berthier's work, I highly recommend reading his book, "The Hidden Logic of Sudoku (Second Edition)". He presents his concepts in a series of well documented steps with numerous examples. I won't presume to describe the xyzt-chain in full, but some aspects of his theory involve always starting a chain from a potential CEC (the z target) and allowing z (the CEC value) and t (all prior right-hand linking candidates) candidates in a potential link of the chain to be ignored if they are nrc linked to the z/t candidates. Whew! Let's go over that again slowly.....Paul

I bought Berthier's book when it first came out. It is still $42 and since that is not a paltry sum for a book, I think it is important to clarify that the book is highly technical, laden with computer solver output and reads more like a university text. IMO, while there are some interesting concepts presented, this is not a book for the manual solver. That's not to say that it isn't necessarily a good book- it has more to do with the fact that it will likely appeal to people with an interest in hard-core logic theory and an entirely different approach to solving puzzles, an approach that (unfortunately again IMO) is illustrated only with computer solver solutions to the puzzles and absolutely no direction for the manual solver in using the methods presented.

[surbier]

Thanks ronk for the example.
Now slightly modified:

Code: Select all

 .   .   .   | .   .   .
 .   12  .   | .   .   .
 .   .   23  | .   34  .
-------------+------------
135  .   .   | .   45  .
 .   -1  .   | .   .   .
 .   .   .   | .   .   . 



Would this variant be a valid xyt-chain elimination ?
( the 3 in r4c1 does not see the 3 in r3c3 )

[StrmCkr]

Code: Select all

 .   .   .   | .   .   .
 .   12  .   | .   .   .
 .   .   23  | .   34  .
-------------+------------
135  .   .   | .   45  .
 .   -1  .   | .   .   .
 .   .   .   | .   .   .

this is not a vaild xyt-chain.

the 3 is not seen and cannot reduce the 135 to the single digit 1.
it must see it in order to reduce the chain correctly.

as i suggested: it best to figure it out by maping all the chain directions out.

2 => 1
3 =>4 => 5 => 13

the key is the cells see each others implication

and network an ellimination,
the chian is bi directional as placing the elimination at the eliminated cell creates a contradiction within the linked cells.

[aran]

Thanks ronk for the example.
Now slightly modified:

Code: Select all

 .   .   .   | .   .   .
 .   12  .   | .   .   .
 .   .   23  | .   34  .
-------------+------------
135  .   .   | .   45  .
 .   -1  .   | .   .   .
 .   .   .   | .   .   . 



Would this variant be a valid xyt-chain elimination ?
( the 3 in r4c1 does not see the 3 in r3c3 )

Is it not just common sense that 3r3c3 cannot have any influence over 3r4c1 since it can't see it ?
Surbier there is no more nor less to "t" or memory or whatever you want to call it than that.
It really is very straightforward.
I think initially you misunderstood something and have thought this is somehow a complicated area.

[PIsaacson]

Would this variant be a valid xyt-chain elimination ?

No. Your own comment indicated why. r4c1 is not nrc linked to (a peer of) r3c3. Also, to repeat my prior definition for Ronk's example: If the start inference was r2c2<>2, then the t-link would not be valid because 3r3c3 would then be a left-linking candidate (false). This only works when 3r3c3 is the right-linking candidate (true) of a conjugate pair. Again, I defer to Denis's definitions, but they are very specific. As DonM pointed out -- a university text indeed. It forced me to learn more about first order logic than I ever wanted to know.

But I disagree with Don that there was absolutely no direction for the manual solver. As compared to what? Reading the original Epstein paper "Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku" to understand b/b plots for construction of NLs or AICs? We're talking about fairly advanced techniques here regardless of whether you want to pursue nrczt, nice-loops or AICs. They are all about equal in terms of degree of difficulty for the human solver, and they are all about equally guilty of not being easily explainable in terms of how to find productive chains from the human solver POV.

Denis has at least taken an extremely rigorous, albeit laborious and expensive, approach to presenting his logic. Of course, take all that with a grain of salt since I'm pretty much an advocate of his theories and nrczt makes mince-meat of nice-loops or AIC. Just a joke... Settle down out there... Not fighting words...

Cheers,
Paul

[aran]

then the t-link would not be valid because 3r3c3 would then be a left-linking candidate (false). This only works when 3r3c3 is the right-linking candidate (true) of a conjugate pair. Again, I defer to Denis's definitions, but they are very specific.

Left-linking, right linking don't IMO have any real relevance to manual solving : by which I mean that the computer needs to be told all that, but the human doesn't need that instruction (it's obvious to the brain).

We're talking about fairly advanced techniques here regardless of whether you want to pursue nrczt, nice-loops or AICs. They are all about equal in terms of degree of difficulty for the human solver

Arguable from a few points of view :
- the "need" (I think) to be in different spaces to use nrczt easily
- starting with zCEC is not usually how the human solver operates, and not perhaps how he wants to operate
- the fact that nrczt doesn't use box logic (I could be wrong there though)

[surbier]

I got it ! Thank you all for your patience !

Reading the original thread again I finally found the key sentence I overlooked or misunderstood several times:

The idea is that ...
...
such that C shares a unit with C'.

Then I agree, it's nothing complicated. I finally also understand why there is no further deduction needed.

Great !

[edit: I was blockhead! ]

I can't say much about the book. I don't have it. There is no chapter extraction publicly available, so I cannot estimate if I would understand its content.