The New Sudoku Players' Forum

[denis_berthier]

.
In a previous post (http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1321.html)
I stated that all the puzzles in mith's database of 63,137 T&E(3) min-expands (http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1304.html)
are indeed in T&E(W2, 2).

My recent calculations allow to extend the above results:
all the puzzles in mith's database of 158,276 T&E(3) min-expands (http://forum.enjoysudoku.com/t-e-3-puzzles-split-from-hardest-sudokus-thread-t40514.html)
are indeed in T&E(W2, 2).

And it is enough to prove:
All the known 9x9 sudoku puzzles in T&E(3) are indeed in T&E(W2, 2) or less.

[mith]

Very nice result, Denis. I wonder if we will find any that go beyond T&E(W2,2).

I've been giving my computer a break from generating puzzles, but I will likely resume work in the new year. jovi_al provided a large list of puzzles generated on the trivalue oddagon pattern which I need to run a depth check on to see if any are depth 3 and need to be added.

[denis_berthier]

Very nice result, Denis. I wonder if we will find any that go beyond T&E(W2,2).

Hi mith. Thanks.
The trivalue oddagon pattern requires more than T&E(W2, 2) to be proven contradictory. Even if it didn't, this wouldn't imply that puzzles with an anti-tridagon are in T&E(W2, 2). Finally, we don't know if all the puzzles in T&E(3) have an extended anti-tridagon.
That makes many reasons for being careful about our expectations.

For more than 10 years, all the known puzzles were at most in T&E(2) - indeed in T&E(B7, 1) = B7B. It was rational at that time to conjecture that all the puzzles were also at most in B7B. With the large number of puzzles in your database, it is now rational to conjecture that all the puzzles are (at most) in T&E(W2,2).

But a conjecture is a conjecture. The longer it lasts, the more interesting it is to find a counter-example.
It's great that my T&E(2) and B7B conjectures were disproved by your Loki puzzle and it's great to see that the new puzzles have led to develop a whole set of new powerful resolution rules (ORk-chains and ORk-g-chains).

I wonder about the other T&E(3) patterns that have been found. Would your techniques allow to develop similar databases concentrated on them?

[mith]

Hi all! I've been taking a longer break from this than expected, for two reasons:

1. I started a puzzle patreon in January, and making puzzles and solve videos for that has taken up a good amount of my free time!
2. The cooler on my computer blew out, so I was without my computer for a couple weeks.

Not sure when I'll get back to running scripts, but I know that jovi_al has done a search on the trivalue oddagon pattern and generated a bunch of puzzles so I need to check those for any new depth 3 to add to the database.

[denis_berthier]

.
Hi mith,
glad to see you back here.
Take your time. With the current database, you've already given us much analysis work. We're still very far from having run out of examples with new interesting features.
What's now clear is, even though all the known puzzles in T&E(3) are indeed in T&E(W2, 2) (see previous post), that leaves a very broad spectrum of complexity, ranging from those that can be solved with simple chains after the simplest tridagon elimination (like Loki) to those that remain in T&E(2) even after applying all the known impossible patterns with long ORk-chains.
.

[mith]

Continuing from the hardest thread.

