In this post, I summarise the notions necessary to define general whips and braids and I develop the consequences of the following general idea
ZT-ING or, more specifically, ZT-WHIPPING OR ZT-BRAIDING IS THE WAY OF INCLUDING BASIC PATTERNS IN WHIPS OR BRAIDS.
It is a natural, and fully supersymmetric, generalisation of the "almost-ing" principle widely used to include ALS, AALS, AAALS ..., AHS, AAHS, ...., A-Fish, AA-Fish, ..., in AICs.
Instead of almost-ing wrt to the previous right-linking candidate in the chain, it does almost-ing wrt to the target and all the previous right-linking candidates.
In the same way as my definition of a chain unifies the previously conflicting views of a chain as a sequence of candidates and as a sequence of cells (in this case of rc-, rn-, cn- or bn- cells), my definitions of a whip and a braid unifiy the research on elementary patterns with limited resolution potential and the research on more complex patterns with broad resolution potential, which have to be based on chains/whips/braids/nets.
But it should first be recalled here that all that follows is interesting only for exceptionally hard puzzles: puzzles solvable by a human can be solved by the most basic nrczt-whips.
For completeness, let me recall the main definitions.
Definition: Given a set S of candidates and an abstract elementary pattern P (e.g. a Naked-Pair or a Swordfish), we say that another set S' of candidates satisfies pattern P modulo S if, when all the candidates in S' that are nrc-linkded to some candidate in S are forgotten from S', what remains in S' satisfies pattern P.
Definition: If P is any elementary pattern, with an associated resolution rule, a candidate C is nrc-linked to P if it satisfies the conditions of the elimination rule for P.
Now, let FP be any fixed family of basic patterns.
Definition: given a target candidate z, a zt-whip(FP) [resp. a zt-braid(FP)] built on z is any sequence L1 R1 L2 R2 L3 R3 .... Ln of elements alternatively called left-linking and right-linking, where
- L1, L2 ... Ln are candidates, (as usual, it is not necessary to extend the possibilities on left-linking candidates),
- each of R1, R2, R3 ... Rn-1 is a pattern from the FP family modulo the target and the previous right-linking candidates,
- L1 is nrc-linked to the target,
- for each 1 < k <= n: Lk is nrc-linked to Rk-1 (in the above extended sense of "nrc-linked") [resp. for braids: nrc-linked to the target or to any previous right-linking candidate]; this is the first part of the chain [resp. braid] condition,
- for each 1 <= k < n, Lk is nrc-linked to at least one element of either the rc-, rn-, cn- or bn- cell containing Rk; this is the second part of the chain condition,
- there is an rc-, rn-,- cn, or bn- cell containing Ln such that there is no candidate in this cell compatible with the target and the previous right-linking candidates.
The patterns in FP are called the generating patterns of the braids zt-braid(FP).
As the families FP of generating patterns will always contain ECP+NS+HS (rules for Elementary Constraints Propagation and for Singles), these patterns will often be left implicit.
Thus, we shall write zt-braids(BI) instead of zt-braids(ECP+NS+HS+BI). These are what I've previously called the hinged-nrczt-braids or grouped-nrczt-braids.
Similarly, we shall write zt-braids(BI+SubsetRules) to mean zt-braids(ECP+NS+HS+BI+ SubsetRules). These are what I've previously called the hinged-nrczt-ALS-braids, which subsume all the nrczt-whips, all the grouped nrczt-whips and all the grouped AICs (including ALS, AALS, AAAAALS, AHS, AAAAHS, A-Fish, AAAAFish,....)
The notion of a zt-braid(FP) establishes a duality between the families FP of basic patterns and the families zt-braid(FP) of braids.
I have proven the following:
T&E(FP) vs zt-braid(FP) theorem: for any family of patterns FP with associated resolution rules, any elimination that can be done by T&E(FP) can be done by a zt-braid(FP)
The T&E(FP) vs zt-braid(FP) theorem provides an easy means of testing whether a puzzle can be solved by zt-braid(FP).
This theorem can even provide a zt-braid(FP) solution for a puzzle, built from the trace of the T&E(FP) procedure. Notice however that this solution will differ from one obtained by directly looking for patterns in four respects:
- the zt-braids thus obtained will have lots of useless branches,
- even if the zt-braids thus obtained are manually pruned of their useless branches, they won't be the shortest ones possible,
- no simpler patterns, such as whips or 2D-chains ..., will be obtained,
- more generally, contrary to what is done for the rules in SudoRules, this procedure doesn't provide any means of putting priorities on the patterns obtained.
We are now naturally led to the question:
What is the "simplest" family FP of elementary patterns such that all the puzzles are solvable by zt-braid(FP)?
I've already mentioned that one can take FP = nrczt-braids and that all the known puzzles can be solved by zt-braids(nrczt-braids), but FP = nrczt-braids is too complex to be an interesting generating family.
The following results suggest that one can find a family FP of basic patterns much simpler than nrczt-braids such that all the known puzzles can be solved by zt-braids(FP).
Of course, the same question can be asked for whips:
What is the "simplest" family FP of elementary patterns such that all the puzzles are solvable by zt-whip(FP)?
In a sense, the question about whips is more interesting, because whips are chains (no branching) whereas braids are nets (even though relatively mild ones), but it is much more difficult to deal with it.
In a previous post, I had given results for the gsf collection of extreme puzzles. Here are more detailed results for the same braids.
- Code: Select all
Nb of puzzles solved by the different types of braids:
FP family............ECP+NS+HS.........ECP+NS+HS+BI..............BI+SubsetRules
Braids used..........nrczt-braids......hinged-zt-braids..........hinged-zt-LS-braids
Other name(s)..........................grouped-nrczt-braids......zt-braids(BI+SubsetRules)
.......................................zt-braids(BI)
1-500................0.................187.......................443
501-1000.............0.................178.......................460
1001-1500............0.................163.......................486
1501-2000............0.................168.......................490
2001-2500............0.................135.......................474
2501-3000............0.................116.......................479
3001-3500............1.................120.......................473
3501-4000............0.................113.......................472
4001-4500............1.................104.......................448
4501-5000............0.................231.......................482
5001-5500............47................348.......................500
5501-6000............434...............490.......................500
6001-6500............487...............500.......................500
6501-7000............494...............500.......................500
7001-7500............500...............500.......................500
7501-8000............500...............500.......................500
8001-8152............152...............152.......................152
Total................2616..............4505......................7859
Rest.................5536..............3647......................293
As zt-braids(BI+SubsetRules) subsume all the grouped whips and AICs, this will be the starting point for my further analyses of larger families of generating patterns.
)
