FAMILIES OF RESOLUTION RULES REVISITEDSeveral times, I've mentioned that I'd been considering four large families of resolution rules:
1) the elementary constraints propagation rules or ECP: elimination of candidates via propagation of direct contradictions along rows, columns and blocks,
2) the basic interaction rules between rows and blocks and between columns and blocks, BI
3) the subset rules: Naked, Hidden and Super-Hidden (or fish) versions of Singles, Pairs, Triplets, Quads,
4) the xy-to-nrczt (xy, hxy, xyt, hxyt, xyz, hxyz, xyzt, hxyzt, nrc, nrct, nrcz, nrczt) family of chain rules (including chains, lassos and whips).
I've already shown the unity of the subset rules through symmetry and super-symmetry.
I've also shown why all the rules in the xy-to-nrczt family can be considered as generalisations of the basic xy-chain rule. This includes nrc-chains, equivalent to the basic NLs or AICs (basic meaning "with no ALSs"
. Although nrczt-chains subsume the whole family, the other chains are easier to find and should therefore not be forgotten. This family is thus organised in a pedagogical hierarchy.
The above rules are enough to solve almost any randomly generated puzzle (indeed, in several tens of thousands of randomly generated puzzles, I've met none that they couldn't solve).
From experiments with hundreds of puzzles taken from various forums, it appears that they are enough to solve puzzles upto SER=9.3. In particular, they are used daily by human players on the French sudoku-factory forum to solve puzzles at SER 9.1 to 9.3. They can probably solve any puzzle that any expert human player can solve and even much more.
It is important to recall this, because the sequel will discuss more complex patterns and I want to make it clear that such patterns, especially braids, are not necessary but for exceptionally hard puzzles.
Considering the current interest for such exceptional puzzles, I've recently extended my set of resolution rules in two directions.
Firstly, I've generalised my idea of additional z- and t- candidates and I've introduced a very general principle,
zt-ing, that allows to define new patterns and associated new chain rules from any family FP of basic patterns: zt-whip(FP). zt-whipping is a general method (more general than the classical almost-ing) for including in chains/whips any pattern having an associated resolution rule.
In essence, the generalisation to nrczt-whip(FP) consists of allowing the right-linking candidates of a whip to be whole patterns instead of mere candidates.
If one takes FP=ECP+NS+HS, one gets the ordinary nrczt-whips.
If one takes FP=ECP+NS+HS+BI, one gets the grouped or hinged nrczt-whips.
If one takes FP = ECP+NS+HS+BI+SubsetRules, one gets a new family of chain patterns,
whip(ECP+NS+HS+BI+SubsetRules), more general than nrczt-chains, AICs with ALSs and than their grouped or hinged counterparts. Indeed, these whips contain any AAAALS, AHHHHS and any AAAAAA-Fish, with as many A's or H's as one wants.
These patterns are chains, in exactly the same sense as any nrczt-chain or any AIC. They can be considered as defining a new set of levels in the hierarchy defined by family 4.
Such generalisations of nrczt-chains have also already been used in the sudoku-factory forum (see solutions by Caravail and Abi) - although in these cases ordinary nrczt-whips were enough.
Secondly, with the introduction of
nrczt-braids, I have added a fifth family, composed of a (relatively mild) kind of nets.
The above two extensions can be combined, leading to zt-braids(FP) for any family of patterns with associated resolution rules.
I've also shown the close relationship between braids and Trial-and-Error (T&E) - the standard T&E procedure (which is not itself a resolution rule) with no guessing and no recursion:
for any family FP, any elimination that can be done by T&E(FP) can be done by some braid(FP).
All the above patterns have two very important properties (defined in detail in the first posts of this thread), helpful for finding them:
- they are
non-anticipative, i.e. the validity of a partial whip/braid depends only on the previous candidates (and it can therefore be checked on-the-fly)
- they are
composable, i.e. partial whips/braids can be linkd together to make longer ones, with obvious compatibility conditions at the junction.
Finally, using the above T&E vs braids theorem and taking FP = the family of nrczt-braids, I've shown that all the known puzzles can be solved by zt-braids(nrczt-braids).
As zt-braids(nrczt-braids) are a complex kind of nets, I'm currently trying to find a simpler FP family with the same property.
Such work may seem very far from the normal player's topics of interest, but I'm not considering this as replacing anything of what I've done previously - just as a short excursion in the realm of exceptionally hard puzzles, most of which have never been solved by human players but have given rise to extremely complex net solutions.