b. The 3 digits are placeable in the three cells of each box (ruling out cases where one of the 12 cells already can't contain one of the digits, but also a case like 1 can go in either of r1c1 or r2c2, but 2 and 3 can only go in r3c3; each cell can contain a digit from 123, but not all three at the same time).

There must be some misunderstanding here. For me "The 3 digits are placeable in the three cells of each box" means that the 3 candidates are present in all the 12 cells - i.e. the pattern is non-degenerate.

What I mean is simply "there exists some way to place the 3 digits of the triple in the 3 cells of the box, for each box of the pattern".

For example:

Code: Select all

,---------------------,-----------------,---------------------,
| 1      248*    3    | 248* 5    6     | 279   24789   2489  |
| 248*   5       7    | 1    248* 9     | 26    2348    23468 |
| 6      9       248* | 3    7    248*  | 125   12458   12458 |
:---------------------+-----------------+---------------------:
| 248    2468    1    | 248  9    3     | 256   2458    7     |
| 5      248     9    | 6    248  7     | 3     1248    1248  |
| 23478  234678  2468 | 5    1    248   | 269   2489    24689 |
:---------------------+-----------------+---------------------:
| 23478  123478  248* | 9    6    12458*| 1257  12357   1235  |
| 23789* 123678  268  | 278* 238  1258  | 4     123579  12359 |
| 23479  12347*  5    | 247  234* 124   | 8     6       1239  |
'---------------------'-----------------'---------------------'

This is one of the min-expands from the Loki tree, with the non-degenerate TO in boxes 1245. What I've marked is a degenerate TO. It is possible to place 248 in the marked cells of box 7, when considering only those cells: for example 2r7c3, 8r8c1, 4r9c2. Likewise, it is possible to place 248 in the marked cells of box 8. However, in both boxes there are cells which are missing one of the candidates from the triple (and this will of course always be the case if the box selection is anything other than the four boxes which don't share a band/stack with the box containing those givens).

This particular degenerate TO has 5 guardian cells and 10 guardian candidates; in theory, you could have some OR-branching chain based on this (and there are some puzzles with non-degenerate TOs after basics which have more guardian cells/candidates).

The full version of the script finds all of these. (One other obvious filter that I neglected to mention - if there is a cell which can only contain digits from the triple in question, it must be part of the pattern. marek pointed out that I could also check whether placing the triple breaks other cells in the box, I will likely add this to the filter for this update.)

Code: Select all

1.3.56....571.9...69.37......1.93..75.96.73.....51.......96..........4....5...86.;1;3;51
1;1;n248;b1p249+b2p159+b4p159+b5p159
5;10;n248;b1p249+b2p159+b7p348+b8p348
5;11;n248;b1p249+b2p159+b7p357+b8p357
10;25;n239;b1p348+b3p168+b7p267+b9p159
8;22;n359;b2p267+b3p159+b8p168+b9p159
6;11;n248;b4p159+b5p159+b7p348+b8p357
6;12;n248;b4p159+b5p159+b7p357+b8p348
10;26;n289;b4p267+b6p159+b7p267+b9p357
10;25;n289;b4p267+b6p267+b7p267+b9p357
10;23;n249;b4p267+b6p267+b7p348+b9p249
10;19;n246;b4p159+b6p159+b7p357+b9p348
10;25;n289;b4p267+b6p267+b7p357+b9p267
10;25;n289;b4p267+b6p168+b7p267+b9p267
10;25;n279;b4p267+b6p357+b7p267+b9p159
10;24;n279;b4p267+b6p357+b7p348+b9p159
10;25;n289;b4p168+b6p267+b7p267+b9p267
9;23;n258;b4p249+b6p159+b7p159+b9p267
8;23;n456;b4p249+b6p159+b7p159+b9p348
9;22;n258;b4p249+b6p267+b7p159+b9p267
8;23;n456;b4p249+b6p267+b7p159+b9p348
10;24;n128;b4p357+b6p159+b7p267+b9p267
10;23;n128;b4p357+b6p159+b7p348+b9p267
10;23;n128;b4p357+b6p267+b7p267+b9p267
10;22;n128;b4p357+b6p267+b7p348+b9p267
10;25;n289;b4p168+b6p168+b7p357+b9p267
9;22;n258;b4p249+b6p168+b7p249+b9p267
10;22;n128;b4p357+b6p168+b7p168+b9p267
10;23;n128;b4p357+b6p168+b7p357+b9p267
10;23;n249;b4p168+b6p168+b7p348+b9p249
9;23;n245;b4p249+b6p168+b7p159+b9p249
9;22;n258;b4p249+b6p168+b7p159+b9p357
10;22;n124;b4p357+b6p168+b7p267+b9p249
10;23;n128;b4p357+b6p168+b7p267+b9p357
10;21;n124;b4p357+b6p168+b7p348+b9p249
10;22;n128;b4p357+b6p168+b7p348+b9p357
10;26;n289;b4p168+b6p159+b7p357+b9p357
10;25;n289;b4p168+b6p267+b7p357+b9p357
9;24;n245;b4p249+b6p159+b7p249+b9p249
9;23;n258;b4p249+b6p159+b7p249+b9p357
9;22;n258;b4p249+b6p267+b7p249+b9p357
10;22;n124;b4p357+b6p159+b7p168+b9p249
10;23;n128;b4p357+b6p159+b7p168+b9p357
10;23;n124;b4p357+b6p159+b7p357+b9p249
10;24;n128;b4p357+b6p159+b7p357+b9p357
10;21;n124;b4p357+b6p267+b7p168+b9p249
10;22;n128;b4p357+b6p267+b7p168+b9p357
10;22;n124;b4p357+b6p267+b7p357+b9p249
10;23;n128;b4p357+b6p267+b7p357+b9p357
9;18;n127;b5p168+b6p357+b8p357+b9p159
9;21;n235;b5p357+b6p249+b8p357+b9p159
8;21;n358;b5p357+b6p249+b8p348+b9p357

