Hi

logel,

Many comments in a single post. Thanks for your interest. I'll try to answer.

logel wrote:(A) Classification

Every classification complying your terms is a lot of work to implement.

Yep, but I've implemented them. On my website and in another thread (

http://forum.enjoysudoku.com/rating-rules-puzzles-ordering-the-rules-t5995.html), very long ago, I have even given very detailed (unbiased) results for the W and B classifications.

Even before implementation, it's also a lot of more theoretical work: you have to define correctly relevant families of rules and to prove that they have the confluence property.

logel wrote:For me its absolutely unclear what kind of insight 10 more classifications should bring. I do not expect them to converge to a final classification.

This is what I've always said: there can't be any unique classification. Any classification has to rest on a predefined family of well defined resolution rules (or on some more or less obscure procedure, or on some abstract "algorithmic complexity" definition, but these would not be compatible with pattern-based resolution and therefore not "final" for Sudoku addicts).

Each family of resolution rules carries its own classification. Classification results obtained with it give an idea of the resolution power of this family and of each of its elements.

In my view, a given classification is also a scale against which other rules can be measured.

Unfortunately, for many families of rules (e.g. AICs), no study of their resolution power has ever been conducted; as a result, their discussion has been mainly about examples and personal opinions on reversibility, ...

In addition to this, although there is no unique rating, my approach leads (at least me) to a clear understanding of the basic principles on which any rating should be built.

One of the principles I haven't mentioned above - because it is more a common point of all my other rating definitions (W, B, gW, gB, S, SB, BB, ...) than an

a priori on rating systems - is, the rating of a rule should be based on the number of CSP-variables (of 2D cells, if you prefer) necessary to formulate it.

logel wrote:And for "statistics" there exists no reference sample of unbiased problems and never will. Because there can be no method to prove a sample to be unbiased.

You are (almost) wrong on this point. I've defined a controlled-bias generator (see my website or here:

http://forum.enjoysudoku.com/the-real-distribution-of-minimal-puzzles-t30127.html). A first, quick implementation was done by Eleven as a simple modification of suexg and then it has been progressively improved by (direct or indirect) contributions from many people: Eleven, Paul Isaacsson, gsf, Brian Turner... I've run it on several PCs in parallel (the equivalent of several months of CPU time) and I obtained a collection of

~ 7,000,000 independent puzzles, with known bias. For statistics, "with known bias" is almost as good as "unbiased", provided you use the proper correction formulae.

All these puzzles are in T&E(1).

What's true is, there's no known unbiased (or with known bias) collection for the hardest (in the broad sense of: in T&E(2)). Probably the best approach to this is Eleven's collection of 13,000,000 (or is it 15,000,000?) T&E(2), though it is not proven to be unbiased. AFAIK, it isn't public (?)

logel wrote:(B) Simplicity

Everybody looks for more "simple" solutions pathes, but obviously there is no common understanding what is simple. A precise definition (here it is again) would be a good challenge.

This is just the second side of the previous question. There can't be a unique definition of simplicity.

logel wrote:denis_berthier wrote:SER is the only rating among these 5 that captures the logical complexity of some of the hardest sudokus. The other 4 ratings completely fail on this point.

To make such a statement you seem to know the logical complexity. If you can calculate the complexity I would like to know how you do it, otherwise the above comment on personal opinions apply.

OK, you caught me. I meant the logical complexity defined by the B?B classification I introduced in this thread. I thought it was clear from the context.

logel wrote:(C) Semantics of rating

Rating is an attempt to approximate the complexity of a sudoku problem. But there are two completely different kinds of complexity.

a) the minimal complexity of finding a solution path

b) the minimal complexity of verifying a solution path

When looking at the discussions, it seems that (a) is meant and expected allways. But (a) is a property of the solving algorithm. A hard rating of complexity (a) would require that ALL possible solving algorithms cannot solve the problem beyond a certain number of steps. There is no hope to calculate such complexity.

In contrary the complexity (b) is nearer to earth, because it depends on the solution pathes only. As far as I can see, the ratings use properties of the solution path, mainly what is regarded as the most complicated step necessary to solve. Although complicated solution pathes probably also require a more complicated finding process, it is is generally incorrect to assume (a) == (b) or even (a) = fkt(b).

It's true that rating has always been the rating of solving (unless I'm missing something, verifying a resolution path is obvious) and it has always been the rating of the hardest step (mainly because nobody knows how to do otherwise).

However, in my approach, it is NOT a property of an algorithm. Although it is explicitly dependent on a family of resolution rules, it is purely logical. And, when it is satisfied by the family of rules, the confluence property guarantees that it does not depend on which particular resolution path using these rules combined with a simplest-first strategy is chosen; otherwise, all the paths would have to be tried.

Even my 3-level T&E classification, apparently based on the T&E procedure, is indeed purely logical, as it corresponds to being solvable respectively by Singles, braids or B-braids.

Every puzzle has an intrinsic rating (possibly infinite) for each family of rules. What's noticeable is, most of the time, these ratings (W, B, gW, gB, W+S, ...) are equal.

logel wrote:Using only a fraction of the solution path is questionable for solutions of "hard" problems with many complicated solution steps. This may be a reason for "failed" ratings shown in this thread.

Clearly, no, it can't be the reason. All the ratings considered in this comparison are based on the same "hardest step" approach.

logel wrote:(D) T&E layer

Trying to expand the class by introducing more methods like BoxLine, Pairs or Triples into the contradiction path has surprisingly very limited effect.

T&E(S), T&E(S+BI), T&E(S+BI+Pairs), T&E(S+BI+Pairs+ Triplets), ... are increasingly more powerful (as shown by my old classification results in this thread:

http://forum.enjoysudoku.com/abominable-trial-and-error-and-lovely-braids-t6390.html)

But it's true that it has little effect (statistically) on the rating of puzzles in T&E(1) as shown by the other old results in this thread:

http://forum.enjoysudoku.com/rating-rules-puzzles-ordering-the-rules-t5995.htmllogel wrote:Looking closely at the remaining cases of class (3) one finds that solving requires branched contradiction logic. The critical network contains at least two three-way connections that block progression of the type (2) procedure. Or in other words, all remaining candidates live in networks of three (or more) coupled loops. I found also that a next recursion level is unnecessary. It is sufficient to branch at constraints that are touched by the steps before and are down to a two-way branch and then apply singles to both branches. I tried various toplists from a year ago and determined no exceptions.

Anyway there is no substancial difference between recursion and branching, so I dont understand many peoples animosity against recursive methods. The main deficit of recursive methods is that they usually lead to awfully long and multiple branched contradiction pathes.

Being in T&E(2) is equivalent to being solvable by B-braids, which means that contradictions arising from the truth of two candidates have to be considered instead of only contradictions arising from a single candidate - whichever method one uses for this.

Some people try to hide a recursion level either by tagging everything or by extracting from xsudo a few more or less readable steps, displaying them with all the bling of grandiose graphics and hiding all the other illegible steps.

I don't consider recursion and branching as being exactly the same thing:

- recursion can only be defined in a procedural way (even so, my conjecture, still verified, that all the puzzles are in one of the 3 T&E classes means that only one level of recursion is necessary).

- various types of branching can be defined in a pure logic way.

Showing that some type of recursion is "equivalent" to some type of branching (i.e. that the result of some procedure can also be the conclusion of an associated resolution rule, e.g. that a T&E(2) solution can always be replaced by B-braid logic solution) may be a lot of work (a very strange thing for a 1st of May!)