The New Sudoku Players' Forum

Website · by **denis_berthier** » Sun Aug 13, 2023 6:28 pm

Paquita wrote:Do I understand correctly that T&E is Trial and Error,

Yes

Paquita wrote:and that T&E(3) means three recursive steps of brute force are needed to solve it?

Not of brute force, but of T&E.

Paquita wrote:That does sound like a possible rating for hard puzzles.

T&E-depth is a universal rating for all the puzzles, not only the hard ones.

Paquita wrote:But if I am correct, only two puzzles of T&E(3) are now available? (Found by Mith).

Mith has now found 100,000s of them.

Paquita wrote:I would assume we do the T&E rating in addition to SER.

T&E-depth is a very broad classification. Each T&E level has many sub-levels:
T&E(1) is sub-divided by the levels of the B rating
T&E(2) is sub-divided by the levels of the BpB rating
More generally, for any n>0, T&E(n+1) is sub-divided by the T&E(Bp, n), p>0
As of now, all the known puzzles in T&E(3) are in T&E(B2, 2).

SER cuts through all the T&E levels and is largely unrelated to them, especially if you don't delete the uniqueness techniques from it.

When you're looking for hard puzzles, you have to decide which criterion you use. There's no "potential hardest"; that's pure BS; "hardest" is meaningful only wrt to some chosen rating.
The most remarkable result in the past year is the huge number of new puzzles that have been found after using T&E-depth instead of SER as the search criterion. Many of them are also hard wrt the SER, but not all.

Paquita wrote:As for the other approach, the expansion of puzzles by Singles, I do not quite grasp the concept yet. Can anyone explain what it is and how it can be used to rate puzzles?

It is related to generation, not to rating.
In vicinity search, instead of looking for neighbours of the minimal puzzles you have already found, first expand them by Singles, look for the neighbours of the expansions and then look for minimals of these neighbours. This produces many more minimals. The problem is, this produces minimals that have the same expansions, and that's why min-expands become more interesting than minimals.

.

by **Paquita** » Sun Aug 13, 2023 8:01 pm

Thank you Denis for your explanations.

Are the T&E(3) puzzles generally harder, would you say? Now that Mith has found many more, what is typical?

Mith, can I download your batch of these puzzles somewhere?

I do now understand the expansion by singles. Turns out I already knew it. In my scripts, expansion has always been one of the methods that I use. I have large amounts of non-minimal puzzles. One of the more time consuming things is to get rid of all the doublures in these large files. And I have to get rid of them because even when I do most of these large files produce many more new puzzles, partly minimal, partly non-minimal. One non-minimal can produce many minimals this way, and they are all different, usually rated the same, although I still wonder if a minimal puzzle, with less information, might sometimes be harder than the nonminimal it came from.

Website · by **denis_berthier** » Mon Aug 14, 2023 3:54 am

Paquita wrote:Are the T&E(3) puzzles generally harder, would you say? Now that Mith has found many more, what is typical?

T&E(3) puzzles are tautologically harder than T&E(2) or T&E(1) ones wrt T&E-depth - but not always wrt SER.
All the known T&E(3) puzzles have at least one non-degenerate tridagon pattern, with varying numbers of guardians. This can be used to define a new rating, the SFin + W + Trid-OR5W rating, consistent with my old W rating. You can then check that their rating spans a whole range of values - which means that the T&E(3) puzzles, or even the T&E(B2, 2) puzzles, have a large range of "difficulties".
You can find all the details in the last two chapters of [UMNR]: https://www.researchgate.net/publication/372364607_User_Manual_and_Research_Notebooks_for_CSP-Rules).
You can also find the detailed classification results on GitHub: https://github.com/denis-berthier/Classifications-of-TE3-Sudokus.
You can also get some information on this forum:
http://forum.enjoysudoku.com/t-e-3-puzzles-split-from-hardest-sudokus-thread-t40514.html
http://forum.enjoysudoku.com/the-tridagon-rule-t39859.html,
but it's less structured than in [UMNR].

Paquita wrote:Mith, can I download your batch of these puzzles somewhere?

