Rating, again
Rating puzzles has always been a hard problem, much harder than solving them.
The W and B ratingsLong ago, I have introduced the W and B ratings (at that time, I used more complex names: pure nrczt-whip and pure nrczt-braid ratings) based on the length of whips or braids necessary to solve a puzzle.
The
B rating satisfies the minimum properties one may expect of a consistent rating:
- it is defined in a purely logical way, independent of any implementation;
- it is based on an increasing sequence of resolution theories that have the confluence property;
- using the "simplest first" strategy, it can therefore be computed with only one resolution path;
- it is invariant under all the Sudoku symmetries and super-symmetries;
- it does not make any difference between the four 2D spaces (said otherwise, it makes no difference between contradiction links along numbers, rows, columns or blocks).
Moreover:
- the
W rating is finite for almost all the minimal puzzles (tested on 10,000,000 randomly generated ones);
- the W rating associated with the simplest first strategy, when finite, provides a good approximation of the B rating;
- due to the almost subsumption theorems of (Naked, Hidden and Super-Hidden) Subsets by whips of same length, the W rating is almost always equal to the S rating (based on Subsets) when S is finite.
The braid and Subsets techniques can be used in conjunction; they lead to define the
S+B rating (which I formally called the nrczt-braid rating). The S+B rating has all the good properties of the B rating listed above. For almost all the puzzles, one has B = S+B: adding Subsets in the landscape does not change much. Ina ll this, braids can be replaced by whips, still with little change in the resulting ratings.
It is essential to notice that this is enough to rate all the puzzles a normal player can solve by hand - and much beyond.
As it deals with puzzles no one is likely to solve by hand, the rest of this post can only be interesting from a more theoretical point of view.
Straightforward extensions of these ratings are the
gB and gW ratings, based on g-braids and g-whips [which I formally called braids(BI) and whips(BI)]. They satisfy all the good properties of ratings listed above.
The SpB and BpB ratingsNow considering exceptionally hard puzzles, more complex solving techniques are needed.
Long ago also, using a more complex terminology than now, I have presented in this forum other rating(s) based on various families of braids with embedded patterns.
First step beyond braids or g-braids:For any p > 1, Sp-braids are defined as generalized g-braids accepting inner Subsets of maximum length p as their right-linking objects, while the left-linking objects always remain mere candidates. S-braids accept inner Subsets of
a priori unrestricted length (but the length of inner Subsets is of course smaller than the total length of the braid in which they are embedded).
For any p >1, one can define the
SpB rating, associated with Sp-braids in the same way as the B rating is associated with ordinary braids. And one one can define the
SB rating, associated with S-braids with inner Subsets of
a priori unrestricted length.
Second step beyond braids or g-braids:Similarly, for any p > 1, Bp-braids are defined as generalized braids accepting inner braids of maximum length p as their right-linking objects, while the left-linking objects always remain mere candidates. And B-braids accept inner braids of
a priori unrestricted length (but the length of inner braids is of course smaller than the total length of the braid in which they are embedded).
For any p >1, one can define the
BpB rating, associated with Bp-braids in the same way as the B rating is associated with ordinary braids. And one one can define the
BB rating, associated with B-braids with inner braids of
a priori unrestricted length.
All these ratings also satisfy all the good properties listed above.
In the same way as braids or whips are much more powerful than Subsets, Bp-braids are much more powerful than Sp-braids.
New resultsI introduced all these more complex braids with inner patterns on this forum in 2008 ("abominable T&E and lovely braids" thread), where I also gave some idea of the scope of Sp-braids, using gsf's 8152 list. All this has also been available on my website for a long time, in a more synthetic form (
http://www.carva.org/denis.berthier/HLS).
What's new since the time I introduced all this fauna ?
- I have studied these patterns more formally and in much more detail in the third part of my new book (
Constraint Resolution Theories, or
CRT, announced a few posts above); unless you want formal definitions and proofs, reading it is not necessary for understanding these patterns and the main results proven in it (the confluence property of the associated resolution theories and the "T&E(T) vs T-braids" correspondence theorem);
- as my old conjecture that all the puzzles can be solved with at most 2 levels of Trial-and-Error [T&E(2)] has survived the recent new series of 11+ puzzles, and due to the "T&E(2) vs B-braids" correspondence theorem proven in
CRT, all the known puzzles can be solved either by Singles, or by ordinary braids or by B-braids; moreover, the necessity of B-braids appears only for extremely rare cases (fewer than 1 in 10,000,000);
- as a result, the BB rating of a puzzle P (i.e. the minimal length of the B-braids necessary to solve P) is universal, in the sense of being finite for all the puzzles (at least for all the known ones, but I conjecture it's true for all), in addition to having the same good properties as the B rating;
- I now have detailed classification results for gsf's 8152 list for Bp-braids (instead of only Sp-braids previously).
Open questionOne question that remains open is the minimal value of p such that all the (known) puzzles can be solved with Bp-braids (possibly with a BpB rating larger than their BB rating). Until now, I have examples that need p≥6. But, for such cases, computation times are long (I have never had time to optimise this program, independent of SudoRules) and I can't yet try many puzzles.
Whips and braids have the essential property of being non-anticipative (or, equivalently, non-look-ahead).
As inner braids can be considered as a form of look-ahead, knowing this minimum value of p would provide an upper bound for the degree of look-ahead necessary to solve any puzzle.
