The New Sudoku Players' Forum

[denis_berthier]

.
Remember my old comparisons of ratings reported in [PBCS 1 to 3]
(https://www.researchgate.net/publication/280301697_Pattern-Based_Constraint_Satisfaction_and_Logic_Puzzles,...,
https://www.researchgate.net/publication/356313228_Pattern-Based_Constraint_Satisfaction_and_Logic_Puzzles_Third_Edition)
and recalled here:
http://forum.enjoysudoku.com/pattern-based-constraint-satisfaction-2nd-3rd-eds-t32567-11.html?

in particular those for the W and gW ratings, based on the 21,375 first puzzles of the controlled-bias collection (cbg-000 ):

W vs gW
Note that one must always have W ≥ gW
In reality, there are only 48 differences, i.e. a proportion of 0,22% differences.
And there are only 5 cases with difference > 1 (0,023%) and only one with difference > 2.

The question here is: what about the puzzles in T&E(3)? As this is a completely different collection - strongly biased, with all the puzzles having a particular pattern (tridagon) -, there's no a priori reason that would allow to extend the previous results to it. And indeed, they can't be extended. The differences are much higher.
To be more precise, consider the W+Trid-OR5W and the gW+Trid-OR5gW ratings (with ?*max-guardians* set to 8 and with all the ORk-consistency and splitting rules active). From my experience with puzzles in T&E(3), this is a good basis for comparison.
The comparison is here restricted to the first 10,000 puzzles in mith's collection of 158,276 min-expands.

Of course, one always has: gW+Trid-OR5gW ≤ W+Trid-OR5W
In reality, the W+Trid-OR5W and gW+Trid-OR5gW ratings are different in 3.69% of the T&E(3) puzzles (instead of 0.22% for W vs gW in cbg-000).
Also, 1.12% of the puzzles that are not solved in W8+OR5W8 get solved in gW8+OR5gW8

Whether this larger difference is totally due to the puzzles being much harder than those in cbg-000 or whether this is somehow specifically related to the presence of the anti-tridagon pattern remains undecided at this point.

For two examples of puzzles with different ratings, see:
- http://forum.enjoysudoku.com/1418-in-158-276-t-e-3-min-expands-t41482.html
- http://forum.enjoysudoku.com/5383-in-158-276-t-e-3-min-expands-t41504.html
The difference can appear with the presence of ordinary g-whips, ORk-gwhips or both.
.

[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).


.

[denis_berthier]

.
All the puzzles in mith's max-expand collection (http://forum.enjoysudoku.com/t-e-3-puzzles-split-from-hardest-sudokus-thread-t40514.html) have a non-degenerate tridagon.

I had previously shown that all the known minimal puzzles in T&E(3) have a non-degenerate tridagon and at that time, I didn't care to look beyond the minimals.

My new calculations allow to conclude that all the known* puzzles in T&E(3) have a non-degenerate tridagon.

(*) and all the implicitly known ones, between the minimals and the max-expands.
.

[denis_berthier]

.
What happens to a (non-degenerate) tridagon pattern when clues are deleted or added? The question arises in particular in the context of vicinity search.


1) When a clue is deleted from a puzzle with a tridagon pattern, the puzzle may come to have multiple solutions, but the tridagon is untouched (except that it may come to have more guardians).

2) As for adding a clue, we can be quite precise for puzzles in T&E(3).
Let's start with mith's collection of T&E(3) puzzles. He provides 3 collections in T&E(3): minimals, min-expands and max-expands (which I now prefer to call T&E(3)-expands in order to avoid any ambiguity).
Starting from minimals, clues can be added by applying Singles until one first reaches the min-expands, but still more clues (taken from the solution) can be added until one reaches the T&E(3)-expands, the limit beyond which one leaves T&E(3). Between minimals and max-expands is the whole T&E(3) land and its thickness is variable between 1 (in case the minimal is its own max-expand) and a few puzzles. Nothing really new until now.

But now what happens if one adds one more clue?
First, let's say that a puzzle P' is a 1-expand of a single solution puzzle P if P' has all the clues of P plus one (taken from the solution of P).
Now, starting from all the max-expands in mith's T&E(3) collection (48,071 minus 6 that are there by error), and applying systematically all the possible 1-expansions, one gets 2,257,893 puzzles, thus multiplying the number of puzzles by about 47 (before this number is eventually reduced by isomorphisms).
By the definition of a T&E(3)-expand, we know that none of these puzzles can be in T&E(3) or deeper (this is how I found the small error in the max-expands database). We also know that all the T&E(3)-expand puzzles have a non-degenerate tridagon.
The T&E(3)-expands form the border of T&E(3) from the inner side, and some of their 1-expands form part of the border from the outer side.
Note that these 1-expanded puzzles are not minimals and they may have other minimals than the already known ones, in T&E(3) or not. That's why they are not necessarily on the outer side of the T&E(3) border.

But are they all in T&E(2)? NO, but a high percentage is.

Code: Select all

1,584,186   are in T&E(2), i.e. 70.16 %
598,053   are in T&E(1), i.e. 26.49 %
75,632  are in T&E(0), i.e. 3.35 %

Note that this is not very surprising, as the addition of a clue has unpredictable effects in general.

Back to our original question: what about the tridagon?
For the puzzles in T&E(2), there are

Code: Select all

617,299 with a tridagon, i.e. 38.97 %
1,117,285 with a tridagon or a degenerate cyclic tridagon, i.e. 70.53%

For the puzzles in T&E(1), the percentages are lower, but still noticeable:

Code: Select all

15.20 % with a tridagon, i.e.
36.08 % with a tridagon or a degenerate cyclic tridagon.

Globally, considering the process of 1-expanding all the T&E(3)-expands:

Code: Select all

-in 27.34 % of the cases, one gets a puzzle in T&E(2) that has a tridagon;
-in 49.48 % of the cases, one gets a puzzle in T&E(2) that has a tridagon or a degenerate cyclic tridagon

Said otherwise, about 50% of the 1-expands of all the T&E(3)-expands (before possible reduction by isomorphisms) are potential precursors of T&E(3) puzzles. Which suggests that, in the vicinity search procedure, one shouldn't only check all the minimals of the min-expands, but all the minimals of the 1-expands of all the T&E(3)-expands. Of course, this may quickly become overwhelming work.

I have many more results about such expansions, but I need to do some cleaning before I can sort out the really interesting ones and publish them.
.