The New Sudoku Players' Forum

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

[denis_berthier]

.
In a previous post (http://forum.enjoysudoku.com/the-tridagon-rule-t39859-119.html),
I gave the proportion of degenerate-cyclic tridagons (as defined here http://forum.enjoysudoku.com/the-tridagon-rule-t39859-118.html)
in the first small part of the [cbg] collection: 0.22%.

As a background work when my Mac was not busy on some other calculations, I have now finished checking the whole collection of ~6M puzzles.

In the full controlled-bias collection, there is no non-degenerate tridagon, but there are 16,453 puzzles (0.278 % ) with the degenerate-cyclic variant.

The purpose of checking the whole collection was not to improve the precision of the percentage (though it did) but to be able to compute such distributions as the SER or B-ratings and to have enough puzzles for starting further calculations.

Both distributions (SER and B-ratings) are concentrated on much higher values than in the full [cbg] distribution, as shown below.

B distribution (number of puzzles):

Code: Select all

3: 3039
4: 7107
5: 4096
6: 1535
7: 492
8: 138
9: 40
10: 5
11: 0
12: 0
13: 1

SER distribution (number of puzzles) (left column is 10*SER:

Code: Select all

42: 240
43: 0
44: 27
45: 0
46: 0
47: 0
48: 0
49: 0
50: 6
51: 0
52: 0
53: 0
54: 1
55: 0
56: 0
57: 0
58: 0
59: 0
60: 0
61: 0
62: 3
63: 0
64: 0
65: 3
66: 127
67: 96
68: 14
69: 3
70: 16
71: 1814
72: 3564
73: 2015
74: 116
75: 75
76: 220
77: 228
78: 408
79: 102
80: 34
81: 0
82: 253
83: 2641
84: 2013
85: 819
86: 73
87: 28
88: 206
89: 623
90: 599
91: 80
92: 5
93: 1

Even after truncating this sub-collection to the upper B or SER values or both, there remains enough puzzles to be used as seeds in the search for non-degenerate tridagons.

[Edit): Actually, in order to avoid problems with uniqueness, I didn't use the SER but SER with no uniqueness; and I didn't use SudokuExplainer but its FPGX variant, available on GitHub in the programs folder of [cbg]: https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection
.

[denis_berthier]

.
This is mainly for completing the contents of this thread about tridagons. I've published all this before, in much more detail.

Having a (non-degenerate) tridagon doesn't imply much about the T&E-depth of a puzzle or about its B or BxB classification when it's in T&E(1) or T&E(2). The reason is that other parts of the puzzle may allow eliminations that bypass the complexity inherent in the tridagon pattern.

However, there are strong converse implications:
- every known puzzle in T&E(3) has a tridagon ; this is now an old result ;
- every known puzzle in T&E(2) AND with BxB > 7 has a tridagon. This may be the most surprising result of the recent search for the "hardest" puzzles.
My old conjecture that all the puzzles were in T&E(≤2) and in BxB, x ≤ 7, has been refuted after the discovery of the Loki puzzle.
What remains is that every known puzzle in T&E(2) with BxB > 7 has a tridagon. And what remains true also is, we have no idea of why this number 7 appears here.
.