The purpose of this post is to show how the T&E vs braid theorems can be used to evaluate the scope of different types of braids (which is also an upper bound for the scope of the corresponding whips).

References:

1) Given a resolution theory T, the procedure T&E(T) was defined in the first post of this thread:

http://forum.enjoysudoku.com/viewtopic.php?t=6390.

Remember that it is the standard Sudoku T&E technique (which is not itself a resolution rule): it uses no guessing and it is not recursive (it has only one hypothesis at a time).

2) nrczt-whips were defined here and in the following posts

http://forum.enjoysudoku.com/viewtopic.php?t=5591&postdays=0&postorder=asc&start=1363) nrczt-braids were defined here:

http://forum.enjoysudoku.com/viewtopic.php?t=5591&postdays=0&postorder=asc&start=1504) Various other more elaborate forms of whips and braids were defined here:

http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=2035) Finally, the most general whips and braids associated with any family of patterns were defined here:

http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=205Let BI be the Basic Interaction rules.

Let SubsetRules2 be the set of resolution rules for (Naked, Hidden and Super-Hidden) Singles and Pairs (and, of course, ECP).

Let SubsetRules3 be the set of resolution rules for (Naked, Hidden and Super-Hidden) Singles, Pairs and Triplets (and, of course, ECP).

Let SubsetRules be the set of resolution rules for (Naked, Hidden and Super-Hidden) Singles, Pairs, Triplets and Quads (and, of course, ECP).

Theorem:

1) Any elimination that can be done by T&E(ECP+NS+HS) can be done by an nrczt-braid

2) Any elimination that can be done by T&E(ECP+NS+HS + BI) can be done by a hinged-zt-braid

3) Any elimination that can be done by T&E(SubsetRules) can be done by a zt-LS-braid

4) Any elimination that can be done by T&E(SubsetRules + BI) can be done by a hinged-zt-LS-braid

5) Finally, the general form: 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 converse of each part is obvious).

In the 2nd post of this thread, I mentioned that all the puzzles in a random collection of 1,000,000 could be solved by T&E(ECP+NS+HS) or equivalently by nrczt-braids.

As a result, puzzles that are not in the scope of nrczt-braids are extremely rare and if we want to compare the scopes of the 4 types of braids above, we can only do this on a collection of exceptionally hard puzzles.

The natural choice for this is gsf's colection of 8152 hardest.

I give these results for two reasons:

- they may help clarify through examples how the above theorems lead to scope estimations;

- they shed some very unusual light on the top level of the hierarchy, which, wrt the various types of braids considered here, appears to be drastically more homogeneous than suggested by the Q1 rating.

Remember that gsf's collection is ordered according to decreasing Q1 rating.

In the following table, the first column defines the sets of puzzles I consider: slices of 1000 or 500 puzzles, depending on variability of behaviour within the slice.

The following columns show how many puzzles of each slice can be solved using the braids mentioned in the second row or, equivalently, the T&E(FP) procedure based on the FP family of patterns in the first row.

What's noticeable is that there is almost no difference for the slices corresponding to puzzles with Q1 rating between 99408 (EasterMonster) and ~8800 (when you check this, beware that the slices have different numbers of puzzles, so that you may have to add 2 of them to get comparable slices of 1,000), after which there is a drastic change in behaviour.

- Code: Select all
`Nb of puzzles solved:`

FP family............ECP+NS+HS.........ECP+NS+HS+BI..............SubsetRules+BI

Braids used..........nrczt-braids......hinged-zt-braids..........hinged-zt-LS-braids

1-500................0.................187.......................443

501-1000.............0.................178.......................460

1001-2000............0.................331.......................976

2001-3000............0.................251.......................953

3001-4000............1.................233.......................945

4001-5000............1.................333.......................930

5001-5500............47................348.......................500

5501-6000............434...............490.......................500

6001-7000............981...............1000......................1000

7001-8152............1152..............1152......................1152

Total................2616..............4505......................7859

Rest.................5536..............3647......................393

When the theory T in T&E(T) becomes more complex than ECP+NS+HS+BI, computation times are very long: Triplets and Quads are relatively rare patterns and, in order to find them, the T&E procedure must explore almost all the candidate hypotheses, sometimes several times (phase iteration). After puzzles solved by hinged-zt-braids are discarded, there remain ~3500 puzzles in the collection; for each of them, T&E must try between 500 and 1,500 auxiliary puzzles; this makes ~ 3 to 4 million puzzles to deal with using the rules in T.

Edited 10/25/08: changed the notation to zt-braid(FP) - instead of my old zt-FP-braid.