The New Sudoku Players' Forum

[mith]

The depth 3 database is now over 400k expanded forms, and over 2mil minimals. Currently the only script running to generate new "families" is the minimal_reducer (-2+1), which has processed about 920k puzzles. Since restarting it, it's finding new expanded forms at a rate of 1.5-2% of the minimals processed, and it accounts for about 5-6% of the total expanded forms added - the rest are the result of the scripts operating on the expanded forms.

[denis_berthier]

.
Here are the results of quite long calculations. (I had previous results related to the much smaller 972 database, but that was too small to make any conjecture about it.)

All the known 9x9 sudoku puzzles in T&E(3) are indeed in T&E(W2, 2) or less.

All the terms are essential:
1) "sudoku puzzles" excludes sukakus
2) "9x9" excludes larger puzzles
3) "known" means both published (i.e. it refers to the last database published by mith *) and it implies that the proof relies on testing this database (not on a formal proof). Notice that (due to the consistency of the classification wrt adding candidates) testing the 375,759 minimal database has been done by testing only its 63,137 min-expands.

Considering my universal T&E(n) classification of any finite binary CSP-instance and the sub-classifications of each level:
- T&E(1) sub-classified by braids(k)
- T&E(2) sub-classified by Bk-braids or equivalently by T&E(Bk, 1)
- T&E(3) sub-classified by T&E(Bk, 2)
and applying it to 9x9 Sudoku puzzles, we have:
1) all the known puzzles in T&E(1) are in B29 or less (Mauricio's example in B29)
2) all the known puzzles in T&E(2) are in B7B = T&E(B7, 1) or less (3 examples currently known to be exactly in B7B)
3) all the known puzzles in T&E(3) are in B2BB = T&E(W2, 2)

Each of these 3 experimental results relies on a sufficiently large number of test cases to be turned into a conjecture by deleting the word "known". Note that the resulting second conjecture is a modified version of my very old B7B conjecture, before I found that mith's puzzle Loki is not in T&E(2).

Notice however that my T&E(2) and B7B conjectures relied on a database assembled from many independent seeds. The T&E(3) mith database seems to be assembled from a much smaller number of seeds (maybe ultimately only 1: Loki). This leaves some open questions about other seeds in T&E(3).

* 375,759 minimal puzzles not in T&E(2): http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1299.html
and the corresponding databases of 63,137 min-expands and 15,606 max-expands:
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1304.html

[mith]

Something I am intending to do eventually is go back to (my local version of) the ph database and try to determine the earliest T&E(3) puzzles(s) found there, as well as earlier T&E(2) puzzles which show the trivalue oddagon pattern (now that I have a reasonably quick script for determining that).

It's difficult to determine "seeds" precisely in the old database, given how many threads I had running at any time and the overlap between them. A newly discovered noteworthy 26c, say, could have come from a 25-27c seed, and I don't know how valuable it would have been to track that (it could have come from puzzles in all three groups, with the actual lineage just being determined by which happened to run first). Loki itself was not directly the seed for all puzzles in the current T&E(3) database - the original set of 972 puzzles was based on ~200 puzzles found with depth 3 searching the old database with SER 11.3+ - but it would not be at all surprising if they all had some common ancestor (possibly not in T&E(3) itself).

Anyway, I am stalled at the moment because I managed to blow out the PSU on the desktop (possibly from running too many sudoku scripts...) and am waiting for a replacement.

[denis_berthier]

Something I am intending to do eventually is go back to (my local version of) the ph database and try to determine the earliest T&E(3) puzzles(s) found there, as well as earlier T&E(2) puzzles which show the trivalue oddagon pattern (now that I have a reasonably quick script for determining that).

Just to make it clear for those who didn't read the 89 pages of this thread: in the ph2010 database itself, there's no puzzle with T&E-depth 3.
"found there" means "found in the vicinity of hard puzzles in ph2010"

[mith]

Yes, when I say my local version, I'm not talking about ph2010 (or ph1910 before that), but rather the roughly 32 million minimals I have after running neighborhood searches on the published ph databases and a few other seeds (for low counts).

