Pattern-based classification of (hard) puzzles

Advanced methods and approaches for solving Sudoku puzzles

Pattern-based classification of (hard) puzzles

Postby denis_berthier » Tue Mar 20, 2012 10:03 am



PATTERN-BASED CLASSIFICATION OF (HARD) PUZZLES


1) Purpose
My purpose in opening this new thread is to expose my latest views on puzzles classification and rating.


2) Classification versus rating
I 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 rating
All 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 facts
Using 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) layer
The 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) layer
As 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 consider
All 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) References
My 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/HLS

My 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.html
e) http://forum.enjoysudoku.com/fully-supersymmetric-chains-t5591.html
f) http://forum.enjoysudoku.com/rating-rules-puzzles-ordering-the-rules-t5995.html
g) http://forum.enjoysudoku.com/abominable-trial-and-error-and-lovely-braids-t6390.html
h) 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.html
j) http://forum.enjoysudoku.com/g-whips-and-g-braids-t30231.html

[Edit 2013/04/30: added reference b']
Last edited by denis_berthier on Tue Apr 30, 2013 5:04 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby champagne » Tue Mar 20, 2012 12:28 pm

well, one more rating program, why not.

May be theoretical analysis of the field are requiring such a program, but this is not the reason why I am working in that field.


I am as many, bored by long path generated by solvers, including mine.

So I am looking for short solutions to hard puzzles that players can find.

This require intensive use of

- uniqueness property
- special patterns leading to quick eliminations at the start.

may be here some stats.

In the data base of "potential hardest", to day including more than 30 000 puzzles

. more than 20 000 have an exocet pattern
- about 25 000 have one or several of the following

. Exocet
. SK loop
. Symmetry of given
. multi fish

I guess you made a classification of the puzzles included in that data base with your rating tool

what is, seen by your tool, the percentage of puzzles eligible to the last class in that lot .



champagne
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Tue Mar 20, 2012 2:25 pm

champagne wrote:well, one more rating program, why not.

I think you missed the main point, maybe because you didn't leave me time for my next posts (in which I planned to give a few examples).

What I'm proposing is not mainly a new rating program - although I also have a universal rating (the BB rating) satisfying all the properties I mentioned in my introductory post.
But the main point is, I want to introduce a principled, theoretically grounded approach to classification (which is the case of none of those associated with the other ratings I've mentioned).
As for the various classifications I'll introduce (later), of course I have a few programs that compute them.

champagne wrote:I am as many, bored by long path generated by solvers, including mine.
So I am looking for short solutions to hard puzzles that players can find.

I can understand this. I'm also bored by my whip or g-whip resolution paths but I still consider them, in all modesty, as the backbone of the best existing classification for puzzles in T&E(1), the associated rating being occasionally improved by more specific patterns. My approach to the remaining T&E(2) is similar.

AFAIK none of the known hardest puzzles in T&E(2) has a short solution (or we don't have the same definition of "short"); at best, they have (nearly) initial eliminations based on smart exotic patterns.

champagne wrote:In the data base of "potential hardest", to day including more than 30 000 puzzles
. more than 20 000 have an exocet pattern
- about 25 000 have one or several of the following...

Having some special pattern at (or near) the start is an interesting thing; but again AFAIK using such patterns is very far from being enough to get a simple solution of the hardest puzzles.
However, one of the things I can compute is how much using it makes the puzzle simpler (in my classification). See my forthcoming examples from the EasterMonster family.

champagne wrote:what is, seen by your tool, the percentage of puzzles eligible to the last class in that lot

This is one thing I haven't tried yet.


Finally, I would not use the word statistics about any of the existing collections of hard puzzles.
These collections are all strongly biased, for a very simple reason. When a new pattern is discovered in a puzzle P, lots of people produce variants of P and many of these variants end in the collections. Even Eleven's collection (which has been my main source of analysis) is probably biased, because he started from the known hardest; it is probably less biased than other manually assembled collections. I'm also aware of the meta-collection you compiled later (including Eleven's puzzles), but I've only analysed the top of it, for SER 11.9 to 11.6 included.


Contrary to you, my focus is on general classifications and on puzzles that have no special pattern. My way of taking special patterns into account is to see how they (occasionally) change the universal classifications.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Using classifications to analyse the impact of exotic patter

Postby denis_berthier » Tue Mar 20, 2012 6:06 pm


Applying the classification approach to the analysis of the impact of exotic patterns





1)The BpB and BB ratings


For any 1 <= p <= infinity, the BpB rating of a puzzle P is the minimum n such that P can be solved by Bp-braids of total length <= n.
If p= infinity (i.e. we put no a priori restriction on the lengths of the inner braids), we call it simply the BB rating.

Having a finite BB rating is equivalent to being in T&E(2). The BB rating is therefore finite for all the known puzzles (and probably for all the puzzles).
Moreover, all the known puzzles (and probably all the puzzles) have a finite B7B rating.



2) Two different classification systems

The universal BB rating leads to a classification of all the puzzles (according to the minimal length of the B-braids necessary), a classification which is similar to the B rating (whose associated classification is limited to puzzles in T&E(1)).

Now, one can also define a different classification. It is rougher but much easier to compute: given any puzzle P, one can look for the smallest integer p such that P can be solved by Bp-braids. By convention, we set B0B = B, i.e. ordinary braids. B1B corresponds to g-braids. (In practice, one will always have p<=7).

This classification has a pure logical meaning: contrary to ordinary braids that rely only on contradictions obtained from a single candidate, B-braids must rely on intermediate contradictions obtained between pairs of candidates (bi-braid contradictions). And Bp-braids rely on such bi-braid contradictions obtained by bi-braids of length <= p.
Each of the bi-braid contradictions used in a Bp-braid elimination can be considered as a lemma used by the proof of this elimination.
p is the maximal length of such proofs (considered as bi-braids patterns) needed in Bp-braids.

Inside each of the BpB layers, a sub-classification can be defined, by the minimal length of the Bp-braids necessary to solve a puzzle.


3) Examples from the EasterMonster family

The famous Easter Monster (SER 11.6) itself is in B6B.

Code: Select all
1.......2
.9.4...5.
..6...7..
.5.9.3...
....7....
...85..4.
7.....6..
.3...9.8.
..2.....1

One kind of questions the above classification allows to answer is, if we add SK-loops in the resolution theories, does this lead to a much simpler positioning of the reduced puzzle (with 13 candidates eliminated) in this classification. In the present case, the answer is yes: it is brought down to B2B.


In the EM family, there appears to be a puzzle with still more beautiful symmetries in the pattern of given cells. I don't know where it was first published and if it has received all the attention it deserves. It is due to Mike Metcalf. It is one of the 3 puzzles I've found to be in B7B (I'll speak of the other 2 another day). It is thus harder than Easter Monster (according to my classification and according to SER: 11.8).

Code: Select all
5.......9
.2.1...7.
..8...3..
.4.6.....
....5....
...2.7.1.
..3...8..
.6...4.2.
9.......5


Same question as before. After elimination of 10 SK-loop candidates, it is brought down to B4B. Conclusion: even after SK-loop eliminations, it remains a very complex puzzle.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

How the BpB classification correlates with other ratings

Postby denis_berthier » Wed Mar 21, 2012 4:42 am


How the BpB classification correlates with other ratings


I'll consider the top5 elements of the most usual 5 ratings, as taken from the 1st post in tarek's "hardest" thread (as of 26 Jun 2011): http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539.html
I just added the last information on each line (in bold), giving the smallest p such that the puzzle is in BpB.
The format is: puzzle; name of puzzle (if any); author or collection; ER/EP/ED or [ER; other rating]; BpB

top5 SER
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....; Golden_Nugget-pearly6000-1812; tarek; 11.9/11.9/11.3; in B5B
12.3.....4.....3....3.5......42..5......8...9.6...5.7...15..2......9..6......7..8; Kolk; eleven #2; 11.9/11.9/9.9; in B5B
12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7; Patience; eleven #3; 11.9/11.9/2.6; in B7B
..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5.; Imam_bayildi; eleven#4; 11.9/1.2/1.2; in B5B
1.......9..67...2..8....4......75.3...5..2....6.3......9....8..6...4...1..25...6.; ; eleven#5; 11.8/11.8/11.6; in B6B

top5 Q1
12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98; Discrepancy; eleven; 10.4; q1= 99529; in B2B
12.3.....34....1....5......6.24..5......6..7......8..6..42..3......7...9.....9.8.; Cigarette; eleven; 10.8; q1= 99495; in B4B
.......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...; Platinum_Blonde; coloin; 10.6; q1= 99486; in B3B
.2..5.7..4..1....68....3...2....8..3.4..2.5.....6...1...2.9.....9......57.4...9..; Cheese; eleven; 11.3; q1= 99432; in B4B
........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........; Fata_Morgana; tarx0001; 10.8; q1= 99420; in B3B

top5 Q2
12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8; Red_Dwarf; eleven; 10.6; q2= 99743; in B3B
12.3.....34....1....5......6.24..5......6..7......8..6..42..3......7...9.....9.8.; Cigarette; eleven; 10.8; q2= 99587; in B4B
12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98; Discrepancy; eleven; 10.4; q2= 99578; in B2B
.......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...; Platinum_Blonde; coloin; 10.6; q2= 99551; in B3B
.2..5.7..4..1....68....3...2....8..3.4..2.5.....6...1...2.9.....9......57.4...9..; Cheese; eleven; 11.3; q2= 99516; in B4B

top5 Suexrat9
..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..; ;coloin-eleven#6539; 11.0; suex9= 10364; in B3B
1...5......7..9.3...9..754...4..3.7..6........9.8........79..2......24.3..2......; ; eleven#2548; 11.2; suex9= 9968; in B3B
..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686....4...7.....5..; ; eleven#6540; 11.0; suex9= 9453; ; in B3B
..3......4...8..36..83..1...4..6..73...9..........2..5..4.7..686........7.....5..; ; eleven#8518; 10.9; suex9= 9195; in B2B
..3.9....4...8..36..8...1...4..6..73...9..........2.....4.7..686........7.....5.4; ; coloin; 10.4; suex9= 8946; in B2B

top5 Suext
..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..; ; eleven#6539; 11.0; suext= 5796; in B3B
..3......4...8..36..83..1...4..6..73...9..........2..5..4.7..686........7.....5..; ; eleven#8518; 10.9; suext= 5693; in B2B
1...5......7..9.3...9..754...4..3.7..6........9.8........79..2......24.3..2......; ; eleven#2548; 11.2; suext= 4969; in B3B
..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686....4...7.....5..; ; eleven#6540; 11.0; suext= 4931; in B3B
1..4....9.56..9.......1..6..6....8..5....4.9.9....5.1..7....2..6....1.5....3.....; ; eleven#25832; 10.6; suext= 4743; in B2B

What does this show?
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.
However, it can also be seen that SER doesn't do it very well: puzzles in B5B appear in its top5 list, whereas there are many known puzzles in B6B (and two other known ones in B7B).

You can also see the second of the previously announced 3 puzzles in B7B, published by eleven (#3 in his list).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Pattern-based classification of (hard) puzzles

Postby champagne » Wed Mar 21, 2012 8:49 am

may be one example to show again how complex is the "hardest" rating.
but this is not more than rewording some discussions that took place in the thread of "hardest "

If I understand your rating target, that puzzle

Code: Select all
12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7; Patience; eleven #3; 11.9/11.9/2.6; in B7B


will be in the top list of hardest.

It happens that that puzzle has a multi-fish pattern on digits 2789.
Ronk would find it in less than one hour

This leads to 24 eliminations and, after really basic moves (not exceeding effect of a naked pair)
we end in that position

Code: Select all
 
__ A____ B_____ C____ |D___ E____ F____ |G____ H____ I____
1||1     2      89    |3    789   6     |789   45    45
2||4     389    5     |2789 2789  1     |6     379   38 
3||3     7      6     |89   4     5     |489   2     1 

4||6     589    2789  |1    279   4     |3     57    258 
5||2789  189    4     |5    3     79    |278   167   1268 
6||2357  135    1237  |267  267   8     |2457  145   9

7||2789  3689   2789  |4    5     79     |1    369   36
8||579   1456   179   |679  1679  3     |2459  8     2456
9||359   13456  139   |689  1689  2     |459   3456  7



from that point, Sudoku Explainer solves with a maximum rating of 8.3. Any skilled player can do that.

As I wrote in the hardest puzzle thread, a rating tool putting in the short list some puzzles having one "easy" solution would have a low credibility.


May be some more comments to close my contribution to that topic.

============

More symmetry has a tendency to give harder puzzles
But more symmetry gives a higher chance to get one of these patterns you consider as "exotic"

At the end, as seen in statistics, a big majority of classified "potential hardest" puzzles have one of these "exotic" patterns

But surely hardest puzzles are in some sense "exotics".

============

For sure, found "potential hardest" puzzles is a biased part of the whole family, but

. I doubt many more will be found with 20 clues
. I think much more than 50% of the 21 family is there
. A significant part of the 22 clues family is there
. for higher number of clues, the chances to be in the top list, from what I can see, are decreasing quickly.
my best SE rating so far in the 23 clues family is 11.6

champagne
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Re: Pattern-based classification of (hard) puzzles

Postby denis_berthier » Wed Mar 21, 2012 12:20 pm

champagne wrote:If I understand your rating target, that puzzle
Code: Select all
12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7; Patience; eleven #3; 11.9/11.9/2.6; in B7B
will be in the top list of hardest.
It happens that that puzzle has a multi-fish pattern on digits 2789.
...
from that point, Sudoku Explainer solves with a maximum rating of 8.3.

In my approach, what this example shows is that the pattern you mention is efficient for this puzzle (and probably for the many others in your database obtained by small variations that don't destroy it).

champagne wrote:a rating tool putting in the short list some puzzles having one "easy" solution would have a low credibility.

I can't discuss this, as it is self contradictory. In the two parts of your sentence, you are implicitly referring to different rating views.
Moreover, it seems you are supposing that a "credible" rating has to take into account all the known resolution rules and all those that could be found some day in the future. This is clearly absurd.

In my view, there is no final unique rating (in CRT, I define several ratings). As I stated previously, the classification system I've introduced provides a universally valid account of the logical complexity of a puzzle based on generic rules - but the counterpart of this universality is that it can be improved in particular cases by specific rules. The concrete positive consequence is that this provides a measure of how much a specific rule simplifies a specific puzzle.

champagne wrote:More symmetry has a tendency to give harder puzzles

It's only a tendency to give harder puzzles, not a tendency to give the hardest. It does in no way imply that the really hardest puzzles have symmetries.

champagne wrote:At the end, as seen in statistics, a big majority of classified "potential hardest" puzzles have one of these "exotic" patterns

People tend to look for puzzles with symmetries or exotic patterns. When one is found with high SER, thousands of variations on it are produced. I wouldn't speak of statistics on so biased samples.

As a result, the end of your post is personal opinion based on strongly biased evidence, so I won't enter into details.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

a graphical representation of the BpB classification

Postby denis_berthier » Wed Mar 21, 2012 12:38 pm



A graphical representation of the BpB classification


Code: Select all

 |-  Solvable by singles = in T&E(0)
 |     
 |-  Solvable by braids = in T&E(1)
 |     
 |-  Solvable by B-braids =  in T&E(2) (less than 1 puzzle in 10,000,000)
 |     |
 |     |- Solvable by B1-braids = solvable by g-braids = in T&E(whips[1], 1) = in T&E(basic interactions, 1)
 |     |
 |     |- Solvable by B2-braids = in T&E(B2, 1)
 |     |
 |     |- Solvable by B3-braids = in T&E(B3, 1)
 |     |
 |     |- Solvable by B4-braids = in T&E(B4, 1)
 |     |
 |     |- Solvable by B5-braids = in T&E(B5, 1)
 |     |
 |     |- Solvable by B6-braids = in T&E(B6, 1)
 |     |
 |     |- Solvable by B7-braids = in T&E(B7, 1)
 |     |
 |     |- ??? more levels needed (unlikely)

where Bn is the resolution theory based on braids of length ≤n

Notice that in each of the Bp-braid levels, a further classification could be introduced, based on the minimum length of the Bp-braids necessary to solve a puzzle at this level.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

one's top is not another's top

Postby denis_berthier » Thu Mar 22, 2012 4:31 am


one's top is not another's top


His selection criteria remain unclear to me, but, just because my Mac was hungry for more puzzles, I've computed the BpB classification (in bold) of Champagne's top 27.
None of the 3 B7B puzzles and none of the 60+ B6B appear in this short list. :|

#1 ..34......5...9...7...2...62...7..1..9...5......3....8..1.6...78......21......4.. 4024 Eleven L406 11.10 11.10 3.40 9 881 B4B
#2 1.......9.5.1...3...8..34...1.5.......9..8..2....6..7.3....4..8..2.......8..7..6. 3411 Eleven 3174 11.10 11.10 10.80 9 785 B4B
#3 1.......9..67...2..8....5.......83.....2...64..7.4..1...462....5..8......9...3... 889 Eleven L59 11.30 11.30 9.50 9 607 B4B
#4 1..4..7....7.8...6.9.......2..3......4...71....5.4..2..3.9..4......6...8..2....5. 7417 Eleven H193 10.80 10.80 10.80 9 592 B4B
#5 98.7.....65....4....3.6....7..5..8......2..5......1..6.4.8..9....9.....3....1..2. 10216 GPenet 22ky5 10.70 10.70 3.40 9 580 B4B
#6 ..3.5.....5.1....68....7....6..9...57....2.4...5...1........8.......4.2...9.3...1 1362 Eleven 413 11.30 1.20 1.20 9 505 B4B
#7 .2.4.......7.8...6.....3.5...9.6...1.....23.....5...4...1...8..6...1...797....... 243 Eleven 258 11.40 11.40 11.30 8 23459 884 B5B
#8 ...45.........9.3.6...375...4....1....8.....29...6..7.3....5.9...2...8...1..7.... 620 Eleven 890 11.30 11.30 10.60 8 12348 829 B5B
#9 ..3..6.8.4.....2......3.5....89...3.5...7...4.....1....6.8...9.7...2......1..3... 2780 Eleven 1126 11.20 1.20 1.20 8 12457 790 B4B
#10 ....5...94..1...3..6.7..1....59......8..7.......5.2..73......6...8.9...2.1....4.. 2051 Eleven 1452 11.20 11.20 9.90 8 13456 542 B4B
#11 98.7.....6.....9....5....7..4..3..2...85..4.......4..1..69..5......2...3.....1.4. 35 GPenet H4 11.70 11.70 11.30 7 1234 852 B4B
#12 .2.4.......7.8...69......5...8...6.15....1.9.....7...3........7.4.2.......1.6.3.. 1263 Eleven 510 11.30 1.20 1.20 7 2459 670 B3B
#13 1...5.7..........6..83...4...4.....7.3.2....4......92......15..7...9......26....8 3909 Eleven 2788 11.10 11.10 9.40 7 1579 529 B3B
#14 98.7.....7...6......5..97..5....69....43...6.....2...1.5...48.....6...3.....1...2 14596 GPenet kz1a 11.40 11.40 11.30 7 1236 525 B4B
#15 .......89.5.1.....6....31...7...16......9..2...8.....4..4.2....7..5..3...6...7... 3329 Eleven 991 11.20 1.20 1.20 5 2489 713 B4B
#16 1....6....5.........82....4..98..3...6...5.7.........27....2.1...2.4.9.3...3..... 1102 Eleven 837 11.30 11.30 2.60 4 12567 619 B4B
#17 1....6.......8.2....97....5.3.9....4..5....9.....2.1....4.....7.9.3...4.8.....6.. 1582 Eleven 567 11.30 1.20 1.20 3 1268 914 B5B
#18 .......8....1.9..66...2...4.7...8.9.5..........4.3...73.2.....5..5.6.3...1.....7. 3218 Eleven 997 11.20 1.20 1.20 3 1789 876 B5B
#19 98.7.....7...8.6....5..4...6..3..9...9.....2...4..1..6.3.8..7.......2.1.........5 227 GPenet H29 11.50 1.20 1.20 3 1245 858 B5B
#20 .....6.8.4..7....3.9..3.....1..4...73..1.......8..52...3.9....4......5....2....6. 4891 Eleven 1905 11.10 1.20 1.20 3 2568 734 B5B
#21 .2.4....9..7......8....2.1...1..5.7..6..9...5...2..........8.5....36...2.3..2.6.. 4993 Eleven 2354 11.10 1.20 1.20 3 1578 730 B4B
#22 98.7.....7...6......5..87..5....69....43...6.....2...1.5...48.....6....3....1..2. 12120 GPenet kz0 11.70 11.70 11.30 3 1236 637 B5B
#23 ........9..71...6.....3.1.42..6...1...5.......8...43..5......2.6.17......9...8... 1690 Eleven 301 11.30 1.20 1.20 3 3489 621 B5B
#24 .2...67..4...8......9.....1..1.....8...2..6...6...3.5......5.2..7.6..3..9...4.... 4582 Eleven 2279 11.10 1.20 1.20 3 1489 529 B4B
#25 1...5......7..9..6.983.......67....8.8.......5...4..2.....3.1...3.9....7.....2.4. 3173 Eleven 1405 11.20 1.20 1.20 3 1245 519 B4B
#26 ...4..7..4...8...6..9..2.......3...83..8..4...18....5..9.....1.7..6....3..2..5... 2926 Eleven L294 11.20 1.20 1.20 3 1259 506 B4B
#27 ....5...94..1..2.......7...2.8.1.6....62......7......3.3..9..5.8..........28..4.. 4971 Eleven 1943 11.10 1.20 1.20 1 3579 780 B3B
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

B?B classification of puzzles with "nothing special"

Postby denis_berthier » Sat Mar 31, 2012 9:17 am



B?B classification of puzzles with "nothing special"


Here is now the B?B classification of the 27 puzzles with "nothing special" in champagne's meta-collection of 3602 hardest with SER >= 11.3

Not that I give much credit to this list, resulting from his claim that the hardest puzzles can be made easy by applying some exotic pattern (SK-loop, multi-fish) or vaguely defined procedure (exocet).

I've already given the example of Mike's puzzle in the EM family. This particular puzzle is made easier by the application of an SK-loop; but it only passes from B7B to B4B; sure, this is easier, but very far from easy. Similarly, EM passes from B6B to B2B. AFAIK, there had never before been any evaluation of the impact of the SK-loop. (In this, I used my formal interpretation of an SK-loop as an x2y2-chain.)

I wanted to check similarly a few puzzles presented as having exocets. But I've been unable to find any definition of an exocet. The best I've found is a tentative definition by Blue on the Programmer's forum (http://www.setbb.com/phpbb/viewtopic.php?t=2068&start=5&mforum=sudoku). Unfortunately, he received no clear answer to his proposal: only a few words making exocet something partly specified by a pattern and partly by a vague procedure involving unavoidable sets (http://www.setbb.com/sudoku/viewtopic.php?t=2068&start=14&mforum=sudoku).


Anyway, taking the short list of puzzles that champagne himself considers as having "nothing special", the following shows that they can be very complex. This shatters to pieces the myth that really hard puzzles can be made easy by applying them a few exotic patterns or vague procedures.


#1 1....6.......8.2....97....5.3.9....4..5....9.....2.1....4.....7.9.3...4.8.....6.. 1582 eleven 567 11.30 1.20 1.20 914 B5B
#2 .2.4.......7.8...6.....3.5...9.6...1.....23.....5...4...1...8..6...1...797....... 243 eleven 258 11.40 11.40 11.30 884 B5B
#3 ..34......5...9...7...2...62...7..1..9...5......3....8..1.6...78......21......4.. 4024 eleven L406 11.10 11.10 3.40 881 B4B
#4 .......8....1.9..66...2...4.7...8.9.5..........4.3...73.2.....5..5.6.3...1.....7. 3218 eleven 997 11.20 1.20 1.20 876 B5B
#5 98.7.....7...8.6....5..4...6..3..9...9.....2...4..1..6.3.8..7.......2.1.........5 227 GPenet H29 11.50 1.20 1.20 858 B5B
#6 98.7.....6.....9....5....7..4..3..2...85..4.......4..1..69..5......2...3.....1.4. 35 GPenet H4 11.70 11.70 11.30 852 B4B
#7 ...45.........9.3.6...375...4....1....8.....29...6..7.3....5.9...2...8...1..7.... 620 eleven 890 11.30 11.30 10.60 829 B5B
#8 ..3..6.8.4.....2......3.5....89...3.5...7...4.....1....6.8...9.7...2......1..3... 2780 eleven 1126 11.20 1.20 1.20 790 B4B
#9 1.......9.5.1...3...8..34...1.5.......9..8..2....6..7.3....4..8..2.......8..7..6. 3411 eleven 3174 11.10 11.10 10.80 785 B4B
#10 ....5...94..1..2.......7...2.8.1.6....62......7......3.3..9..5.8..........28..4.. 4971 eleven 1943 11.10 1.20 1.20 780 B3B
#11 .....6.8.4..7....3.9..3.....1..4...73..1.......8..52...3.9....4......5....2....6. 4891 eleven 1905 11.10 1.20 1.20 734 B5B
#12 .2.4....9..7......8....2.1...1..5.7..6..9...5...2..........8.5....36...2.3..2.6.. 4993 eleven 2354 11.10 1.20 1.20 730 B4B
#13 .......89.5.1.....6....31...7...16......9..2...8.....4..4.2....7..5..3...6...7... 3329 eleven 991 11.20 1.20 1.20 713 B4B
#14 .2.4.......7.8...69......5...8...6.15....1.9.....7...3........7.4.2.......1.6.3.. 1263 eleven 510 11.30 1.20 1.20 670 B3B
#15 98.7.....7...6......5..87..5....69....43...6.....2...1.5...48.....6....3....1..2. 12120 GPenet kz0 11.70 11.70 11.30 637 B5B
#16 ........9..71...6.....3.1.42..6...1...5.......8...43..5......2.6.17......9...8... 1690 eleven 301 11.30 1.20 1.20 621 B5B
#17 1....6....5.........82....4..98..3...6...5.7.........27....2.1...2.4.9.3...3..... 1102 eleven 837 11.30 11.30 2.60 619 B4B
#18 1.......9..67...2..8....5.......83.....2...64..7.4..1...462....5..8......9...3... 889 eleven L59 11.30 11.30 9.50 607 B4B
#19 1..4..7....7.8...6.9.......2..3......4...71....5.4..2..3.9..4......6...8..2....5. 7417 eleven H193 10.80 10.80 10.80 592 B4B
#20 98.7.....65....4....3.6....7..5..8......2..5......1..6.4.8..9....9.....3....1..2. 10216 GPenet 22ky5 10.70 10.70 3.40 580 B4B
#21 ....5...94..1...3..6.7..1....59......8..7.......5.2..73......6...8.9...2.1....4.. 2051 eleven 1452 11.20 11.20 9.90 542 B4B
#22 1...5.7..........6..83...4...4.....7.3.2....4......92......15..7...9......26....8 3909 eleven 2788 11.10 11.10 9.40 529 B3B
#23 .2...67..4...8......9.....1..1.....8...2..6...6...3.5......5.2..7.6..3..9...4.... 4582 eleven 2279 11.10 1.20 1.20 529 B4B
#24 98.7.....7...6......5..97..5....69....43...6.....2...1.5...48.....6...3.....1...2 14596 GPenet kz1a 11.40 11.40 11.30 525 B4B
#25 1...5......7..9..6.983.......67....8.8.......5...4..2.....3.1...3.9....7.....2.4. 3173 eleven 1405 11.20 1.20 1.20 519 B4B
#26 ...4..7..4...8...6..9..2.......3...83..8..4...18....5..9.....1.7..6....3..2..5... 2926 eleven L294 11.20 1.20 1.20 506 B4B
#27 ..3.5.....5.1....68....7....6..9...57....2.4...5...1........8.......4.2...9.3...1 1362 eleven 413 11.30 1.20 1.20 505 B4B
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: B?B classification of puzzles with "nothing special"

Postby ronk » Sat Mar 31, 2012 12:14 pm

denis_berthier wrote:Not that I give much credit to [edit: champagne's] list, resulting from his claim that the hardest puzzles can be made easy by applying some exotic pattern (SK-loop, multi-fish) or vaguely defined procedure (exocet).
...
Anyway, taking the short list of puzzles that champagne himself considers as having "nothing special", the following shows that they can be very complex. This shatters to pieces the myth that really hard puzzles can be made easy by applying them a few exotic patterns or vague procedures.

By "nothing special", I think champagne meant his program found "no known exotic pattern." Other "exotic patterns" may yet be found.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: B?B classification of puzzles with "nothing special"

Postby denis_berthier » Sat Mar 31, 2012 1:27 pm

ronk wrote:By "nothing special", I think champagne meant his program found "no known exotic pattern." Other "exotic patterns" may yet be found.

Undoubtedly, other exotic and vaguely defined resolution procedures such as the exocet will be found.
It is great that some people have fun in looking for such things through the detailed examination of examples.
Maybe it'd be still greater if it eventually led to precise definitions of new patterns.

In my approach, the backbone of a classification or rating system (which is the topic of this thread) cannot rely on such patterns. It has to keep some generality. Only in such an approach can the impact of these specific patterns (if they ever become properly defined) somehow be evaluated.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: B?B classification of puzzles with "nothing special"

Postby ronk » Sat Mar 31, 2012 2:02 pm

denis_berthier wrote:It is great that some people have fun in looking for such things through the detailed examination of examples.
Maybe it'd be still greater if it eventually led to precise definitions of new patterns.

You seem to have fun writing "precise definitions", so feel free to write one for an exotic pattern of your choice.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: B?B classification of puzzles with "nothing special"

Postby denis_berthier » Sat Mar 31, 2012 2:37 pm

ronk wrote:You seem to have fun writing "precise definitions", so feel free to write one for an exotic pattern of your choice.


http://forum.enjoysudoku.com/x2y2-belts-t5894.html
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: B?B classification of puzzles with "nothing special"

Postby champagne » Sat Mar 31, 2012 5:26 pm

denis_berthier wrote:
ronk wrote:You seem to have fun writing "precise definitions", so feel free to write one for an exotic pattern of your choice.


http://forum.enjoysudoku.com/x2y2-belts-t5894.html


We have a French proverbial sentence to summarise that

Why should you make it simple if you can make it complex.

The SKloop is a very simple pattern. Few lines can describe it.

My solver looks for all alternative patterns of the family, but I have never identified one of them.

Definitely, this thread is not for me.


champagne
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Next

Return to Advanced solving techniques