NRCZT-BRAIDS
Just a little time after the nrczt-whips, which synthesise in a single chain pattern the nrczt-chains and nrczt-lassos, here is a generalisation of them, the nrczt-braids. I'll soon show that they have very interesting properties.
In a previous post, I've defined nrczt-nets by generalising nrczt- chains and lassos (or nrczt-whips, in my new perspective) with the possibility of having several right-linking candidates in the same rc-, rn-, cn- or bn- cell as a left-linking one. See near the bottom of this page: http://forum.enjoysudoku.com/viewtopic.php?t=5600&postdays=0&postorder=asc&start=90. These nets include grouped nrczt-chains, which are a relatively mild special case. But the most general nrczt-nets are very hard to use, because their structure is complex and the conditions of the associated elimination theorem are very hard to check.
In this post, I'll introduce nrczt-braids, a much milder kind of nets, with an easier elimination theorem.
Informally, given a target candidate z, an nrczt-braid built on z is, as an nrczt-whip, a linear sequence of candidates, alternatively called left-linking and right-linking. Its precise definition is obtained from that of an nrczt-whip by merely changing the condition "any left-linking candidate is nrc-linked to the previous right-linking one" by "any left-linking candidate is nrc-linked to a previous right-linking one or to the target".
As any nrczt-whip, an nrczt-braid can also be considered as a sequence of rc, rn, cn or bn cells.
And, still as any nrczt-whip, an nrczt-braid produces a contradiction on its target when its last cell has no right-linking candidate compatible the previous ones and with the target.
Now the formal definition.
Definition: an nrczt-braid of length n for a target z is a sequence of candidates L1, R1, L2, R2, .... Ln-1, Rn-1, Ln, alternatively called left-linking and right-linking, such that:
- for any 1<= k <= n, Lk is nrc-linked to the target or to a previous right-linking candidate (some Ri, for i < k);
- for any 1 <= k < n, Lk and Rk are in some well defined rc, rn, cn or bn cell (which entails they are nrc-linked) such that each of the other candidates in this cell is nrc-linked to the target or to a previous right-linking candidate; Rk itself is not nrc-linked to any of these;
- in at least one of the four rc, rn, cn or bn cells containing Ln, each of the other candidates is nrc-linked to the target or to a previous right-linking candidate.
Notice that, as nrczt-whips, nrczt-braids still have one and only one right-linking candidate per cell but the last one, but they may have several left-linking candidates branching off the target or off any right-linking candidate - with the restrictive condition that the set of candidates must be totally ordered. Their branching structure is thus severely restricted.
There are therefore two complementary views of nrczt-braids: sequential (a sequence of candidates) or as a net with a restricted form of branching. Both of them are useful.
The following definitions are used:
- an additional z-candidate in a cell is defined as usual: it is nrc-linked to the target);
- an additional t-candidate in a cell is defined as usual: it is nrc-linked to a previous right-linking candidate (one could add: in the same branch OR in any other branch; but such a distinction is pointless as "previous" refers to the total ordering of the right-linking candidates induced by the total ordering of all the candidates);
- a terminal right-linking candidate is one which sprouts no left linking candidate.
Pruning useless parts of branches: we may add the condition that the any terminal right-linking candidate is nrc-linked to a t-candidate in a cell after his own (in the global ordering). Otherwise, its cell can merely be eliminated from the nrczt-braid, thus leaving a smaller one with the same target. Doing this as many times as necessary, we can reach an nrczt-braid with no useless cell; we'll call this a minimal nrczt-braid. Unless otherwise stated, all nrczt-braids will be minimal (but this is only for efficiency reasons).
Any branch of an nrczt-braid starting from the first llc and ending with the last llc is thus almost an nrczt-whip; it only has a few additional candidates (other than the usual t- or z-) in some of its cells, candidates which must be dealt with by considering additional branches.
Notice that this is nevertheless very different from accepting to take left-linking candidates among already deleted candidates: when we progressively build our nrczt-braid, we don't have to consider all the missing candidates anywhere in the grid as potential left-linking ones for the next cell. We can only consider those that are nrc-linked to an already chosen previous right-linking candidate. Said otherwise, this definition sticks to the idea that deleted candidates play no role in the rules.
It is then easy to prove that,
nrczt-braid elimination theorem: given an nrczt-braid, its target can be eliminated.
Proof: exactly the same as for nrczt-whips, following the total ordering of the candidates, until the last left-linking candidate, with no compatible right-linking one, is reached. The proof shows progressively that, if the target was true, then all the left-linking candidates would be false and all the right-linking candidates would be true.
Finally, it may be useful to give an elementary example of something which cannot be the beginning of any nrczt-braid (it is impossible to define any total ordering of the candidates, compatible with the above definition):
- Code: Select all
/ {llc1 rlc1 t1#rlc2}
/
z
\
\ {llc2 rlc2 t2#rlc1}
each of the 2 lines represents an rc, rn, cn or bn cell,
with t2 an additional candidate nrc-linked to rlc1 and t1 an additional candidate nrc-linked to rlc2.
From z true, there is no possibility of concluding that rlc1 is true or that rlc2 is true: one can only conclude (rlc1 & rlc2) or (t1 & t2)
This example is also an indication on how nrczt-braids could be generalised. But before generalising them, there's a lot more to say about them.