Follow the links here: http://forum.enjoysudoku.com/post328587.html?hilit=expand#p328587
ot here: http://forum.enjoysudoku.com/t-e-3-puzzles-split-from-hardest-sudokus-thread-t40514.html

Paquita wrote:I do now understand the expansion by singles. Turns out I already knew it. In my scripts, expansion has always been one of the methods that I use. I have large amounts of non-minimal puzzles. One of the more time consuming things is to get rid of all the doublures in these large files. And I have to get rid of them because even when I do most of these large files produce many more new puzzles, partly minimal, partly non-minimal. One non-minimal can produce many minimals this way, and they are all different, usually rated the same, although I still wonder if a minimal puzzle, with less information, might sometimes be harder than the nonminimal it came from.

Yes, that's why we need the min-expands (expansions of minimals by Singles). They are the right collection for analysing the difficulties of puzzles without redundancies.

by **JPF** » Mon Aug 14, 2023 10:12 am

Not knowing exactly where to find the latest update of "THE" database, I'm offering the following puzzles in maxlex form just in case:

Code: Select all: 98.76.5..7.5.48....64..9....976.4.8.....87..9....5.....4......3..6...4.2......... ED=11.8/1.2/1.2 98.76.5..7.5.48....64..9....4.....3...6...42............76.4..8...95........87.9. ED=11.8/1.2/1.2 9876.........958.......4...8.9...36..6....2...23....8767.......3.82..69...23.67.. ED=11.8/1.2/1.2 9876.........958.......4...76....3...32....87..9...26.67.......2.83..69...32.67.. ED=11.8/1.2/1.2 9876.........958.......4...8.9...36..6....2...23.6..8767.......3.82..69...23..7.. ED=11.8/1.2/1.2 9876.........958.......4...76....3...32.6..87..9...26.67.......2.83..69...32..7.. ED=11.8/1.2/1.2

JPF

by **Paquita** » Mon Aug 14, 2023 1:57 pm

Yes of course, it is better to rate the expanded ones, and then the high-rated can be processed to give their minimals. So much more easy indeed, why did I not think of that!

Mith, your collection of T&E(3) puzzles, I assume you want to further process them yourself? (To reduce to minimals). But can I use then as seeds for my scripts? If I do and I get many doubles compared to your or Hendriks batches, I might change my scripts. But it will always be some kind of vicinity search, combined with expansion.
I don't know how we can arrange that our script results do not overlap.

by **mith** » Mon Aug 14, 2023 4:04 pm

Paquita wrote:But can I use then as seeds for my scripts?

Of course! This has always been a collaborative effort, I may never have gotten to these puzzles if not starting from champagne's database including puzzles from a large number of contributors.

Given the renewed interest, I'll aim to publish an update soon (I'd stop the scripts now, but I realized a few days ago that one of the scripts wasn't running so it's got a bit more to catch up on).

The expanded database is around 1.07M puzzles, up from 847k last update, all of which are depth 3 (I do calculate the exact depth just in case this somehow generates a depth 4, but I am very confident that no such puzzle exists). Currently:

7 are 11.9 (rated in gsf minlex form; some morph dependency due to a bug in SE)
623 are 11.8 (rated in gsf minlex form)
79 are 40c

These puzzles are expanded in the sense that no digit can be placed by singles. I've posted details of the scripts I run in the other thread, but in summary: I find all minimals of the expanded forms and add to the minimal database if new, and also run a couple of "trivial" operations to generate more expanded forms directly.

The minimal database is around 4.57M puzzles, of which 897 have an 11.8+ expanded form. I run neighborhood searches on these; the resulting puzzles don't need to be minimal, instead I check depth, and if depth 3 expand them first and check against that database.