Because of the way those scripts run, this is actually split by clue count, so the best I will be able to do as a first pass is find the earliest T&E(3) puzzle at each clue count (if any - there probably aren't any at very low or very high counts).

[mith]

Five new 11.8 expanded forms today:

Code: Select all

........1......23....245.6....47......85.6....47.28.56.86......42.65.7..7.5.8.6..  ED=11.8/2.0/2.0
........1.....234.235....6.....76...56.23.8..7..8.56...56..7...3.7.28.5682.......  ED=11.8/2.0/2.0
........1.....234.235..........67...57.23.8..6..8.57...57..6...3.6.28.5782.......  ED=11.8/2.0/2.0
........1......23....245.6....47......85.6....47.28.56.867.....42.65.7..7.5.8.6..  ED=11.8/10.5/2.6
........1.....234.235....6..56..7...3.7.28.5682........8..76...56.23.8..7..8.56..  ED=11.8/11.8/2.6

Six minimals between them. All have a 1-guardian trivalue oddagon.

[mith]

[edit]Nine[/edit] more 11.8s since my last update:

Code: Select all

........1....23.4...5..6....576..4.814.....768.6...51..81.6...456...8..77.4......  ED=11.8/2.0/2.0
........1....23.4...5..6....576..4.814.....768.6...51..81.6...456...81.77.4......  ED=11.8/11.8/3.4
........1.....2.3.....4.56.....1.....17..5..84.2.87....2857....1.5.2478.74....25.  ED=11.8/11.8/2.6
........1.....2.34..4.1356...2.....3.3..56...7.8.3.....1.3.542..2..64.15.4.12.3.6  ED=11.8/2.0/2.0
........1.....2.34..4.1356...2.....3.3..56...7.8.3.....1..64.25.2.3.541..4.12.3.6  ED=11.8/2.0/2.0
........1.....2.34..4.1356...2.....3.3..56...7.8.3.....1.32.4.6.2..64.15.4.1.532.  ED=11.8/2.0/2.0
........1.....2.34235...6...27.368..38.2.57.65.6.......53.68...6.2..7...87.52..6.  ED=11.8/11.8/2.6
........1.....2.34235...6...53.67...62...8...7.852..6..82.367..3.72.58.656.......  ED=11.8/11.8/2.6
........1.....2.34235...6...73.258.65.6......82.3.67...8725..6.35.6.7...6.2..8...  ED=11.8/11.8/2.6

[edit]Thanks JPF for pointing out the duplicate that was included here.[/edit]

Five "trees" here, and 21 minimals altogether. (All of them have single-guardian trivalue oddagons available after basics.)

The past little while I have been running the minimal_reducer script ({-2+1} on te3 minimals) along with the scripts on expanded forms. Closing in on 3 million minimals in the database, and a bit over 70% have been "reduced". I'm not sure at this point how long to expect it to run before running out of minimals (and I should mention there appears to be some bug that is causing some minimals to not be added to the database - shouldn't be too hard to track down, and I can just run the minimizer on all the min-expands once it's fixed), so depending on how I'm feeling in the next weeks I may go ahead and pause for an update of the database. My family finally got hit with COVID, and I'm definitely struggling with brain fog right now, so it may be a bit before I'm feeling up to that anyway.

When I do post an update, it will include some tools for trivalue oddagon/guardian analysis.

[mith]

Seven more:

Code: Select all

........1.......2....3456.7.....6....357.48..4.68..7....856..74.47.83...56.4.7..8  ED=11.8/11.8/2.6
........1.......2....3456.7.....6....354.78..4.68..7....856..74.47.83...56.7.4..8  ED=11.8/11.8/2.6
........1.......2....3456.7.....6....358.47..4.67..8....856..74.47.83...56.4.7..8  ED=11.8/11.8/2.6
................12...345.......36.....67.4.5847.85..6..54.638..3.7..86..68..7....  ED=11.8/11.8/2.6
................12...345.......36.....675..4857.8.4.6..45.638..3.7.8.6..68...7...  ED=11.8/11.8/2.6
................12...345.......36.....675..4857.8.4.6..45.836..3.7.6.8..68...7...  ED=11.8/11.8/2.6
................12...345.......36.....675..4857.8.4.6..45.836..3.7...8..68...7...  ED=11.8/2.0/2.0

9 minimals from these.

[denis_berthier]

Hi mith,
Best wishes with covid.

The past little while I have been running the minimal_reducer script ({-2+1} on te3 minimals) along with the scripts on expanded forms.

When this is done, can we formulate any closure properties, e.g.:
1) all the puzzles in the min-expand database are in T&E(3) (not really a question);
2) any puzzle in the min-expand database has all its minimals in the minimal database (they obviously are also in T&E(3));
3) any T&E(3) puzzle in the minimal database has its expanded form in the min-expand database (not really a question);
4) any puzzle in the minimal database has all its [-2 +1] neighbours in the minimal database, provided that they are in T&E(3) and minimal; (that's were I'm the least sure about what to think; what about the T&E(2) minimals?).