[mith]

I don't understand: "each cell can contain a digit from 123, but not all three at the same time". Do you mean some cyclic condition like a 12 23 31 pattern in each block? I've tried this, but I found it difficult to manage the inter-block conditions.

What I mean here is that there could be cell A with candidates 1xxx, cell B with candidates 1xxx, and C with candidates 23xx. This would pass a filter that only checks for whether there is at least one candidate from 123 in each cell of the pattern, but it fails the filter that tries to place 123 in ABC.

[denis_berthier]

.
Hi Mith
Thanks for your explanations.
I think your filters amount to the following (in addition to the pattern of cells):
- either one of the 3 cells of the block is decided (say = 1) and the other two cells have the remains 23 candidates;
- or there is a cyclic 123-pattern in the 3 cells of the block: at least 12, 23, 31 candidates.
.

[denis_berthier]

I get the impression that T&E(3) has a lot of 11.8 puzzles. In T&E(2), 11.8 is quite rare, with a lot more 11.7 and 11.6.
Now, when I find a 11.8, I am almost sure it is T&E(3) (they are all already in miths T&E(3) collection). And although I find only a few T&E(3) because I use T&E(2) seeds almost half of them is 11.8. Maybe another illustration of how the SE/PGX rating fails for T&E(3), also since I read the posts about how easy those puzzles sometimes are.

