PATTERN-BASED CLASSIFICATION OF (HARD) PUZZLES1) PurposeMy purpose in opening this new thread is to expose my latest views on puzzles classification and rating.
2) Classification versus ratingI make a distinction between classification and rating. In my view, classification is more general than rating. Some classifications can be based on a unique rating, but this is not a necessary condition.
The reasons for this and details of how it works will appear later.
3) Key properties of a classification or a ratingAll the classifications and ratings I'll consider here will share the following properties, which I consider as minimal conditions a good classification or rating must satisfy:
- it should be based on purely logical definitions (and therefore independent of any implementation);
- it should be based on a clearly defined hierarchy of resolution theories;
- it should be invariant under all the logical symmetries of the game; by this I mean much more than the usual geometric and renaming symmetries: all the types of links (i.e. rc, rn, cn, bn) should be given exactly the same role in all the definitions; (e.g. no difference should be made between the rating of a triplet in rows or in blocks; no difference should be made between naked, hidden or super-hidden Subsets of same size: they are the same thing in one of the rc, rn, cn of bn spaces);
- optionally, but preferably, all the rules appearing in the hierarchy of resolution theories should be homogeneous; this is not to deter anyone from using exotic or extremely rare patterns (such as mutant Jellyfish), but to allow analysis of what they bring (in terms of classification/rating improvements) when they can be applied to some puzzle.
AFAIK, none of the existing ratings (SER, Q1, Q2, SXT, SX9) satisfy any of the above basic conditions.
For ease of language, I'll accept that a rating can have an infinite value for some puzzles; it only means that the rules it is based on are not enough to solve this puzzle.
Additionally:
- the resolution theories used to define a classification/rating should have the confluence property; this is not necessary for being able to give a purely logical definition, but this is necessary for having good computational properties; however, whip theories (that do not have the confluence property but are very close to having it and are a good approximation of braids) will also be considered;
- the resolution theories used to define a classification/rating should be formalised in such a way that they display some degree of generality beyond Sudoku, if any; again, this is not a necessary condition, but in my experience it allows to find the proper formulations and eventually to extend them (as a matter of fact, most of the rules used in Sudoku can be defined in any CSP [added 2013/04/30: see reference b' for detailed illustrations to various logic puzzles]).
4) A recall of a few basic factsUsing my formalised definition of Trial-and-Error (T&E, see references b, b', c, e or g), my old T&E(2) conjecture is that all the 9x9 puzzles fall into a first rough three-level classification:
1) they can be solved by Singles;
2) they can be solved by ordinary T&E;
3) they can be solved by T&E iterated once.
(Notice that this is not true for larger sized puzzles).
Contrary to the still older backdoor-size 2 conjecture (first disproved by EasterMonster), the T&E(2) conjecture has resisted the recent findings of huge collections of new hardest puzzles. I shall show later that disproving it would require the discovery of puzzles very very much harder than the hardest known ones.
Of course, T&E is not a resolution theory (but a procedure) and this classification does not
a priori satisfy the above-mentioned conditions. BUT, I've also shown that:
- being in T&E(1) is equivalent to being solvable by braids (references b, b', c, g);
- being in T&E(2) is equivalent to being solvable by B-braids (references b, b').
The T&E(0) layer (about 29.17% of the minimal puzzles - unbiased statistics) is devoid of any interest, consisting of very easy puzzles.
The T&E(1) layerThe B rating of a puzzle (defined as the largest braid size necessary to solve it) defines a sub-classification of the puzzles in the T&E(1) layer. In references, a, b, b', c, e and h, I have given detailed results about the statistical distribution of puzzles in this layer.
I have also shown that:
- the W rating is a very good approximation of it (they are very rarely different);
- allowing additional resolution rules (e.g. naked, hidden and super-hidden Subsets) rarely leads to a smaller rating.
Noticeably, the T&E(0) + T&E(1) layers together contain almost all the minimal puzzles. The rest is less than 1 in 10 millions (but considering the huge number of puzzles, this may still be a big number in the absolute).
The T&E(2) layerAs a result of the above, this thread will be mainly devoted to the classification of the hardest puzzles - which, within the context of this thread, I'll assimilate to being in T&E(2) (this is a broad understanding of "hardest").
It is mainly about puzzles much beyond human solving capabilities, but such puzzles can have exotic patterns (such as in EasterMonster) whose discovery makes them simpler. How much simpler will be one of the topics I'll discuss.
Being in T&E(2) is equivalent to being solvable by B-braids, which entails being solvable by Bp-braids for some p. The largest value of p I've found in the known collections of hardest puzzles is 7. And I've found there only 3 such extreme puzzles.
Whence my more recent conjecture that all the puzzles can be solved by B7-braids. Even if a puzzle requiring B8-braids was found, this would still leave much room before we can find one beyond T&E(2) and this considerably re-inforces the T&E(2) conjecture.
5) The types of classifications / ratings I'll considerAll the ratings or classifications I'll consider will be based on generalised whips and braids (or occasionally on reversible Subset chains). These have been defined in references c, e, g. Much more detail has been devoted to them and to associated proofs in references b or b'.
In short, a generalised whip or braid is a whip or braid in which we accept sub-patterns (instead of mere candidates) as right-linking objects.
The types of sub-patterns I'll consider are mainly Subsets, g-Subsets or Braids.
6) ReferencesMy three books:
a) The Hidden Logic of Sudoku (hereafter
HLS, preferably the second edition);
b) Constraint Resolution Theories (hereafter
CRT; the part of this book dedicated to Sudoku can be considered a sequel to HLS);
b') Pattern-Based Constraint Satisfaction and Logic Puzzles (hereafter
PBCS); a full pdf version in available at
http://arxiv.org/abs/1304.1628;
(see also on my website, a few papers published in scientific journals, freely available in pdf form).
c) My website
http://www.carva.org/denis.berthier, more specifically the Sudoku pages:
http://www.carva.org/denis.berthier/HLSMy threads on this forum, mainly:
- the old ones, partly lost after the Big Crash (links are not active in the recovered pdf versions)
d)
http://forum.enjoysudoku.com/the-concept-of-a-resolution-rule-and-its-applications-t5600.htmle)
http://forum.enjoysudoku.com/fully-supersymmetric-chains-t5591.htmlf)
http://forum.enjoysudoku.com/rating-rules-puzzles-ordering-the-rules-t5995.htmlg)
http://forum.enjoysudoku.com/abominable-trial-and-error-and-lovely-braids-t6390.htmlh)
http://forum.enjoysudoku.com/the-real-distribution-of-minimal-puzzles-t30127.html- the new ones
i)
http://forum.enjoysudoku.com/more-on-whips-braids-t-e-t30230.htmlj)
http://forum.enjoysudoku.com/g-whips-and-g-braids-t30231.html[Edit 2013/04/30: added reference b']