The New Sudoku Players' Forum

[denis_berthier]

.
SudoRules has finally completed its analysis of mith's collection of 158,276 min-expand puzzles in T&E(3) and of eleven's list of 630 3-digit impossible patterns in two bands (or two stacks).
As expected, the full calculations don't bring results significantly different from those obtained before with the partial lists of puzzles:
- there are four natural selections of Subsets of the 630 patterns (defined by how "useful" they are in solving the puzzles);
- Select1 is unchanged, apart from the last two patterns being permuted (but internal changes are not really relevant);
- there is more internal change in the other 3 subsets (but internal changes are not really relevant);
- 2 patterns are downgraded from Select3 to Select4 (but anyway, no calculations were done with Select3 or Select4);
- 2 new patterns are added to Select4.

The final result is:
Select1 = {EL13c290, EL14c30, EL14c159, EL14c1, EL14c13}
Select2 = Select1 + {EL10c28, EL13c179, EL13c30, EL13c171, EL13c234, EL13c176, EL10c6}
Select3 = Select2 + {EL13c259, EL10c8, EL13c172, EL14c19, EL10c4}
Select4 = Select3 + {EL13c175, EL13c136, EL15c97, EL13c187, EL14c93, EL12c2, EL14c154, EL13c19, EL13c170, EL13c168, EL10c10}
and these are the four subsets of patterns that can be collectively selected in SudoRules.

Remember that "usefulness" of a pattern is defined by the number of puzzles in which it leads to at least one elimination when the rules of (Trid+Imp630)+W8+OR5W8 are activated.
The final "usefulness" numbers are as follows. I give them here to show that the four subsets appear quite naturally.

Code: Select all

