Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Ranking the rules/puzzles. Logical/psychological complexity

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 11:03 am    Post subject: Ranking the rules/puzzles. Logical/psychological complexity Reply with quote

In this post, I'd like to raise three different problems that are intimately related:
- ranking of the rules vs ranking of the puzzles,
- logical vs psychological complexity,
- auxiliary representations of a puzzle.

A given Sudoku puzzle will usually be given different rankings by different Sudoku creators.
The reason is that any ranking of the puzzles relies:
- firstly on the set of rules one uses to solve them,
- secondly on some combination of the rankings of the sequence of rules necessary to solve the puzzle; since there may be several ways to solve it, this supposes that one of these ways is chosen, which in turn supposes:
- thirdly some precedence ordering of the rules, i.e. an explicit or implicit ranking of these rules (and it is well known there is no agreement on any such ranking).
Moreover, as far as I know, there is no public debate on any of these rankings, for the simple reason that they are not disclosed by the puzzle creators.


Worst, there seems to be no general guiding principles on which a ranking of the rules could be based.
One of the reasons for this seems to be that (as far as I know) the following fundamental distinction has not yet been stated. There may be a gap between the "psychological" complexity of a rule (however you define it) and its logical complexity (again, however you define it).
For a given rule, its "psychological" complexity should somehow be defined on the basis of how difficult it is to find the corresponding patterns on a grid. But this may depend on the specific instantiations of such patterns (e.g. where they occur in the grid). It may therefore be different for two equivalent grids (obtained by a rotation or a permutation of rows or columns) or for two different persons. Or it may depend on whether a required link between two cells (e.g. in a chain) is a row, a column or a block/box (whatever you call it), whereas this information is totally irrelevant from a logical point of view. It also obviously depends on which auxiliary graphical representations we use (see the examples below).

For all these reasons, I personally feel totally unable to rank the "psychological" complexity of a rule and I've therefore concentrated on the logical complexity (and used it to rank only the rules, not the puzzles).
In my new book ("The Hidden Logic of Sudoku" - see my post on the forum on the mathematics of Sudoku), I have introduced two guiding principles and applied them to the logical ordering of the all rules I consider:

P1) two rules that can be deduced from each other by a (generalised) logical symmetry should be given the same place in the ordering; this entails that the same complexity is granted to identical patterns in the standard row-column representation or in the new row-number and column-number representations I have introduced; principle P1 is thus related to the third problem in this post: representations of the puzzle;

P2) the complexity of a rule should be roughly defined by the minimum number of cells (in the standard row-column representation or in the new row-number and column-number representations) necessary to state it. (Sublevels might be defined based on the complexities of the patterns of values in each cell - but I've not tackled this point).

I can now give two simple examples of the gap between the psychological complexity and the logical one, showing simultaneously that principle P1 does not extend to psychological complexity (unless we allow new representations):
- Naked Triplets, Hidden Triplets and Swordfish are given the same logical complexity (but obviously they do not have the same psychological complexity when one considers only the standard representation);
- xy-chain and hidden xy-chains of the same length (their counterparts in rn- and cn- representations) are given the same logical complexity, although some hidden xy-chains look very complex in rc-space.

If anybody can formulate rules or at least exhibit detailed observations of a systematic deviation of the psychological complexity from the logical one in the same representation space, say the standard one, I think that would be a great thing for Sudoku (and cognitive science).
I've not been able to find any reference on this. So, if you have some, please let us know.

(In addition, I'd be interested also in any reference on how the ranking given by a known creator can be used to guide the search for a solution).
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Jun 13, 2007 12:23 pm    Post subject: Re: Ranking the rules/puzzles. Logical/psychological complex Reply with quote

berthier wrote:

Moreover, as far as I know, there is no public debate on any of these rankings, for the simple reason that they are not disclosed by the puzzle creators.

you are right that rating/ranking is currently art more than science

the best a programmer can do is provide an initial stab at rating, along with mechanisms
for others to tweak the ratings to reach some form of consensus

my solver allows both the constraint order and the rating formula to be specified on the command line
the defaults for the default rating and the -q1 rating (for the hardest sudoku) are documented by the --man option
and in postings on the players forum
Back to top
View user's profile Send private message Visit poster's website
berthier

Joined: 13 Jun 2007
Posts: 43
:
Location: Paris, France

Items
PostPosted: Wed Jun 13, 2007 1:20 pm    Post subject: Re: Ranking the rules/puzzles. Logical/psychological complex Reply with quote

gsf wrote:
you are right that rating/ranking is currently art more than science
the best a programmer can do is provide an initial stab at rating, along with mechanisms
for others to tweak the ratings to reach some form of consensus

I mostly agree on this.
What I've tried to do is finding general principles (which may themselves be debated) and applying them systematically.
I think a clear distinction between logical and psychological complexity is essential here because "tweaking the ratings" may be done easily on large collections of puzzles by a machine (giving something corresponding to logical complexity) but may be much more difficult to do on large scales with human players.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron