RATING RULES / PUZZLES; ORDERING THE RULES

INTRODUCTION - MOTIVATIONS

Several ratings of rules or puzzles are known and they generally lead to different classifications of puzzles.

Comparison of different ratings can't therefore be done on a puzzle by puzzle basis. They can only be statistical.

I tried a first approach of this problem, based on a small sample (31 of the 33 "Unsolvables") for which 5 different ratings were available.

These results are still available on this forum, here: http://forum.enjoysudoku.com/viewtopic.php?t=4833&start=90

They suggested that it would be interesting to extend this study to larger collections of puzzles, preferably random ones.

The various ratings can also suggest different clasification of the rules.

The ratings initially considered are (this list can be extended if participants propose new ratings):

NRCZT-rating

SER-rating

SUEX9-rating

SUEXT-rating

GSF-Q1-rating

The purpose of this thread is thus multiple. It aims at least at:

- assembling in a single place a precise definition of each rating (or pointers to such definitions)

- giving references to where and how each of these ratings can be computed

- providing software so that anyone can compare for himself the various ratings on large collections of puzzles

- providing large collections of puzzles that can be used as references for such comparisons

- evaluating the statistical complexity of rules (mean value analysis) and, for rules depending on some parameters, how this complexity varies with these parameters

(examples of possible parameters: length for chains, maximum ALS size for chains with ALS, ...)

- analysing the consequences on rules classification

CORRELATION COEFFICIENT OF TWO RATINGS

The main and simplest statistical tool for comparing two ratings is their correlation coefficient.

Given a collection of N puzzles and several rating functions, each of these rating functions is a statistical variable and it can be seen as a vector in R^N.

The (linear) correlation coefficient between 2 statistical variables has a value between -1 and +1. It is the cosine of the angle between the associated vectors in R^N.

A correlation coefficient whose absolute value is greater than .8 is generally considered high.

A correlation coefficient whose absolute value is smaller than .5 is generally considered low (which means that there is no meaningful correlation between the two variables - the angle between the 2 vectors representing the 2 variables in R^N is > 45°).

In a forthcoming post, I'll provide pseudo-code for computing this coefficient (this is a very standard statistical tool).

MEAN DISTANCE OF A RATING FROM ALL THE OTHERS

Whereas the correlation coefficient allows comparisons between 2 ratings, the mean distance from a rating to all the others allows to evaluate its compatibilty with them.

Its geometrical meaning is a mean distance in space R^N between the unit vectors associated to each rating. (Lengths are discarded, everything is brougth to the unit sphere in R^N. This rescaling allows to eliminate meaningless differences between different ratings).