Trid = 152446 (in some puzzles, the tridagon pattern doesn't imply any elimination)
Total IMP630-EL<xxx>c<yyy> = 128584 (percentages below are wrt to this number)

Imp630-Select1 (total 86164, 67.01%):
EL13c290 = 29764
EL14c30 = 22989
EL14c159 = 14111
EL14c1 = 10027
EL14c13 = 9240

Imp630-Select2 (total +23789, +18.50% = 85.51%):
EL10c28 = 5486
EL13c179 = 4834
EL13c30 = 3200
EL13c171 = 2768
EL13c234 = 2598
EL13c176 = 2475
EL10c6 = 2428

Imp630-Select3 (total +7427, +5.78% = 91.29):
EL13c259 = 2108
EL10c8 = 1804
EL13c172 = 1462
EL14c19 = 1040
EL10c4 = 1013

Imp630-Select4 (total +5309, +4.13% = 95.42%):
EL13c175 = 726
EL13c136 = 656
EL15c97 = 623
EL13c187 = 581
EL14c93 = 578
EL12c2 = 448
EL14c154 = 396
EL13c19 = 389
EL13c170 = 316
EL13c168 = 307
EL10c10 = 289

SudoRules has been updated to reflect these minor changes (to be published soon).
The User Manual is also being updated and will be published soon. It will contain detailed additional results on the classification of puzzles that allow to draw stronger conclusions than the existence of the above sets of patterns.

As a personal side note:
After the discovery of the tridagon impossible pattern and of Loki by mith (http://forum.enjoysudoku.com/loki-ser-11-9-t39840.html?hilit=Loki)
and following my surprise to find it was in T&E(3) (http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1048.html),
I've been working on how to define generic resolution rules (ORk-chains) able to use application-specific impossible patterns (applied in particular to T&E(3) puzzles). More specifically, my recent work has been on selecting a small set of impossible patterns from the full set, with almost the same resolution power.
The above results make me feel my approach has reached its goals and I can now switch to other topics.

As a result, I don't plan to propose more T&E(3) puzzles from mith's collection in the "Puzzles" section (those I've proposed illustrate the different cases of interest I've found). However, I plan to publish my detailed classification results on GitHub, together with some explanation of how to use them to find more interesting puzzles. It may take some time to prepare all this.
Alternatively, you can use the "puzzles" section in a new way, to ask questions such as: is there a T&E(3) puzzle such that.... I can probably not answer all such questions, but let's see.
.

[JP_BENTZ]

Hello,
I haven't really been following your work, so I'm at risk of hitting a few open doors, but I'd like to submit to you an empirical solubility test which may be usable for certain specific configurations discussed in 2022.
Let's first define "pseudo-independent" positions (or "PIPs") in a block as positions within this block which do not share any row nor any column. Note : there are 2 different ways of completely dividing a block into 3 sets of 3 PIPs.
Let's now select in a grid ANY set of 3 PIPs in EACH one of ANY 4 blocks at the corners of a square or of a rectangle. And let's consider the path or paths which link(s), one to the other and from each block to the next, those of the 12 selected PIPs (i.e. 4 x 3) which are aligned along the rows and along the columns of these 4 blocks.
RULE (still to be formally demonstrated and possibly extended) : If the TOTAL number of crossings of this path with itself, or of these paths with each other, is odd, then the 4 sets of 3 PIPs cannot contain the same triplet of figures. As a result, if these 12 PIPS contain each the same triplet of candidates, this configuration has no solution as it stands (i.e. without additional information).

[denis_berthier]

Hi Jean Paul
Welcome on this forum

I'd like to submit to you an empirical solubility test which may be usable for certain specific configurations discussed in 2022.
Let's first define "pseudo-independent" positions (or "PIPs") in a block as positions within this block which do not share any row nor any column. Note : there are 2 different ways of completely dividing a block into 3 sets of 3 PIPs.
Let's now select in a grid ANY set of 3 PIPs in EACH one of ANY 4 blocks at the corners of a square or of a rectangle.

If you take this with the contraposition of

the 4 sets of 3 PIPs cannot contain the same triplet of figures

then you get the conditions in my first post (without additional conditions).

Using isomorphisms, there are only two possibilities:

Code: Select all

+-------------------------------+-------------------------------+
! 123       .         .         ! 123       .         .         !
! .         123       .         ! .         123       .         !
! .         .         123       ! .         .         123       !
+-------------------------------+-------------------------------+
! 123       .         .         ! 123       .         .         !
! .         123       .         ! .         123       .         !
! .         .         123       ! .         .         123       !
+-------------------------------+-------------------------------+

and

Code: Select all

+-------------------------------+-------------------------------+
! 123       .         .         ! 123       .         .         !
! .         123       .         ! .         123       .         !
! .         .         123       ! .         .         123       !
+-------------------------------+-------------------------------+
! 123       .         .         ! .         .         123       !
! .         123       .         ! .         123       .         !
! .         .         123       ! 123       .         .         !
+-------------------------------+-------------------------------+

The second case is the trivalue oddagon impossible pattern.
It shouldn't be too difficult to write your path condition from it.
.

[denis_berthier]

.
The degenerate cyclic anti-tridagon pattern

The most general non-degenerate anti-tridagon pattern with guardians has been defined here: http://forum.enjoysudoku.com/the-tridagon-rule-t39859-95.html
Non-degenerate means that each of the 3 candidates is present in each of the 12 cells of the pattern.
Proving the pattern contradictory requires (restricted) T&E(3).
This is a very strong condition, but all the known puzzles in T&E(3) happen to have this pattern.


Two degenerate forms of the anti-tridagon pattern were considered:
- here when a value is decided in one of the 12 cells:
http://forum.enjoysudoku.com/the-tridagon-rule-t39859-106.html
- and here for (the more general case of) 1 missing candidate in one of the 12 cells:
http://forum.enjoysudoku.com/the-tridagon-rule-t39859-106.html
It was shown there that these two cases require only T&E(2) to be proven contradictory.


Definition: the degenerate cyclic anti-tridagon pattern
- the pattern of 12 cells satisfies the same conditions as in the first post of this thread or as here: http://forum.enjoysudoku.com/the-tridagon-rule-t39859-95.html
- the pattern of digits in these cells has relaxed conditions, allowing some of the 123-candidates to be missing, but in a controlled way: in each of the 4 blocks, the 3 cells of the pattern must have the cyclic pattern of 123 digits, i.e. at least the respective following contents, in any order: 12 23 31.

Remarks:
- this defines a restricted form of degeneracy;
- none of the 12 cells of the pattern can be decided;
- from the above theorem, this pattern can be proven contradictory in T&E(2);
- cyclic conditions appear quite naturally in other patterns, such as Triplets or Quads and are used in SudoRules to differentiate non-degenerate Subsets from degenerate ones;
- the pattern of cells and the cyclic conditions make it relatively easy to identify the degenerate cyclic pattern, even with very large numbers of guardians.



******************

One question is, can one find this pattern in old puzzle collections? Moreover, how far back in time can one go and find it?
The question comes naturally when considering the search methods used to find the "hardest" puzzles: vicinity search starts from puzzles with high SER and looks for hopefully harder puzzles in their neighbourhood.


At this point, it is essential to recall that this is how Loki (and similar puzzles) was originally found by mith: as a puzzle with high SER (11.9).
Later, I found that Loki was not in T&E(2) but in T&E(3). Replacing SER by T&E-depth in the search scripts then led to find many more puzzles in T&E(3), but the original way Loki was found was by vicinity search for high SER, starting from puzzles with already high SER (which I proved long ago to be in T&E(2)).
Note also that there has never been any explicit search for the tridagon pattern. It is a fact that it appears in all the T&E(3) puzzles, but it just happens to be so.


As a result, it is natural to think there must have been some precursors of the tridagon pattern in the T&E(2) puzzles that were used as seeds in the vicinity search procedures. And the degenerate cyclic anti-tridagon pattern appears to be a good choice for a possible precursor.

Note that the case of a decided cell may also be a precursor, but I haven't yet investigated it .
.

[denis_berthier]

.
Answers to the questions in the previous post.

The first collection I tried is eleven's "gotchi" collection:
http://forum.enjoysudoku.com/the-making-of-a-gotchi-a-simple-way-to-find-extreme-sudokus-t30150.html,
because it was built in a pattern-independent way and I've analysed it recently in relation to the BpB classification of puzzles in T&E(2):
https://github.com/denis-berthier/Classification-of-TE2-Sudokus
10861 out of 26,370 puzzles (41 %) have a degenerate cyclic anti-tridagon, regardless of their place in the collection (i.e. of their SER).


******************

The second collection I tried is the famous Magictour "top 1465 hardest" collection (unfortunately, I don't have any url to give for it).
There was a time when it contained part of the currently hardest known puzzles. I've shown long ago that all of its puzzles are in T&E(1), except 3 that are in gT&E(1).
By today's standards, it is therefore not an extremely hard collection and one may not necessarily expect to have any precursor of the tridagon pattern in it.
However, it is there:
53 out of the 1465 puzzles (3.6 %) have the degenerate cyclic anti-tridagon pattern, regardless of their place in the collection.


******************

The third collection I tried is my controlled-bias one, which is in the mean still easier than Magictour. The degenerate pattern is there also, though not very frequently.
48 out of 21375 (0.22 %) puzzles have the degenerate cyclic anti-tridagon pattern. This is not much, but this nevertheless proves that one doesn't have to look very long for the pattern before finding it.


******************

Conclusion: degenerate cyclic precursors of the anti-tridagon pattern are everywhere around. This allows to understand why vicinity search can eventually find non-degenerate ones.
Note however that, in most cases, they have very large numbers of guardians, which makes them quite useless for solving puzzles.


[Edit]: needless to say, but: in all of these collections, there's no non-degenerate tridagon.
.

[denis_berthier]

.
Resilience of the non-degenerate tridagon pattern

Following the last collection of T&E(2) puzzles published by Paquita:
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1650.html

I had a few questions about it, because it had an unusually high proportion of puzzles in B6B.
I went back in time and checked his previous two collections:
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1648.html
http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-1644.html
They also have unusually high proportions of puzzles in B6B.

But what I had completely overlooked and what there's in common between the three collections is a very high proportion of puzzles with a non-degenerate tridagon (with guardians): 100%, 99.97% and 97.01% resp.

The result is, my questions in the "hardest" thread about the unusual BpB ratings were misguided by my idea that they could mainly result from the search for high SER.
Indeed, I now think they result mainly from the technique of vicinity search.

Starting from puzzles with a non-degenerate tridagon, "many" nearby ones will also have this non-degenerate pattern. Said otherwise, the non-degenerate tridagon pattern is very resilient to "small" changes of givens (even without counting all the trivial isomorphisms).

(For puzzles in T&E(3), this high resilience may also explain why so many puzzles with a non-degenerate tridagon have been found so fast after the first few ones.)

There remains to explain why the presence of a non-degenerate tridagon AND a high SER favours a high BpB, but at least this is easier to imagine than just a high value of the SER (because this explanation alone would contradict our previous vague correlation results).


.