The New Sudoku Players' Forum

[Paquita]

Indeed Denis, this procedure does not change the solution.
Maybe I did not understand your challenge. What kind of procedure do you have in mind that might generate high BxB from T&E(3) puzzles?
In the procedure that I described I assume that some kind of vicinity search must be used, other than this one. But preferably while preserving the tridagon. (Instead of generating a lot more puzzles of which only some just happen to have kept the tridagon)
What did you mean by "procedure (that needs to take one out of the given solution grid)" ?

[denis_berthier]

Hi Paquita

Indeed Denis, this procedure does not change the solution.
Maybe I did not understand your challenge. What kind of procedure do you have in mind that might generate high BxB from T&E(3) puzzles?

Actually, that's the whole point of the challenge: finding such a procedure - or perhaps just describing in detail the procedure you are using - because you do succeed in generating such puzzles and the starting point was the T&E(3) puzzles. By "you", I mean you, Hendrik and coloin.

What did you mean by "procedure (that needs to take one out of the given solution grid)" ?

Indeed, it's just a reminder that the T&E(3) and BxB≥7 sets of solution grids are almost disjoint; so it's better to concentrate on a procedure that produces different solution grids.

In the procedure that I described I assume that some kind of vicinity search must be used, other than this one. But preferably while preserving the tridagon. (Instead of generating a lot more puzzles of which only some just happen to have kept the tridagon)

Yes, this is indeed the heart of the question. I've been thinking about it but I don't see how to do it while still using gsf's program for minimisation. (That's why I asked if you used this program.)
If you add any clue from the solution grid, you get into the problem in the previous paragraph.
If you add a clue (say a non-tridagon one) not from the solution grid, you get an inconsistent puzzle and minimisation via gsf doesn't work. As a result, before applying minimisation, you also need to delete at least one other clue in order to get back to a consistent puzzle. Is there a smart way of doing it? I guess this is what you call "some kind of vicinity search" and this is probably the most interesting part of the procedure.

.

[Paquita]

Further thoughts on the challenge

I went back to the start of this thread, as the question is how to generate BxB>6 puzzles. This is related to the length of inner braids. Calculating BxB was proposed as a way to measure hardest puzzles, alternative for SER.

Quote :
"one more geenral conclusion is, the SHC allows much better computation times than the SER (or even its PGXplainer variant) and it could replace it in the search of the hardest T&E(2) puzzles."

This was a conclusion while no BxB>7 was known. It is no longer true, the SER or its quicker alternative skfr is much faster than SHC. There are differences per system of course, but in my PC a typical B10B takes between 30 minutes and 2 hours. And B9B and B11B are almost equally timeconsuming. The funny thing is that the B14B costs much less time. This may be reflected by the observation that a typical B10B is skfr 11.6 or 11.7, and B14B is skfr 11.2. These are not incidents but overall results. If we choose not to compare the BxB to skfr anymore, the anomaly remains that B10B is the most calculation consuming, and not B14B.

Now it seems almost impossible to use the BxB rating on most T&E(2) puzzles. If they rate higher with skfr, they usually have a low BxB, <7. In other words, by using the BxB rating the number of puzzles that rate high is radically diminuished.

I can understand the desire for a clean criterium for rating. If the length of braids is the sole test, that is cleaner than the SER or skfr that test for several complex constellations in a puzzle.
Now that it has been used, and higher BxBs have been found, what is the evaluation? I it indeed a better rating instrument? Are the rare B14Bs indeed the hardest puzzles?

I looked at Champagnes tridagon puzzles, they are skfr rated. A lot of T&E(2) with tridagons, and almost no BxB>6. Or at miths T&E(3), also with tridagons, but as it now seems, to get higher BxBs from them with vicinity search is a rare occurence.

I was looking at the early posts of this thread, to see if I can find an answer to the question : what defines a high number of inner braids? Is this a certain constellation, like the tridagon is? Even, a constellation in addition to a tridagon, or a certain kind of tridagon?

[denis_berthier]

.
Hi Paquita

Many topics in a single post.

The main point is about goals: do you want to mine for coal or for diamonds? Same atoms, different substance. Also different quantities to be expected and different worths. High BxB puzzles are very rare; one of these diamonds is worth tons of high SER coal.