[mith]

I am currently running this script only on T&E(3) minimals (a separate database from the ph fork). But yes, the process currently is:

For each puzzle in the minimal_te3.db:
- Find all essentially different puzzles at {-2+1} (regardless of whether they are minimal)
- Check whether each puzzle is in T&E(3). If so:
- - Find the singles expanded form of the puzzle and check if it is new in the expanded_te3 database; if it is, add it.
- - All new puzzles in the expanded_te3.db are checked for transforms (digit cycle swaps), which are always also in T&E(3) as well as {+1} neighbors that remain in T&E(3).
- - All puzzles in the expanded_te3.db are minimized, and new minimals added to minimal_te3.

The result is stronger than property 4 - all {-2+1} neighbors which are T&E(3) and minimal will be present, but also any puzzle which is in the same "tree" as a {-2+1} neighbor (even if that neighbor isn't itself minimal).

Eventually I will also be running {-1+2} and {-2+2} neighborhoods, but this take much longer and are unlikely to ever reach a point of closure so long as I am running this on a single PC (I've given some thought to some sort of distributed computing program - sudoku@home if you will - but that's a longer term project and I have no idea how many people would be interested in contributing computing resources to something like this anyway). Even {-2+1} is quite slow - we're down to "only" 859k minimals unprocessed at the moment, out of 3.18m.

Only T&E(3) puzzles are in these databases. That said, I do intend to go back to the ph fork and run a depth check on all puzzles (or at least those not in the minimal_te3.db already), it would not be surprising to find some in different neighborhoods to add to the te3 databases.

[hendrik_monard]

A new batch of findings with 10 11.9s, 63 11.8s, 7497 11.7s and 5563 11.6s.
11.9s

Code: Select all

27...........8.......75.2..43.....177.9...32..12...9.49.7.314..14........23..91..   11.9/2.0/2.0
98.76.5..7.5..9....64.58...8.....4.....9...........32.6.8..5..4.7.64.....498.7..5   11.9/1.2/1.2
.39.....4......8.1..5......2..8.7.155...14.7.....2.4.8....75..2..248.1.7.....1...   11.9/1.2/1.2
......97.2....5......1.4.2.9.2..678.85........76.......89.6..576.....29.7...5.6.8   11.9/1.2/1.2
...8.1.........6.3.4....5..4.5..9....29......18.4.29..5.824..9..14.98.5.2..1.5...   11.9/1.2/1.2
......17.....5.......96..8.58.....3..71.3.84.3.4......15...34.8.4....75.8.7..5.13   11.9/1.2/1.2
.59..............7...9...513.529....94.3.6.2...6.45...5.36..4.229.4..3...64......   11.9/1.2/1.2
....46...3........5.7..2........9.13........69...6124..3.1...62.9.6.43.1....2349.   11.9/1.2/1.2
....8.5..3.9......5..76....1.....48........3.4.3.1.9.5.4...83..93...1.488.5...1.9   11.9/1.2/1.2
..6.81....2834.....1.2.6..48.3.64...14..2.6...621.3.......38....8....37........5.   11.9/1.2/1.2

11.8s

Code: Select all

98.76.5..7.4.9..8..56......5.83........2.9.............6...795...5..47.6.......48   11.8/1.2/1.2
98.76.54.7.5.......6.8...7.54...6.87..8...46...7...9.54.9..........39.5.....2....   11.8/1.2/1.2
98.76.54.7.5.......6.8...7.6.7...9.554.....87..8...46.4.9..........39.5.....2....   11.8/1.2/1.2
98.76.5..7.5..9....645.8...8...75.9.5.649...7...8.....6.....4.3...6.4...........2   11.8/1.2/1.2
98.76.5..7.58.49...46.5.....78.46.9...958.......9.7....6.........4....32.....8.5.   11.8/1.2/1.2
98.76.5..7.54.98...64..5....96.......4.....32.......8..79.46.5....95.......8.7...   11.8/1.2/1.2
98.76.54.7.5.......6.8..7..8.....6..5......97.47..685.4.9..........394......2....   11.8/1.2/1.2
98.76.5..7.58.49...46.5....8.954.....74.86.9....9.7....6............8.5........32   11.8/1.2/1.2
98.76.5..7.54......46......6.8..7...45.98..6...95...4....89........7.3.2......4..   11.8/1.2/1.2
98.76.54.7.54.......6......6.8.47...45.98...6..95........89........7.32.......4..   11.8/1.2/1.2
98.76.54.7.54.......6......6.8..7...45.98...6..95....4...89........7.32.......4..   11.8/1.2/1.2
98.76.54.7.5.......46......67...598..59...7.4..8....6....32.4......7..........89.   11.8/1.2/1.2
98.76.54.7..5.......6.4....6.8..7...54.98...6..94....5...89........7.32........5.   11.8/1.2/1.2
98.76.5..7.45..8...56......8...7496..6...97.5.......84...93........2.6.8.........   11.8/1.2/1.2
98.76.5..7.5.......46.5.87.6.....43....67..2............758...4...9.6.......4..89   11.8/1.2/1.2
98.76.5..7.45..8...56.......6...975.....749.6.......48..893........2.68..........   11.8/1.2/1.2
98.76.5..7.5.......64.58...8.....4.....9...........32.6.8.47..55..69.....978....4   11.8/1.2/1.2
98.76.5..7.5.......4..5.87.6.....43....67..2...........6..4..89..758...4...9.6...   11.8/1.2/1.2
98.76.5..7.54...8..46......8...7569..6...9.74......8.5...93........2..68.........   11.8/1.2/1.2
98.76.5..7.5.......46.5.87..6..4..89..758...4...9.6......67..3.......42..........   11.8/1.2/1.2
98.76.5..7.5.......46..98..6.....43....67..2............758...4...9.6.......4..89   11.8/1.2/1.2
98.76.5..7.5.......4...98..6.....43....67..2...........6..4..89..758...4...9.6...   11.8/1.2/1.2
98.76.5..7.54...8..46.......6...9.74....7569.......8.5..893........2..68.........   11.8/1.2/1.2
98.76.5..7.4.5.68.........78..3.4......2...........94.6.7...4.954....8...9.....65   11.8/1.2/1.2
98.76.5..7.59...6..64......84.....765.....89..97...4..4............38.5.....2..8.   11.8/1.2/1.2
98.76.54.7.59...6..6.......84.....765.....89..97...4..4............38.5.....2..8.   11.8/1.2/1.2
98.76.54.7.59...68.6.......84.....765......9..97...4..4............38.5.....2..8.   11.8/1.2/1.2
98.76.5..7.59...86.64......84.....675.......9.97...4..4............38..5....2...8   11.8/1.2/1.2
98.76.5..7.5..9....64.58...89........4.....32.......6.4..89..76...6.5.......47...   11.8/1.2/1.2
98.76.5..7.5..96....4.58...89........4.....32.......6.6...47...4..89..7....6.5...   11.8/1.2/1.2
98.76.5..7.5..9....64.58...89........4.....32.......6.6...47...4..89..76.....5...   11.8/1.2/1.2
98.76.5..7.5..96....4.58...89........4.....32.......6.6...47...4..89..76.....5...   11.8/1.2/1.2
98.76.5..7.5..96....4.58...89........4.....32.......6.6...4....4..89..7..7.6.5...   11.8/1.2/1.2
98.76.5..7.5..96....4.58...89........4.....32.......6.6...4....4..89..76.7...5...   11.8/1.2/1.2
98.76.5..7.4.5.69......9...69..84...5.8.7.....476.5......84...........38.......2.   11.8/1.2/1.2
98.76.5..7.54......46......6.8..7...45.89..6...95...4....98........7.3.2......4..   11.8/1.2/1.2
98.76.54.7.59..6.8.6.......84....7.65.....9...97....544............38.......2.8..   11.8/1.2/1.2
98.76.54.7.54.......6......6.8.47...45.89...6..95........98........7.32.......4..   11.8/1.2/1.2
98.76.5..7.45.......6.4....56.98..4.4.8..7.....96...5....89........7.3.2........5   11.8/1.2/1.2
98.76.54.7.54.......6......6.8..7...45.89...6..95....4...98........7.32.......4..   11.8/1.2/1.2
98.76.54.7.59..6...6.......84....7.65.....98..97....544............38.......2.8..   11.8/1.2/1.2
98.76.54.7.5.......46......67...589..59...7.4..8....6....32.4......7..........98.   11.8/1.2/1.2
98.76.54.7..5.......6.4....6.8..7...54.89...6..94....5...98........7.32........5.   11.8/1.2/1.2
98.76.5..7.4.5.68.........78..3.4......2...........94.64....8..5.7...4.9.9.....56   11.8/1.2/1.2
98.76.5..7.59...6..64......84.....965.....87..79...4..4............38.5.....2..8.   11.8/1.2/1.2
98.76.54.7.59...6..6.......84.....965.....87..79...4..4............38.5.....2..8.   11.8/1.2/1.2
98.76.54.7.59...68.6.......84.....965......7..79...4..4............38.5.....2..8.   11.8/1.2/1.2
98.76.5..7.59...86.64......84.....695.......7.79...4..4............38..5....2...8   11.8/1.2/1.2
98.76.5..7.5..8....64.59...89........4.....32.......6.4..98..76...6.5.......47...   11.8/1.2/1.2
98.76.5..7.5..86....4.59...89........4.....32.......6.6...47...4..98..7....6.5...   11.8/1.2/1.2
98.76.5..7.5..8....64.59...89........4.....32.......6.6...47...4..98..76.....5...   11.8/1.2/1.2
98.76.5..7.5..86....4.59...89........4.....32.......6.6...47...4..98..76.....5...   11.8/1.2/1.2
98.76.5..7.5..86....4.59...89........4.....32.......6.6...4....4..98..7..7.6.5...   11.8/1.2/1.2
98.76.5..7.5..86....4.59...89........4.....32.......6.6...4....4..98..76.7...5...   11.8/1.2/1.2
98.76.5..7.58.49...4..5....8.954....6..9.7....74.86.9..6............8.5........32   11.8/1.2/1.2
98.76.5..7.5..9....64.58...8.....4.....9...........32.6.8.47..55..6......978....4   11.8/1.2/1.2
98.76.5..7.5..9....64.58...6.8..5.4..7.64.....49..7.5....9.........8.3.2......4..   11.8/1.2/1.2
98.76.5..7.5..9....64.5....6.8..5.4..7.64.....498.7.5....9.........8.3.2......4..   11.8/1.2/1.2
98.76.5..7.45.......6.4....56.89..4.4.8..7.....96...5....98........7.3.2........5   11.8/1.2/1.2
98.76.5..7.5.4.6....45.8...64.......5.869.....798.4.6....9...32.....7..........5.   11.8/1.2/1.2
98.76.54.7.59..6.8.6.......84....9.65.....7...79....544............38.......2.8..   11.8/1.2/1.2
98.76.5..7.4.5.69......9...6.8.7....59..84....475.6......84...........38.......2.   11.8/1.2/1.2
98.76.54.7.59..6...6.......84....9.65.....78..79....544............38.......2.8..   11.8/1.2/1.2

As the remaining part is too large for posting here directly, I put the whole file, also including the above puzzles, on google drive.
This is the link:

Code: Select all

https://drive.google.com/file/d/1uYqIUHUybvcPoN9zeFkxJxbPaxLPr3vq/view?usp=sharing

As this is the first time I use this tool, I hope it works.

[eleven]

Great respect for all these findings with the TH pattern.

But isn't it time now to establish an alternative rating based on SER, which has this pattern integrated as an easy to spot one, and maybe SK loops a bit harder to spot and JExocets as hard to spot and MSLS as very hard to spot ?
(Also simple techniques like (grouped) skyscraper, w-wing should be integrated, as well as the harder ALS chains)

This way the hardest list does not make much sense to me.

[mith]

That's a lot of new 11.9s, well done hendrik I had paused the te3 search and was getting an update ready, but I will probably check your list for additions before I finish the update.

eleven: I don't disagree that an alternative to SER would be good - I am still rating by SER but I have somewhat lost interest in looking for high SER puzzles specifically (rather, I am looking for depth 3 puzzles, which are invariably high SER if uniqueness is excluded).

However, the relative difficulty of these "exotic" patterns is very subjective. It's easy to spot potential TH patterns, but not necessarily easy to get deductions from them when there is more than one guardian. (The same is true for relabeling - it might be obvious that you can relabel, but not obvious which house to use. What is the difficulty if I can reduce the puzzle to basics but only by choosing one specific house? Probably still easier than arbitrary dynamic chains? But how much easier?) And I personally find SET (basically a complimentary way of looking at MSLS) *much* easier to spot than JExocets (and "Almost SET" can be used in place of JExocets as well, which some may find easier).

[eleven]

Well i don't know SET.
It is clear, that some Exocets and MSLS's are easy to spot, and some very hard. (The same is true even for hidden pairs.) A rating may differ between them or not. It wouldn't be that important for me, which technique exactly gets which rating, eg. all around 9 (say 8-10) would be appropriate for JExocets/MSLS for me.
But if there are puzzles with TH (which - with one extra candidate - i woudln't rate harder than 7) in the top hardest list, which can be solved by spotting it and finish with singles, then this rating disqualifies for very hard puzzles.

[mith]

Quick illustration of SET on a coloin 11.7:

....5.7.....9.1.6.........52....8.16.......2..3....4.7.7..4......82.9...9.68.....
https://f-puzzles.com/?id=2oy8zcfw

The digits in r24589c13468 (orange) are equal to the digits in r1367c2579 (blue) + one extra set of 1-9. There are eight digits from 3457 in blue, so we need twelve in orange (8 + 4 from the extra set), and there are twelve empty orange cells. So all of these are from 3457, all of the empty blues are from 12689. 457 triple in box 4, stte.

The corresponding MSLS:
MSLS:20 Cells r1367c13468, 20 Links 34r1,347r3,5r6,35r7,168c1,129c3,16c4,26c6,89c8
22 Eliminations:r5c134,r8c1<>1,r2c3<>2,r3c57,r7c79,r1c9<>3,r1c29,r3c2<>4,r7c7<>5,r5c146<>6,r3c5<>7,r25c1<>8,r45c3<>9

Note the complimentary nature - this MSLS uses the rows from blue and the columns from orange; there is also a 19 cell MSLS using the rows from orange and columns from blue:
MSLS:19 Cells r24589c2579, 19 Links 28r2,9r4,1689r5,16r8,12r9,45c2,37c5,35c7,34c9
22 Eliminations:r5c134,r8c1<>1,r2c3<>2,r3c57,r7c79,r1c9<>3,r1c29,r3c2<>4,r7c7<>5,r5c146<>6,r3c5<>7,r25c1<>8,r45c3<>9

I find SET much easier to spot just looking at a grid of givens because it's immediately obvious how to try partitioning the rows/columns. (Yes, there are harder ones to find, sometimes incorporating boxes. But the general principle is that by adding and subtracting houses, your two partitions of cells will always be equivalent up to complete sets of 1-9, and you have a clear goal of forming partitions of cells that also partition the digits.)

Anyway, I absolutely agree that a puzzle solvable (or at least greatly simplified) with TH+1 is not going to be an actual "very hard puzzle" now that we know and understand it. In some sense though, the technique is still very difficult, in that we are only able to use it after having prove these patterns not chromatic number 3. So it's not clear to me how to take that into account when rating a puzzle, other than adding extra dimensions to the rating (for example, indicating the difficulty of the TH step separately from the difficulty otherwise). So a puzzle might be an 11.9, or [TH+1, 3.0], or [rc-SET, 5.4] or whatever. It sounds like what you're really after for this thread specifically though is a list of high SER puzzles that *don't* have any of these techniques available to reduce the difficulty - in which case we need tools to identify them quickly to filter those puzzles out from the database.