Such posts reflect a confusion between two different ways of rating puzzles. One way is the SER (that doesn't take tridagons into account). The other way uses tridagons. It's like comparing bananas and snails.

As for the SER 11.8:
- it is indeed rare in the current T&E(2) database (but remember it hasn't been searched with the same vicinity and expansion methods);
- the T&E(3) database of 847,778 minimals shows that 11.8 is very far from having any predominance in it (and it confirms an anomaly at SER 10.4 that I had already pointed out in [PBCS], plus one at SER 10.9 plus one in the 9.x range):

Code: Select all

-       7 have SER 11.9
-     316 have SER 11.8
-  95,482 have SER 11.7
-  63,706 have SER 11.6
-     989 have SER 11.5
-      13 have SER 11.4
-     825 have SER 11.3
-   5,525 have SER 11.2
-  27,422 have SER 11.1
-  63,306 have SER 11.0

- 109,033 have SER 10.9
-     369 have SER 10.8
-   2,855 have SER 10.7
-  51,816 have SER 10.6
-  52,857 have SER 10.5
- 214,743 have SER 10.4
- 101,502 have SER 10.3
-  35,108 have SER 10.2
-   1,653 have SER 10.1
-     900 have SER 10.0

- 16,429 have SER 9.x
-    842 have SER 8.x
-    528 have SER 7.x
-  1,005 have SER 6.x
-     24 have SER 5.x
-    523 have SER 4.x

The small values of the rating are due to rules of uniqueness in SER.

[Paquita]

Yes, in the T&E(2) database about 1 in 5000 is 11.8; in this T&E(3) collection it is about 1 in 2500. Not as much as I thought.

[denis_berthier]

Update as of 2022-11-06

The database "expanded_te3.db" currently holds 847778 depth 3 expanded forms*, with clue counts ranging from 24c-40c.
[...]
From this database, the min-expand** and max-expand*** puzzles have been determined.
[...]
max_expands_20221106 (48071 puzzles)
unix format
dos format
[...]
*** max-expand - these are expanded forms which cannot have clues added while remaining depth 3

There's a small error in the "max-expand" database: the following six puzzles can be further expanded in T&E(3)

Code: Select all

.23456......18923......74............35.62.41.1.....6.34....65.5.16...23.625..1.4;15829;673789
1.3.5.......18923......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4;15829;710018
.234.6.......89.3......741...........35.62.41.1.....6.34....65.5.16...23.625..1.4;15829;403342
.2345........89.3......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4;15829;419498
1...56.......8923......74............35.62.4..1.....6.34....65.5.16...23.625..1.4;15829;754675
....56.89...1.9..6.96.3....26...34.8.....469..49..8.23.32.....46.4......98..4..62;23048;452096

They have the following expansions by 1 clue (they may have further expansions; I didn't check:
(orig# is the place of the puzzle in the max-expand collection.)

Code: Select all

123456......18923......74............35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17719
.23456......18923......741...........35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17719

123.5.......18923......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4 orig# 17720
1.345.......18923......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4 orig# 17720
1.3.56......18923......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4 orig# 17720
1.3.5.......18923......741...........35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17720

1234.6.......89.3......741...........35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17721
.23456.......89.3......741...........35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17721
.234.6......189.3......741...........35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17721
.234.6.......8923......741...........35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17721

12345........89.3......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4 orig# 17722
.23456.......89.3......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4 orig# 17722
.2345.......189.3......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4 orig# 17722
.2345........8923......741...........35..2.41.1.....6.34....65.5.16...23.625..1.4 orig# 17722
.2345........89.3......741...........35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17722

12..56.......8923......74............35.62.4..1.....6.34....65.5.16...23.625..1.4 orig# 17723
1.3.56.......8923......74............35.62.4..1.....6.34....65.5.16...23.625..1.4 orig# 17723
1..456.......8923......74............35.62.4..1.....6.34....65.5.16...23.625..1.4 orig# 17723
1...56......18923......74............35.62.4..1.....6.34....65.5.16...23.625..1.4 orig# 17723
1...56.......8923......741...........35.62.4..1.....6.34....65.5.16...23.625..1.4 orig# 17723
1...56.......8923......74............35.62.41.1.....6.34....65.5.16...23.625..1.4 orig# 17723

...456.89...1.9..6.96.3....26...34.8.....469..49..8.23.32.....46.4......98..4..62 orig# 25533


[mith]

That's unexpected, but I was able to figure out what is going on here.

The actual max-expands for these puzzles are:

Code: Select all

12....78..571..2.66.82...152.....5..7.5.628.1............72165857..4....86.593...;15829;658138
....567...5718.2..8.62.71...65....1....52.697...6..5.35.286..7.67........817.....;23048;624629

Note that they look very different from the puzzles you've listed, and this is why they are listed despite being max. The current script only does a naive check of whether the solution minlex grid is a subgrid of a larger puzzle just by comparing the strings. However, these solution grids have a nontrivial automorphism, and it happens that the other "max-expand" puzzles listed are being canonicalized to the other morph of the solution grid, resulting in the naive check failing.

The second thing to note is that at least the first two expanded puzzles in your list are not in the database at all, because they are not singles expanded; both expand to the 36c puzzle above (placing 1 in either position makes the other placement of 1 a hidden single). The same sort of thing is happening for the rest (the puzzles listed either are actual max-expands or are intermediates that singles-expand to the actual max-expands).

So, there aren't any puzzles missing, but rather there are some extra puzzles in the max-expand list which should not be; the automorphism in the solution grids results in ambiguity when gsf canonicalizes in "solution_minlex" form. I'll look into addressing this in my next update, it should only require a change for solution grids with this property so it shouldn't add too much time to do a more thorough check for these grids.

[mith]

(I'm running a check now for any other solution grids with nontrivial automorphisms; it's over halfway through the solution grids included in the 2022-11-06 update, and these are the only two found. So this may be a really small task for correcting the old list - literally just removing the puzzles Denis listed from the max-expand file. Given how infrequent this issue is, it should be quick to just add special handling when the automorphism count is >1, rather than changing the process for all trees.

[edit]Confirmed, these are the only two out of the 44251 solution grids in the 2022-11 update. I'll check the remainder of the database when I next run the update and determine the max-expands.[/edit])

[denis_berthier]

.
Hi mith
Thanks for your quick answer.
Fortunately, this will not change what I was doing with the max-expands (see the tridagon thread).
.

[mith]

Continued from hardest puzzle thread:

the 11.3 Denis posted earlier does *not* have a valid non-degenerate trivalue oddagon (at least by my definition); because r1c9 is limited to 123, the three marked cells in box 3 already cannot all contain 123, so the OR branching can be reduced to considering that r2c7 and r3c9 cannot both contain 123.

"My" 11.3 (indeed Paquita's) has a non-degenerate trivalue oddagon (it has indeed many different ones), unless one is willing to add to the definition conditions (such as those you're mentioning) that have never been defined and that are potentially in unlimited numbers. I think you're confusing the presence of the pattern (defined in the precise, simple way I gave in the tridagon thread) with its usefulness in specific circumstances.
In the present case, there are two independent circumstances that make it useless: the one you're mentioning and the very high number of guardians.
.

This condition was defined (insofar as it is part of the algorithm I use) in this thread: p328613 (fourth bullet point). This specific post does not exclude degenerate tridagons by your definition, though that is handled in a later algorithm (a trivalue oddagon can only contain all digits in all cells of the pattern if those digits are restricted as givens to a single box which is not aligned with the four boxes of the pattern; a given in any other box will necessarily remove that candidate from a cell of the pattern, since the pattern spans all rows and columns within each box it covers).

It is not merely a matter of usefulness; it is a matter of reduction to a smaller pattern. In this case, the set of cells r1c89+r2c7+r3c9 is a 4 cell pattern with a chromatic number of 4, and the guardians are a subset of the guardians in the trivalue oddagon. We can quickly identify such cases by noting that there is a cell in box 3 which is not part of the potential trivalue oddagon but which is limited to the three digits of the trivalue oddagon, and is quite limited in scope (I can think of one other similar limitation involving the rows/columns instead of the box, but it would be much more unlikely to occur; might add a check for that at some point anyway).

In fact, there is nothing precluding a case where the guardians of the smaller pattern are exactly the same as the guardians of the trivalue oddagon, and in such a case the trivalue oddagon would be exactly as useful as the smaller pattern. Even in cases where the guardians of the smaller pattern are a proper subset of the guardians of the trivalue oddagon, there is nothing precluding the smaller pattern from being useful.

You can choose to not define this case as degenerate, that's your prerogative. It's totally reasonable to draw the line at only considering cells and candidates which are part of the pattern. That said, one could perhaps make the argument that it is degenerate even by your definition in the sense that whatever (unknown) digit goes in r1c9 (which we know is from 123) is excluded from the other cells in the box (r1c8+r2c7+r3c9).

Anyway, I do consider this case degenerate, and specified in my post that my comment was according to my definition. And I have consistently defined it this way since starting to analyze the T&E(3) database for the pattern (it just happens to be the case that all puzzles in T&E(3) currently known satisfy this more restrictive condition as well).