For decades, puzzle diggers have mined for millions of high SER puzzles and the collector-in-chief has merely stuffed them into a large database. This has left thousands of puzzles in it with a tridagon undetected for more than 10 years. Now, this approach starts to apply mith's idea of expansion by Singles and re-minimisation, in combination with Methuselah's old idea of vicinity search. And high SER puzzles can easily be found by millions to fill up some google drive. Apart from the quantity, what's new?

The SER and its alternative implementations rely on no theoretical ground; the SER is a hotpot of rules of different kinds (not even popular ones) assigned arbitrary ratings. Find an anomaly in a collection, you can't use it to conclude anything, except that it may be due to an arbitrary threshold in the SER (see [PBCS] for an example) or to some new type of its rules starting to be used in the rating - or to uniqueness...
I haven't studied the anomaly you mention about the low SER of high BxB puzzles. But mith has done it for T&E(3) puzzles. It was almost always due to the uniqueness rules in the SER. A purely artificial cause. Did you try to eliminate uniqueness rules in your calculations?

On the other hand, after his use of expansion by Singles and of T&E-depth as the unique filter in vicinity search, mith could find millions of T&E(3) puzzles - and a non-circular conclusion could be drawn: they all have a tridagon. (Non-circular, because the tridagon was not part of the search criteria.)

T&E-depth, B, BxB, BxBB have intrinsic, purely structural meanings. They are defined in purely logical terms. (Not only the SER IS NOT, but IT CANNOT BE defined so.) It's anyone's choice to decide if they want to build on solid foundations or on quicksands.
Like the SER, these classifications rely on the notion of the hardest step and they exclude the number of times this step needs to be reached in the solution. It is therefore inherent both in them and in the SER that the computation times for a fixed value have a very large variance and a puzzle with a lower value may indeed take much more time than a "harder" one. It is also the case that the most extreme values often require shorter computation times than intermediate ones, because there are fewer possibilities for many non-visible useless partial chains of smaller lengths to be present.

There's a reason why I call T&E-depth, B, BxB, BxBB classificationS and not ratings.
When one talks of A rating, there is always the totalitarian view that it must hold the ultimate truth about the difficulty of a puzzle. See how SER worshippers behave about it! The best of it is when the words "rating" and/or "hard" are used twice in the same sentence with different meanings.

About the challenge, it didn't include any "smart" condition. This word came out in our discussion, but it may be ill advised to add it to the challenge - in particular if that leads to adding tridagon condition that would make the conclusion that all the B7B+ have a tridagon circular.

Some practical note: when you are looking for high BxB puzzles, this can be done in stages. Do all the search with the fast-to-compute condition BxB ≥ 7 *. You get rough diamonds. At the end, do a precise BxB computation to determine their worth.
(*) in SHC, this can be done by choosing max-length=6 and buffer-size large. Any puzzle with BxB≥7 will get the -3 value, which will mean BxB>6 (if you have previously filtered for T&E(2) puzzles).
.

[Paquita]

Thank you Denis for such an elaborate answer.

What about the non-tridagon puzzles? Are they easier puzzles by definition and not worthy to be collected? Or is the collection of sudoku puzzles in itself a hotpot of many types of puzzles. As I said, I understand the desire for a clean rating criterium. Can all puzzles be solved somehow with inner braids? I looked at the site named Phils Folly, where a puzzle can be solved by applying different techniques. I can't identify the inner braids there, are they chains? Is it a solving technique?

[denis_berthier]

What about the non-tridagon puzzles? Are they easier puzzles by definition and not worthy to be collected?

I think I've done enough with puzzles much before there was any tridagon to not need to give an answer.
As for generating hundreds of million more puzzles with no other purpose than storing them in a database, I don't see the interest.

Or is the collection of sudoku puzzles in itself a hotpot of many types of puzzles.

Obviously.

Can all puzzles be solved somehow with inner braids?

If you mean by B-braids, no. B-braids are enough only for T&E(2).

I looked at the site named Phils Folly, where a puzzle can be solved by applying different techniques. I can't identify the inner braids there, are they chains? Is it a solving technique?

Can you give a link?

[Paquita]

https://www.philsfolly.net.au/Sudoku/index.htm

[Paquita]

I think that people try to define what is a hard puzzle. SER or skfr rating them and storing them is a step, to collect hard puzzles so bright minds can study them and come up with definitions of what is a hard puzzle.