To prep for an update, I make sure the scripts on the expanded database are finished running (so that I have all the "trivial" modifications published together, and all the minimals generated), then run other scripts to find the min-expands (puzzles which cannot have a digit removed while remaining unique and singles expanded) and max-expands (puzzles which can't have a digit added while remaining depth 3). I also assign some unique ids for the puzzle and the minlex solution grid, and run some checks for the trivalue oddagon pattern (number of guardians for the best triple/box choice). Every puzzle in the database as of last update has the property that there are three digits which appear at most once, all in the same box, with at least one potential trivalue oddagon in the four boxes not aligned with the box containing those givens.

Since all the puzzles in both databases can be trivially generated from the min-expands or max-expands, I publish these smaller collections as well; I haven't been publishing the minimals but I can do that to make it easier to check for new puzzles. It's worth noting that not all of these minimals would qualify for the old ph database using SER, due to uniqueness techniques; about 20k of the expanded forms don't require Dynamic Forcing Chains, and 645 are SER 4.X.

(I'll also make the older ph2010-based database available somewhere, though it does not currently contain the vast majority of depth 3 puzzles. That may take a while longer since it's a bit disorganized and also an order of magnitude bigger.)

by **mith** » Mon Aug 14, 2023 4:07 pm

A longer term goal is to get the depth 3 and ph-style databases online with a form to submit a batch of puzzles and automatically check whether it's already there (and if not add it to a temporary pile for verification), make this more of a distributed effort. Not sure when I'll have the time/energy to tackle that, but it's on my mind.

by **Paquita** » Mon Aug 14, 2023 9:04 pm

Mith : Good ideas!

I currently use minimals to identify puzzles. That is how champagne taught me to do it. One could of course identify the expanded ones instead. It is a choice to make. One minimal has multiple expanded equivalents and one expanded may have several minimals.

As for the ph database, I now use only the 11.6+ puzzles to check against because I also select my output to be 11.6+. Given the large amount of new puzzles since you and Hendrik have been working on it this seems appropriate. So maybe a new version of the database should be only 11.6+. On the other hand, you say you have many T&E(3) with lower rates. So perhaps use 2 criteria : either be 11.6 + SER or be T&E(3), (or both, of course).

Website · by **denis_berthier** » Tue Aug 15, 2023 5:47 am

.
The question of what should be in the databases depends on their purposes: either accumulate puzzles or gain some knowledge on puzzles at different natural levels of complexity. What I have in mind is:
- we have a perfect knowledge of the minimal puzzles in T&E(0): they are solvable by Singles and they represent 29.17% of all the minimal puzzles in unbiased statistics, with 0.06% precision (see [PBCS, chapter 6]);
- we have an almost perfect knowledge of the minimal puzzles in T&E(1): solvable by braids and sub-classified by their B ratings, with a precisely known distribution of these ratings (see also [PBCS, chapter 6]);
- we have a pretty good knowledge of the minimal puzzles in T&E(3) and their sub-classification by their W+OR5W ratings (see [UMRN] or this thread: http://forum.enjoysudoku.com/the-tridagon-rule-t39859.html);
- in spite of having a large database, we have almost no knowledge of the minimal puzzles in T&E(2); what we only have is a highly biased database, developed by many different people with no common goal other than finding high SER puzzles.

About the T&E(3) database, the purpose is to reach some knowledge of T&E(3) minimal or min-expand puzzles. My recommandation is, don't change anything to what mith and Hendrik have been doing (the big change has already occurred at the start, when T&E-depth has been chosen as the search criterion) ; in particular, don't add a SER criterion to further filter puzzles entering the database ; increase it according to the same principles. It's interesting to continue checking if all the puzzles in it have the non-degenerate tridagon pattern (+ guardians) and if they are in T&E(W2, 2).

As for the ph database, its real purpose has always been to accumulate puzzles with some high SER (if you object to this, just check what has been done for decades). I don't have much to say about it: I think, past the accumulation thing, it's a dead end. But I also think:
- its real purpose should be made clear: "find the highest SER minimal puzzles", instead of the repeated BS: "find the hardest puzzles according to some inexistent definition of hardest and that are not really the hardest because they can be solved by exotic patterns";
- as a result, I support Paquita's idea to restrict it to SER ≥ 11.6;
- with the possible introduction of expansions in vicinity search, it will have to deal with redundancies and to have a companion min-expand database;
- moreover, it shouldn't be mixed with puzzles obtained with a different filtering criterion; let this database assume that it is for high SER and don't introduce in it puzzles found by using a totally different search criterion (T&E-depth).

Now, back to the general knowledge of the T&E(2) domain. What type of knowledge can we expect? How can one reach such knowledge? Where to start from?
A good starting point would be a large unbiased collection of T&E(1) puzzles - or a collection with known bias (and, of course, I'm thinking of the controlled-bias collection) -. Starting a vicinity search from this collection, with T&E-depth as the criterion, how many T&E(2) puzzles does one obtain by such or such type of vicinity search?
We know that T&E(2) puzzles are very rare, but less than T&E(3) ones.
.

by **champagne** » Tue Aug 15, 2023 6:58 am

Paquita wrote:Mith : Good ideas!

I currently use minimals to identify puzzles. That is how champagne taught me to do it. One could of course identify the expanded ones instead. It is a choice to make. One minimal has multiple expanded equivalents and one expanded may have several minimals.

Hi Paquita,

Nice to see you back.
Regarding the "minimal" issue, This was not really a concern as long as the search was in the low clues area. The oldest known case of minimal with singles on my side is tarx0104 and tarx105 in the file of potential hardest.

tarx0104 ....5...9..6...1...8.1...4.2....5....9..1..3....2.7.....1...8...4...1.6.9...2...7 11 1.2 1.2
tarx0105 ....5...9..6...1...8.1...4.2....5....9..1..3....2.7.....1...8...4.....6.9...2..17 11 1.2 1.2

With all the work done on the family of puzzles having the "Thor Hammer" pattern, the situation is quite different. The number of clues is usually much higher and the focus is on the place were the Thor Hammer plays the key role, so yes, it makes sense here to merge all puzzles having the same position after singles.

EDIT: In fact, it seems to me that for a manual solver, assuming that applying the Thor Hammer rule lowers significantly the hardness of the puzzle, one interesting point is "how hard is it to reach this point with several gardians". In this case, all "basic moves" can be applied first (leading more or less to SER ED 4.2)

Website · by **denis_berthier** » Tue Aug 15, 2023 7:45 am

mith wrote:The expanded database is around 1.07M puzzles, up from 847k last update, all of which are depth 3 (I do calculate the exact depth just in case this somehow generates a depth 4, but I am very confident that no such puzzle exists).
...
The minimal database is around 4.57M puzzles, of which 897 have an 11.8+ expanded form. I run neighborhood searches on these; the resulting puzzles don't need to be minimal, instead I check depth, and if depth 3 expand them first and check against that database.

I think you meant:
- the expanded database is around 1.07M puzzles, up from 158,276 last update
- the minimal database is around 4.57M puzzle [up form 847k last update)

Or did I miss some update?

by **hendrik_monard** » Tue Aug 15, 2023 9:13 am

As I am not (yet?) able to ascertain depth_3 or TH or trigadon ..., I submit the following intermediate mixed list.

Hidden Text: Show

It starts with an SER 11.9:
9.7.........23.......1...8...5.....18.65...97......56.65...19.8.89..5.7.7.1.....6 11.9/1.2/1.2

by **champagne** » Tue Aug 15, 2023 12:44 pm

hendrik_monard wrote:As I am not (yet?) able to ascertain depth_3 or TH or trigadon ..., I submit the following intermediate mixed list.

with so many clues and such a high SER, I would bet that they all have the TH pattern. a counter example would be very interesting

Website · by **denis_berthier** » Tue Aug 15, 2023 5:40 pm

hendrik_monard wrote:As I am not (yet?) able to ascertain depth_3 or TH or trigadon ...,

All your puzzles have the tridagon pattern with guardians.
Only 43 of them are in T&E(3):

Code: Select all: 7 8 11 12 18 27 34 35 36 37 38 64 71 87 88 106 107 108 109 110 112 114 116 117 118 128 132 133 147 148 149 150 151 152 210 221 222 261 263 271 272 318 355

by **hendrik_monard** » Wed Aug 16, 2023 9:50 am

Hi Denis,
After publishing my list yesterday I noticed that there was a duplicate on position 3. I have removed it through an Edit. It is possible therefore that, if you downloaded the list before my Edit, each number in your list should be decreased by 1. Sorry for this inconvenience.

The New Sudoku Players' Forum

The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)

Re: The hardest sudokus (new thread)