The New Sudoku Players' Forum

[re'born]

The purpose of this thread is to clear up the confusion (mostly mine) between the almost xy-chains (introduced informally in a recent thread) and the xyt-chain's of Denis Berthier (see here for the definition and details). My goal is to show that they are distinct generalizations of xy-chains. Their overlap is what caused my initial confusion.

For the convenience of the reader I will sketch a proof of the validity of both almost xy-chains and of Denis' xyt-chains. Let me first say though that when I say "almost xy-chains", I mean a technique which is a special case of the work of bennys on ALS, aeb on Subset Counting and even the inspiration of Ravel (this post is what made me think about it formally in the first place and which is also the first occurence I remember of a semi-remote naked pair being used). Let me also apologize in advance for any misunderstandings of Denis' work that I might demonstrate below.

We begin with a proof of what everyone around here knows already, namely that discontinuous xy-chain deductions are valid. The proof (at least to me) explains why the generalizations under consideration work.

Let S be a discontinuous xy-chain with n cells (to be clear, I do not include the target cell in S). Let x_1,...x_s,e denote the distinct candidates in S, where e denotes the target candidate (i.e., the candidate involved in the discontinuity). Each link in the xy-chain is an x_i-link for some i or an e-link, and there are n-1 links. Let n_i denote the number of x_i-links and E the number of e-links. Then
n_1 + ... + n_s + E = n - 1 (*)
For each i=1,...,s, let m(x_i) (resp. m(e)) denote the maximum number of times x_i (resp. e) could occur in S in a solution. Because of the links in an xy-chain, it is easy to see that m(x_i) <= n_i and m(e) <= E + 2 (the 2 coming from the endpoints of the chain). Therefore, the max number of possible candidates in S is (by (*))
m(x_i) + m(e) <= n_1 +...+ n_s + E + 2 = n - 1 + 2 = n + 1
Hence, any placement that would decrease the max number of candidates by 2 must be invalid. In particular, if we put an e in the target cell, then we will have m(e) <= E and consequently S will have n cells and only n-1 candidates to put in them. So, we can eliminate e from the target cell.

The extension to almost xy-chains (in the form in which I originally conceived of them) is proved in exactly the same way. Any of the candidates x_1,...,x_s may be added to any of the cells in S as long as they don't change m(x_i). Extra placements of e are slightly trickier. e can be added to any cell in S that see the target cell as well as any cell that is not an endpoint and such that m(e) does not change.

The extension to xyt-chains is more complicated. Denis' method allows you to add candidates that change the max multiplicities, but in a very controlled way. In his post on xyt-chains, he makes a big deal about left and right candidates in cells and this is super important. I think about them in the following way: The right candidates are the candidates that would become true if the target cell was e. With this in mind, let S now be an xyt-chain. This gives the chain a natural total ordering on the cells. With respect to this total ordering, let D < C < B be cells such that D and B are in the same unit (the C is only there so that D and B are non-consecutive) . Let x_D denote the right candidate of D. If we add x_D to B then the max multiplicity of x_D in S will possibly increase by 1. However, since x_D is the right candidate of D, if we assume that the target cell is e, then D will be x_D and hence B will not be x_D (since B and D are in the same unit). In other words, with the forknowledge that we are going to try to assign e to the target cell, we can effectively ignore the increase in max multiplicity of x_D. Therefore, we can again eliminate e from the target cell.

From the proofs, the differences between the patterns becomes quite clear. Additionally, we can spot some strengths and weaknesses of the different approaches. For instance, the almost xy-chains can add candidates to any cell in the chain, while the xyt-chains have predetermined positions and candidates. This makes the almost xy-chains more flexible, but not necessarily as prescriptive as xyt-chains and hence perhaps more difficult for a novice to grasp.

There are already examples in the xyt-chain thread that demonstrate some of the differences, so I'll just link to them here. See this or this. I would also like to add a real example of a xyt-chain that is not an almost xy-chain. The proof above all but implies such chains exist, I just don't have one handy.

Finally, ravel has more recently been mentioning "extended xy-chains". I think that this is a completely seperate generalization that will handle cases that neither almost xy-chains nor xyt-chains will handle.