You do have some valuable criterium for T&E(2) puzzles. If all T&E(2) puzzles can be solved with it and it is an indication how hard the puzzle is. My question is, does this cover the hardness definition for all T&E(2) puzzles? Or are there other factors in some hard puzzles. For example, the highrated SER 11.9 puzzles that do not have a tridagon are usually BxB<7. Does this mean they are not hard? (I have a vague idea that "hard" means : hard to be solved by a human. Possibly a human who knows the tricks and constellations).

[denis_berthier]

I looked at the site named Phils Folly, where a puzzle can be solved by applying different techniques. I can't identify the inner braids there, are they chains? Is it a solving technique?
https://www.philsfolly.net.au/Sudoku/index.htm

It's a solver among many ones. I've never used it. I see it has lots of familiar patterns, including some chain patterns. In this sense, it's not fundamentally different from the most familiar (to me) Hodoku. The chain patterns seem to be those of the SER (just a first impression). It doesn't have explicit braids or B-braids. I'm not interested in checking the details.

[denis_berthier]

I think that people try to define what is a hard puzzle.

Good luck with this. No two people agree on what "hard" means - not even on whether Hidden Singles are harder or easier than Naked Singles.

ISER or skfr rating them and storing them is a step, to collect hard puzzles so bright minds can study them and come up with definitions of what is a hard puzzle.

First, there's no "SER or skfr rating". There's the SER, which has become some kind of common reference, by default. And there's skfr, the buggy re-implementation of it. (Not that a difference of 0.1 or 0.2 means anything real - but, considering the original goal, the fact is there).
Again, good luck for finding a definition.
About "bright minds studying" the SER rated collections, can you name anyone, apart from me, who really studied them and came out with some result (with references to such studies, please)?

IYou do have some valuable criterium for T&E(2) puzzles. If all T&E(2) puzzles can be solved with it and it is an indication how hard the puzzle is. My question is, does this cover the hardness definition for all T&E(2) puzzles? Or are there other factors in some hard puzzles. For example, the highrated SER 11.9 puzzles that do not have a tridagon are usually BxB<7. Does this mean they are not hard? (I have a vague idea that "hard" means : hard to be solved by a human. Possibly a human who knows the tricks and constellations).

I don't know what "hard" means, even if you add "hard to be solved by a human"; see the first paragraph.
I'm not in the least interested in defining a unique rating for all the puzzles or in defining what "hard to be solved by a human" means.

My classification system is based on a radically different philosophy. It satisfies precise conditions:
- universal (meaningful in any finite CSP);
- pure logic (pattern-based);
- intrinsic (depends only on the puzzle at hand);
- invariant under isomorphisms;
- invariant under expansion by Singles;
- (decreasing) monotonic wrt expansion.

These properties are essential for any systematic work about classification. Two examples:
- when I expand a puzzle, I don't have to wonder whether that can make it "harder"; in SER, it can;
- when I look for the minimals of a puzzle, I don't have to wonder whether some of them can be "easier"; in SER, they can.

I could add one property:
- doesn't depend on oracles (such as uniqueness).

Moreover, for the specific hierarchical classification system I've introduced:
- T&E-depth defines a partition of all the puzzles;
- B is a complete sub-classif of T&E(1);
- BxB is a complete sub-classif of T&E(2);
- BxBB is a complete sub-classif of T&E(3).

Note that the universality condition implies the classifs cannot be based on any pattern that is not meaningful in all the finite CSPs.

Does this cover all the possible definitions of "hardness": NO. And I couldn't care less.

One question: did you try to recompute the SER of your "anomalous" B7B+ ¨puzzles, without uniqueness?
.

[hendrik_monard]

This was a conclusion while no BxB>7 was known. It is no longer true, the SER or its quicker alternative skfr is much faster than SHC. There are differences per system of course, but in my PC a typical B10B takes between 30 minutes and 2 hours. And B9B and B11B are almost equally timeconsuming. The funny thing is that the B14B costs much less time. This may be reflected by the observation that a typical B10B is skfr 11.6 or 11.7, and B14B is skfr 11.2. These are not incidents but overall results. If we choose not to compare the BxB to skfr anymore, the anomaly remains that B10B is the most calculation consuming, and not B14B.

These long durations for BxB calculations remind me of the time when the 'old' BxB calculation was used. Did you already download the new version? It is considerably less time consuming.
Regarding your observation on B14B puzzles: can one talk about a typical B14B when all known B14B puzzles have been derived directly or indirectly from the same original one? This could also explain the fact that they share the same skfr rating.

[Paquita]

Hendrik : where can I download the new version? Is it here https://github.com/denis-berthier/Sudoku_Hierarchical_Classifier

Denis : I am just trying to get closer to an answer for your challenge. To me this means to understand what you are looking for. So I try to understand the rating system of braids. I know you wrote about it but I am looking for a more basic explanation. (I ment you with the Bright mind- I need simpler overviews).
There is not a lot about this online. https://www.reddit.com/r/sudoku/comments/r0hnhk/braiding_analysis/ is it this?

I came across another rating system https://www.nature.com/articles/srep00725 I am not sure if this is a solving technique as well.

The anomaly I was talking about got nothing to do with SER rates, unique or not. It is the fact that B10B takes much longer to compute than B14B. The question I have (but not your question, as I understand) is whether the B10B puzzle is harder. And my other question is, if it is not hardness that you rate, what is it? Are braids the means or the end? You introduced this thread because the BxB was faster than SER. But SER, or skfr (skfr because it is faster and because the differences of 0.1 or 0.2 are not significant) is about hard sudokus (imperfect as it is), isn't it?

Actually collecting puzzles in a database and hope they shed light on the nature of sudokus for some brighter mind, is what I did and what I do. I am hoping you can explain what you search and what you find, if possible so that the less brighter brain can understand it.

(If someone tells me that I found a rare puzzle, it is a nice result. Puzzle digging, indeed. I lack the insight to evaluate the rating system that I use, for example compare SER to BxB. But I do try to understand them, as far as I can)

[denis_berthier]

Hendrik : where can I download the new version? Is it here https://github.com/denis-berthier/Sudoku_Hierarchical_Classifier

Yes

So I try to understand the rating system of braids. I know you wrote about it but I am looking for a more basic explanation.

See the User Manual. There are graphics.

There is not a lot about this online. https://www.reddit.com/r/sudoku/comments/r0hnhk/braiding_analysis/ is it this?

This "braid analysis" has nothing to do with braids.

I came across another rating system https://www.nature.com/articles/srep00725 I am not sure if this is a solving technique as well.

If I remember well, the hardest puzzle he found was solvable by Singles.

The anomaly I was talking about got nothing to do with SER rates, unique or not. It is the fact that B10B takes much longer to compute than B14B.

You've been talking about two anomalies. One is about high BxBs having a low SER. My answer was and is: don't use uniqueness in SER
As for this question B10B vs B14B, I need to check it. If it's true, I've already given a possible explanation.

if it is not hardness that you rate, what is it?

I rate nothing, I classify. See previous answers.
Your question supposes that there is some predefined notion of "hardness".

You introduced this thread because the BxB was faster than SER.

No. I introduced this thread to talk about the BxB classification - as the title says. I've recalled my global motivations in a previous answer.

If someone tells me that I found a rare puzzle, it is a nice result. Puzzle digging, indeed.

And you've been quite successful at it.

I lack the insight to evaluate the rating system that I use, for example compare SER to BxB. But I do try to understand them, as far as I can)

The comparison is hard to make, as the correlation coefficient between the two is not meaningful.
.

[Paquita]

Yes this is a faster version, thank you. Relative speed remains for the values of x in BxB, but overall much faster.

The Nature link is interesting I think. It uses Platinum Blonde as hardest example. It does not use singles:

"our continuous-time dynamical system was designed to solve k-SAT formulae in conjunctive normal form (CNF), we first briefly describe how Sudoku can be interpreted as a +1-in-9-SAT formula and then how it is transformed into the standard CNF form"
However, I have no idea how much time is needed to solve hard puzzles, the software they used is not given in this scientific report.

In the mean time I am reading what you wrote about braids. But I don't see a User manual-where can I find it? I have the "Pattern-Based Constraint ..." pdf.

[denis_berthier]

.
https://www.researchgate.net/publication/388568383_User_Manual_and_Research_Notebooks_for_CSP-Rules_Second_Edition
.