The New Sudoku Players' Forum

[denis_berthier]

.
The previous posts were about maximally expanding minimal puzzles in T&E, while remaining in T&E(3).
This post will be about minimally expanding the same minimal puzzles in T&E in a way that leads to leaving T&E(3).

The simplest way of doing this would be to use BRT-expansion, but that keeps the puzzles in T&E(3). Moreover, mith's database is closed under BRT-expansion and minimisation, so that no new minimal of a BRT-expand of his minimals can appear in the process (unless there's some breach of the principle - but that could be only rare, as I've checked it on large random samples).

As a result, the next simplest case is to consider 1-expansions of the BRT-expands, i.e. the "p1" puzzles in the above notation, or rather the "p1U" ones (i.e. the "p1" with no redundancies). Here again, several options are possible, e.g.
- studying those at T&E-depth 3: I'll skip this because I'm not mainly interested here in producing new T&E(3) puzzles;
- studying those at T&E-depth 2: I'll skip this for now, because the results are not very promising, but I may come back to it later;
- studying those at T&E-depth 1: this will be the topic in the rest of this post. The question here is, can we get "hard" T&E(1) puzzles this way. And the answer is a big YES. "Hard" is here understood as "with very large B rating". And "very large B rating" will in turn be understood as "with B ≥ 12". Note that this is a very reasonable choice: in the whole controlled-bias collection "cbg" of 5,926,343 minimal puzzles, all in T&E(1), there are only 6 with B rating 12, 2 with B rating 13 and none with a larger B rating; B ≥ 12 can therefore naturally be considered as "very high".

Starting from these "p1U" puzzles in the same sample as in my previous posts, several actions can be done:
- start: 512,822 "p1U" puzzles (non-minimal)
- filter those in T&E(1) ===> 126,985 "p1U-d1" puzzles (non-minimal)
- filter those with B ≥ 12 ===> 1,638 "p1U-B12" puzzles (non-minimal) - note that this is already much more that in the whole cbg collection.
- find all their minimals ===> 16,153 "p1U-B12-mins" minimal puzzles (which can a priori be at any T&E-depth ≥ 1)
- filter those in T&E(1) ===> 7,226 "p1U-B12-mins-d1" minimal puzzles (which can a priori only have B ≥ 12)
Now, we have many more minimal puzzles with B≥12 than among the non minimal "p1U-B12". This was of course to be expected at the end of minimisation. But the question is, how much harder can they be than B12? And that's were we find interesting results: they can be as hard as B19 - i.e.. extremely rare T&E(1) puzzles - so rare that no probability for them can be computed.

In particular, we find 86 minimal puzzles in B18 and 35 minimal puzzles in B19 (shown below):

Code: Select all

1...5678....78...3...1.3.65......83.....7.....6783.51..9.56.....42.1....8........  #125
1...5678....78...3...1.3.65......837..........6783.51..9.56.....42.1....8........  #126
1...5678....78.1.3.....3.65......83.....7.....6783.51..9.56.....42.1....8........  #127
1...5678....78.1.3.....3.65......837..........6783.51..9.56.....42.1....8........  #128
12...67.9.56......7.9.2..........95.....6...1....123.85...7....6.2.91..7.9...5.1.  #656
12...67.9.56...1..7.9.2..........95.....6...1....123.85...7....6.2.91..7.9...5...  #657
..34....94.6.8.....8.1...6......19.4...3..81......8.363........5.296.....97......  #1912
..34....94.6.89....8.1...6......19.4...3..81......8.363......9.5.2.6.....97......  #1913
..34.6..94.6.8.....8.1..4.......19.4...3..81......8.363........5.296.....97......  #1914
..34.6..94.6.89....8.1..4.......19.4...3..81......8.363......9.5.2.6.....97......  #1915
1.34.....4.6.89....8.1...6......19.4...3..81......8.363......9.5.2.6.....97......  #1916
1.34.6...4.6.89....8.1..4.......19.4...3..81......8.363......9.5.2.6.....97......  #1917
1.3.......567.....78...356...16.7....6..18..7...5........8..29....3....58.5...3.1  #2704
1.3...7...56......78...356...16.7....6..18....7.5........8..29....3....58.5...3.1  #2707
1.3...7...56......78...356...16.7....6..18..7...5........8..29....3....58.5...3.1  #2710
1.3.......5678....78...356...16.7....6..1...7..85........8..29....3....58.5...3.1  #2713
1.3.......5678....78...356...16.7....6..18..7...5...........29....3....58.5...3.1  #2714
1.3...7...56.8....78...356...16.7....6..1.....785........8..29....3....58.5...3.1  #2719
1.3...7...56.8....78...356...16.7....6..1...7..85........8..29....3....58.5...3.1  #2720
1.3...7...56.8....78...356...16.7....6..18....7.5...........29....3....58.5...3.1  #2721
1.3...7...56.8....78...356...16.7....6..18..7...5...........29....3....58.5...3.1  #2723
...4...8.....8912....1.24.52.4....9..3.9.....96.5.1.....82.591.............8..254  #3043
...4...89....8912....1.24.52.4.......3.9.....96.5.1.....82.591.............8..254  #3044
.2.45.7.9...7.9..3....3254..........5...7493.9..5.32...7.....9.64.......8.1.....5  #6228
.2.45.7.9...7.9..3....3254........5.5...7493.9....32...7.....9.64.......8.1.....5  #6230
.2.45.7.9.5.7.9..3....32.4..........5...7493.9..5.32...7.....9.64.......8.1.....5  #6237
.2.45.7.9.5.7.9..3....32.4........5.5...7493.9....32...7.....9.64.......8.1.....5  #6240
...45...9.5...9..37.9.32...2.....6..3.7....15....7.4.25.23.7..4..4......9....5...  #7215
...45...945...9..37.9.32...2.....6..3.7....15....7.4.25.23.7..4.........9...45...  #7216
..345...9.5...9..37.9..2...2.....6..3.7....15....7.4.25.23.7..4..4......9....5...  #7217
..345...945...9..37.9..2...2.....6..3.7....15....7.4.25.23.7..4.........9...45...  #7218
.2.45...9.5...9..37.9.32.........6..3.7....15....7.4.25.23.7..4..4......9....5...  #7219
.2.45...945...9..37.9.32.........6..3.7....15....7.4.25.23.7..4.........9...45...  #7220
.2345...9.5...9..37.9..2.........6..3.7....15....7.4.25.23.7..4..4......9....5...  #7221
.2345...945...9..37.9..2.........6..3.7....15....7.4.25.23.7..4.........9...45...  #7222

One question one might ask is, do all these exceptional puzzles have a tridagon? For the whole list of 7,226 minimals with B ≥ 12, the answer is no:
- only 5,282 have a non-degenerate tridagon
- only 6,113 have a non-degenerate or degenerate-cyclic tridagon
For an example that has none of these, see http://forum.enjoysudoku.com/t-e-1-nightmare-t45664.html
.

[denis_berthier]

.
Here are now the results of the search for high B-rating puzzles for the second sample of 1000 solution grids. The results are still better than in the first 1000.
Same notations as before.

Code: Select all

start with 496,242 "p1U" puzzles
123,029 "p1U-d1" puzzles
2,042 "p1U-B12" puzzles
26,485  "p1U-B12-mins" puzzles
11,625 "p1U-B12-mins-d1" puzzles (which can only have B ≥ 12)

What's new is, we find minimal puzzles up to B = 22.

525 in B16
155 in B17
101 in B18

24 in B19:

Code: Select all

12...6...4.....1...89.......6..41......3.7..2.3726.4.......427.6...7..3.....236.1  #2115
12...6...4.....1...89.......6..41......3.7.62.372..4.......427.6...7..3.....236.1  #2116
...45.......7.9..3.89..2....7.86.39.........7.983..2...37...9.8..2...6...6..7....  #2843
...45...9...7.9..3.89..2....7.86.3..........7.983..2...37...9.8..2...6...6..7....  #2845
1......894.6...1.3.8..3.......3.46..8......529.....3....184.....98.63....4.9.1...  #3943
1..4...894.6...1.3.8..3.......3.46..8......529.....3....18......98.63....4.9.1...  #3944
.2.4.67..4.67.912...9......2.....47...7..4.9.9.4...6.1..28.5.......6....6.13.7...  #4034
...4.67.94.67.912..........2.....4.........929.4.7.6.1..28.5.1.....6...76.13.....  #4063
...4.67.94.67.912..........2.....47........929.4.7.6.1..28.5.1.....6....6.13.7...  #4064
1..4...894...8.12.......5...48....9567..9.....3..4.......51..48....2.9.1...9..25.  #6655
1..4...894...8.12.......5..248.....567..9.....3..4.......51..48....2.9.1...9..25.  #6657
1..45..894...8.12...........48....9567..9.....3..4.......51..48....2.9.1...9..25.  #6665
1..45..894...8.12..........248.....567..9.....3..4.......51..48....2.9.1...9..25.  #6667
1..4...894...8.12.......5....8....9567..9.4...3..4.......51..48....2.9.1...9..25.  #6675
1..4...894...8.12.......5..2.8.....567..9.4...3..4.......51..48....2.9.1...9..25.  #6677
1..45..894...8.12............8....9567..9.4...3..4.......51..48....2.9.1...9..25.  #6685
1..45..894...8.12..........2.8.....567..9.4...3..4.......51..48....2.9.1...9..25.  #6687
1..4...894...8.12.......5....8....9567..9.....3..4.......51..48....2.9.1.1.9..25.  #6693
1..45..894...8.12............8....9567..9.....3..4.......51..48....2.9.1.1.9..25.  #6699
.23.5.7.94........7.9.325.42.5...3..........793....6.8....94......27.....4.3.5...  #8379
.23.5.7.94........7.9.325..2.5.....1........793....6.8....94......27.4...4.3.5...  #8398
.234..7.945.......7.9.325..2.5.....1........793....6.8....9.......27.4...4.3.5...  #8399
.2345.7.94........7.9.325..2.5.....1........793....6.8....9.......27.4...4.3.5...  #8400
.23.5.7.94........7.9.325.42.5...3.......3..79.....6.8....94......27.....4.3.5...  #8402

9 in B20:

Code: Select all

.23......45....1....9....6....87.....7..238.....6.13....8...61...731.2.8..2.6...7  #4899
.23......456...1....9....6....87.....7..238.....6.13....8...61....31.2.8..2.6...7  #4900
.23..6...45....1....9....6....87.....7..238.....6.13....8...61....31.2.8..2.....7  #4901
.....6......78.....89.32....41...8....85...1.59...143..15...9.8.3.....41..4...35.  #5803
.....6......78.....89.32....41...8.5..85...1..9...143..15...9.8.3.....41..4...35.  #5804
.....6.8....78.....89.32....41........85...1.59...143..15...9.8.3.....41..4...35.  #5805
.....6.8....78.....89.32....41.....5..85...1..9...143..15...9.8.3.....41..4...35.  #5806
12.45.........9.2.7...3...4.6..1...7.7.64..92..4.......1....9..6.7.....1.92....46  #11228
12.45.........9.2.7...3...4.6..1...7.7164..92..4............9..6.7.....1.92....46  #11229

5 in B21:

Code: Select all

12.........6....2378..3.......56..9...59.1..6....23.15.9..1....5..69..32...3....1  #3306
12.........6....2378..3.......56..9...59.1..6....23.1539..1....5..69..32........1  #3307
12........56....2378..3.......56..9....9.1..6....23.15.9..1....5..69..32...3....1  #3308
12........56....2378..3.......56..9....9.1..6....23.1539..1....5..69..32........1  #3309
123........6....2378..........56..9...59.1..6....23.15.9..1....5..69..32...3....1  #3310

2 in B22:

Code: Select all

.23......45.7.9...7....25.4.....3.75.9....6.1.4.....92...2.4.....2.95...9..37....  #7017
.23......45.7.9...7.9..25.4...9.3.75......6.1.4.....92...2.4.....2.95...9..37....  #7018

.

[denis_berthier]

.
Here's some update to my previous results.
Still about the same collection.

I've now analysed the first 5 continuous samples of 1,000 solutions grids.

1) Variations among solution grids and samples
As I said previously, there are very large variations between different solution grids, e.g. in the numbers of minimal puzzles for them in the collection. These numbers can vary from 1 to several thousands. This is one interesting result of splitting the global collection of minimals.
Are those variations smoothed out by glueing together 1000 solutions grids into a sample? Yes, of course, but not to the point of not remaining obvious. For the 5 samples, the total numbers of minimals are respectively:
67368
56409
74198
62512
67929
I've also started to study a slice of solution grids in the middle of the file (sample #30, i.e. solution grids 29001 to 30000) for which the number is
53771


2) The T&E(3) expansion phases
As of now, the largest number of (1+BRT)-layers I've found above the p0 layer (consisting of minimals and their BRT-expands) remains 9.


3) The p1U puzzles and their minimals at T&E-depth 1
In [HCCS2,section 6.1 https://www.researchgate.net/publication/381884473_Hierarchical_Classifications_in_Constraint_Satisfaction_Second_Edition,
I noticed that the 1-expands of T&E(3)-expands (i.e. of mith's max-expands) can be in any of T&E(0, 1 or 2) and that those in T&E(1) can have very large B ratings and I found a few thousand puzzles with B ≥ 12.

In the previous posts of this thread, instead of starting from T&E(3)-expand puzzles, I started from puzzles closer to the T&E(3)-minimals, namely the "p1U" puzzles, i.e. the 1-expands of the min-expands (with no redundancies). The result is very large numbers of non-isomorphic minimal puzzles at T&E-depth 1 with extremely large B ratings.
After analysing the 5 samples, I now have the followng numbers of puzzles with B ≥ 12, for each sample:
7226
11625
22339
9704
[Edit] running18109 [/Edit]
Here also, one can see the large variations between samples.

I also have several thousands of puzzles with B ≥ 15.
The maximum B rating reached remains 22.

(Notes:
- the largest known B rating is 30, for a puzzle due to Mauricio; only 2 puzzles with B=30 are known, the second one is due to 1to9only;
- before the above results, there was no collection of puzzles with large B ratings, say B ≥ 12.
)
.

[eleven]

A solution to the B22 above:
.23......45.7.9...7....25.4.....3.75.9....6.1.4.....92...2.4.....2.95...9..37....

Hidden Text: Show

Code: Select all

+------------------------+--------------------+----------------------+
|  *168    2      3      | 45     45    *168  | 79     168    79     |
|   4      5     *168    | 7     *168+3  9    | 138    2      368    |
|   7     *168    9      |*168   d1368   2    | 5     c1368   4      |
+------------------------+--------------------+----------------------+
|   1268   168    168    | 9      12468  3    | 48     7      5      |
| fa2358   9     e578    | 458    2458   78   | 6     b348    1      |
| f 13568  4     e15678  | 1568   1568   1678 | 38     9      2      |
+------------------------+--------------------+----------------------+
|   1568   37    *168+5  | 2     *168    4    | 13789  1368   36789  |
|  *168    37     2      |*168    9      5    | 13478  13468  3678   |
|   9     *168    4      | 3      7     *168  | 2      5      68     |
+------------------------+--------------------+----------------------+

Tridagon 168 (*): 5r7c3 = 3r2c5
3r5c1 = r5c8 - r3c8 = r3c5 == 5r7c3 - r56c3 = 35r56c1
=> -28r5c1

Hidden Text: Show

Code: Select all

+----------------------+----------------------+----------------------+
| 168    2      3      | 45     45     168    | 79    *168    79     |
| 4      5    BT168    | 7     a1368   9      |*138    2     *368    |
| 7      168    9      | 168   b1368   2      | 5     c1368   4      |
+----------------------+----------------------+----------------------+
| 2      168    168    | 9      1468   3      | 48     7      5      |
| 35     9      578    | 45     2      78     | 6      348    1      |
| 13568  4      15678  | 168    1568   1678   | 38     9      2      |
+----------------------+----------------------+----------------------+
| 1568   7     T168+5  | 2     T168    4      | 1389  A168+3  3689   |
| 168    3      2      | 168    9      5      | 1478   1468   678    |
| 9      168    4      | 3      7      168    | 2      5      68     |
+----------------------+----------------------+----------------------+

If 3r2c5 and not 5r7c3, there is a remote triple 168r27c3,r7c5 from the tridagon, and 3r3c8, -3r7c8
This is not possible, because the digit in r7c8 (1,6, or 8) goes to r2c3 (RT), and can't be in box 3.
So 5 must be in r7c3 because of the tridagon.

Hidden Text: Show

Code: Select all

+-------------------+-------------------+-------------------+
|a168   2     3     | 45    45   *6-18  | 79    168   79    |
| 4     5    A168   | 7    B1368  9     | 13    2    C368   |
| 7     168   9     | 168   1368  2     | 5     1368  4     |
+-------------------+-------------------+-------------------+
| 2     168   168   | 9     1468  3     | 48    7     5     |
| 35    9    B78    | 45    2    C78    | 6     34    1     |
| 35    4     1678  | 168   1568  1678  | 38    9     2     |
+-------------------+-------------------+-------------------+
|b168   7     5     | 2     168   4     | 139   1368  3689  |
|b168   3     2     | 168   9     5     | 147   1468  678   |
| 9    c168   4     | 3     7    d168   | 2     5    d68    |
+-------------------+-------------------+-------------------+

kite 1: 1r1c1 = r78c1 - r9c2 = r9c6 => -1r1c6
8 in row 2:
8r2c3 - r5c3 = r5c6
8r2c5
8r2c9 - r9c9 = kite 8 [8r1c1 = r78c1 - r9c2 = 8r9c6]
=> -8r1c6

Hidden Text: Show

Code: Select all

+-------------------+-------------------+-------------------+
| 18    2     3     | 45    45    6     | 79    18    79    |
| 4     5     6     | 7     18    9     | 13    2     38    |
| 7    *18    9     |*18    3     2     | 5     6     4     |
+-------------------+-------------------+-------------------+
| 2     6     18    | 9     148   3     | 48    7     5     |
| 35    9     78    | 45    2     78    | 6     34    1     |
| 35    4     178   | 168   1568  178   | 38    9     2     |
+-------------------+-------------------+-------------------+
| 168   7     5     | 2     168   4     | 139   138   389   |
| 168   3     2     | 6-18  9     5     | 147   148   78    |
| 9    *18    4     | 3     7    *18    | 2     5     6     |
+-------------------+-------------------+-------------------+

remote pair 18: r3c4 - r2c2 - r9c2 - r9c6 => -18r8c4, stte

[jco]

A solution to the B22 above:
.23......45.7.9...7....25.4.....3.75.9....6.1.4.....92...2.4.....2.95...9..37....
(...)

Nice solve! Thank you for sharing it.

[denis_berthier]

.
Some of the high B-rating puzzles still have a non-degenerate tridagon, with 1 or more guardians. It works as for the T&E(3) puzzles, i.e. it makes them simpler but what remains may be easy or extremely hard. One could say exactly the same of any rating and any pattern not considered in the rating: adding the pattern has totally unpredictable effects.
Some puzzles don't have such a tridagon, but they have some pattern close to it: I've given an example in the Puzzles section.

Considering the way the puzzles were obtained, having a tridagon or a very close pattern shouldn't be a surprise.

For the B22 puzzle, I have three solutions:
- one in B22 (by definition);
- one using only the tridagon, in W7+Trid-OR2-W7;
- one using the tridagon + eleven's EL14c30 3-digit impossible pattern (used for only 1 elimination), in W5+(Trid+EL14c30)-OR3-W5 - below:

Code: Select all

Resolution state after Singles and whips[1]:
   +-------------------+-------------------+-------------------+
   ! 168   2     3     ! 14568 14568 168   ! 1789  168   6789  !
   ! 4     5     168   ! 7     1368  9     ! 138   2     368   !
   ! 7     168   9     ! 168   1368  2     ! 5     1368  4     !
   +-------------------+-------------------+-------------------+
   ! 1268  168   168   ! 9     12468 3     ! 48    7     5     !
   ! 2358  9     578   ! 458   2458  78    ! 6     348   1     !
   ! 13568 4     15678 ! 1568  1568  1678  ! 38    9     2     !
   +-------------------+-------------------+-------------------+
   ! 1568  13678 1568  ! 2     168   4     ! 13789 1368  36789 !
   ! 168   13678 2     ! 168   9     5     ! 13478 13468 3678  !
   ! 9     168   4     ! 3     7     168   ! 2     5     68    !
   +-------------------+-------------------+-------------------+
177 candidates

hidden-pairs-in-a-column: c2{n3 n7}{r7 r8} ==> r8c2≠8, r8c2≠6, r8c2≠1, r7c2≠8, r7c2≠6, r7c2≠1
hidden-pairs-in-a-row: r1{n7 n9}{c7 c9} ==> r1c9≠8, r1c9≠6, r1c7≠8, r1c7≠1
hidden-pairs-in-a-row: r1{n4 n5}{c4 c5} ==> r1c5≠8, r1c5≠6, r1c5≠1, r1c4≠8, r1c4≠6, r1c4≠1

Code: Select all

Trid-OR2-relation for digits 1, 6 and 8 in blocks:
        b1, with cells (marked #): r1c1, r2c3, r3c2
        b2, with cells (marked #): r1c6, r2c5, r3c4
        b7, with cells (marked #): r8c1, r7c3, r9c2
        b8, with cells (marked #): r8c4, r7c5, r9c6
with 2 guardians (in cells marked @): n3r2c5 n5r7c3
   +----------------------+----------------------+----------------------+
   ! 168#   2      3      ! 45     45     168#   ! 79     168    79     !
   ! 4      5      168#   ! 7      1368#@ 9      ! 138    2      368    !
   ! 7      168#   9      ! 168#   1368   2      ! 5      1368   4      !
   +----------------------+----------------------+----------------------+
   ! 1268   168    168    ! 9      12468  3      ! 48     7      5      !
   ! 2358   9      578    ! 458    2458   78     ! 6      348    1      !
   ! 13568  4      15678  ! 1568   1568   1678   ! 38     9      2      !
   +----------------------+----------------------+----------------------+
   ! 1568   37     1568#@ ! 2      168#   4      ! 13789  1368   36789  !
   ! 168#   37     2      ! 168#   9      5      ! 13478  13468  3678   !
   ! 9      168#   4      ! 3      7      168#   ! 2      5      68     !
   +----------------------+----------------------+----------------------+

EL14c30-OR3-relation for digits: 1, 6 and 8
   in cells (marked #): (r2c3 r3c5 r3c4 r3c2 r1c8 r1c6 r1c1 r8c4 r8c1 r9c6 r9c2 r7c8 r7c5 r7c3)
   with 3 guardians (in cells marked @) : n3r3c5 n3r7c8 n5r7c3 
   +----------------------+----------------------+----------------------+
   ! 168#   2      3      ! 45     45     168#   ! 79     168#   79     !
   ! 4      5      168#   ! 7      1368   9      ! 138    2      368    !
   ! 7      168#   9      ! 168#   1368#@ 2      ! 5      1368   4      !
   +----------------------+----------------------+----------------------+
   ! 1268   168    168    ! 9      12468  3      ! 48     7      5      !
   ! 2358   9      578    ! 458    2458   78     ! 6      348    1      !
   ! 13568  4      15678  ! 1568   1568   1678   ! 38     9      2      !
   +----------------------+----------------------+----------------------+
   ! 1568   37     1568#@ ! 2      168#   4      ! 13789  1368#@ 36789  !
   ! 168#   37     2      ! 168#   9      5      ! 13478  13468  3678   !
   ! 9      168#   4      ! 3      7      168#   ! 2      5      68     !
   +----------------------+----------------------+----------------------+

whip[5]: c7n9{r7 r1} - c7n7{r1 r8} - r8c2{n7 n3} - r8c9{n3 n6} - r9c9{n6 .} ==> r7c7≠8
Trid-OR2-whip[5]: c1n3{r5 r6} - c1n5{r6 r7} - OR2{{n5r7c3 | n3r2c5}} - b3n3{r2c7 r3c8} - r5n3{c8 .} ==> r5c1≠2
singles ==> r4c1=2, r5c5=2
At least one candidate of a previous EL14c30s-OR4-relation between candidates n2r4c5 n4r4c5 n5r7c1 n3r2c5 has just been eliminated.
There remains an EL14c30s-OR3-relation between candidates: n4r4c5 n5r7c1 n3r2c5

EL14c30s-OR3-whip[4]: r5n3{c1 c8} - r5n4{c8 c4} - OR3{{n4r4c5 n5r7c1 | n3r2c5}} - b3n3{r2c7 .} ==> r5c1≠5
Trid-OR2-whip[3]: OR2{{n3r2c5 | n5r7c3}} - c1n5{r7 r6} - r6n3{c1 .} ==> r2c7≠3
z-chain[4]: r4n6{c3 c5} - b5n4{r4c5 r5c4} - r5n5{c4 c3} - c3n7{r5 .} ==> r6c3≠6
z-chain[4]: r4n1{c3 c5} - b5n4{r4c5 r5c4} - r5n5{c4 c3} - c3n7{r5 .} ==> r6c3≠1
Trid-OR2-whip[4]: r5n3{c1 c8} - r3n3{c8 c5} - OR2{{n3r2c5 | n5r7c3}} - c1n5{r7 .} ==> r6c1≠3
singles ==> r5c1=3, r6c7=3
Trid-OR2-whip[5]: OR2{{n3r2c5 | n5r7c3}} - r5n5{c3 c4} - b5n4{r5c4 r4c5} - r4c7{n4 n8} - r2c7{n8 .} ==> r2c5≠1
z-chain[2]: r9n1{c2 c6} - b2n1{r1c6 .} ==> r3c2≠1
whip[5]: r2c7{n8 n1} - b1n1{r2c3 r1c1} - r1n8{c1 c6} - r3n8{c4 c2} - r9n8{c2 .} ==> r2c9≠8
whip[1]: c9n8{r9 .} ==> r7c8≠8, r8c7≠8, r8c8≠8
whip[5]: c5n5{r6 r1} - c5n4{r1 r4} - r4c7{n4 n8} - r2n8{c7 c3} - b4n8{r4c3 .} ==> r6c5≠8
whip[5]: r3c2{n8 n6} - r3c4{n6 n1} - r1c6{n1 n6} - r9n6{c6 c9} - r2n6{c9 .} ==> r3c5≠8
finned-swordfish-in-columns: n8{c5 c7 c3}{r7 r2 r4} ==> r4c2≠8
z-chain[5]: r3n1{c5 c8} - r2c7{n1 n8} - r1n8{c8 c1} - c2n8{r3 r9} - r9n1{c2 .} ==> r1c6≠1
whip[1]: b2n1{r3c5 .} ==> r3c8≠1
finned-x-wing-in-columns: n1{c6 c2}{r9 r6} ==> r6c1≠1
whip[1]: r6n1{c6 .} ==> r4c5≠1
biv-chain[5]: r3n1{c4 c5} - r3n3{c5 c8} - r2c9{n3 n6} - r9c9{n6 n8} - c2n8{r9 r3} ==> r3c4≠8
biv-chain[3]: r3n8{c2 c8} - r2c7{n8 n1} - b1n1{r2c3 r1c1} ==> r1c1≠8
Trid-OR2-whip[4]: OR2{{n5r7c3 | n3r2c5}} - b2n8{r2c5 r1c6} - r5c6{n8 n7} - c3n7{r5 .} ==> r6c3≠5
z-chain[5]: r4n4{c5 c7} - c7n8{r4 r2} - b3n1{r2c7 r1c8} - r1c1{n1 n6} - r6n6{c1 .} ==> r4c5≠6
whip[1]: b5n6{r6c6 .} ==> r6c1≠6
naked-pairs-in-a-row: r4{c5 c7}{n4 n8} ==> r4c3≠8
z-chain[3]: c1n6{r8 r1} - b1n1{r1c1 r2c3} - r4c3{n1 .} ==> r7c3≠6
Trid-OR2-whip[5]: c3n6{r2 r4} - c3n1{r4 r7} - OR2{{n5r7c3 | n3r2c5}} - b3n3{r2c9 r3c8} - r3n8{c8 .} ==> r2c3≠8
hidden-single-in-a-block ==> r3c2=8
naked-pairs-in-a-block: b3{r2c9 r3c8}{n3 n6} ==> r1c8≠6
naked-pairs-in-a-column: c3{r2 r4}{n1 n6} ==> r7c3≠1
x-wing-in-rows: n8{r2 r4}{c5 c7} ==> r7c5≠8
t-whip[2]: r1n6{c6 c1} - b7n6{r8c1 .} ==> r9c6≠6
biv-chain[3]: r7c5{n6 n1} - r9c6{n1 n8} - r9c9{n8 n6} ==> r7c8≠6, r7c9≠6
finned-x-wing-in-rows: n6{r7 r1}{c1 c5} ==> r3c5≠6, r2c5≠6
swordfish-in-rows: n6{r2 r4 r9}{c9 c3 c2} ==> r8c9≠6
biv-chain[3]: r9c6{n1 n8} - r1c6{n8 n6} - r3c4{n6 n1} ==> r8c4≠1
finned-x-wing-in-rows: n1{r1 r8}{c1 c8} ==> r7c8≠1
stte
.

[denis_berthier]

.
I've now analysed 9 samples of 1000 solution grids each (about 7.5% of the collection of solution grids), corresponding to 576697 minimal puzzles.

The maximum number of T&E(3) layers I found remains 9.

I've also studied the T&E-expands ("max-expands" in mith's vocabulary).
The above samples together give rise to 9614 T&E(3)-expands.
The question I asked was: how do they occupy the various layers? Said otherwise, at which layer do T&E(3)-expands occur?

Code: Select all

p0     p1      p2      p3      p4      p5      p6      p7      p8      p9      p10
6,21   17,19   24,55   21,87   16,37   8,08    3,99    1,32    0,35    0,05     0,00

Thus:
- 6,21% of the T&E(3)-expands are in layer p0, i.e. after a simple BRT-expansion;
- the largest percentages occur in layers p2 (24.55%) and p3 (21.87%);
- there are still 0.05% of T&E(3)-expands in layer p9. That's a very small percentage, but if you multiply by the total number of T&E(3-expands, it makes 5 T&E(3) puzzles on the p9 border.

Globally, this shows one can have a significant number of (1+BRT)-expansions before leaving T&E(3). My interpretation is, the non-degenerate tridagon pattern is extremely stable under the random addition of clues and under BRT-expansion. Moreover, it is not so easy to short-circuit its internal T&E3) complexity by using other parts of the puzzles (as must be the case for T&E(2 or 1) puzzles that have the pattern).

My plans are now to analyse different collections at different T&E-depths, with and without tridagons, and to see how many layers one can obtain while remaining at the same T&E-depth. Don't be too impatient about it; that will require some time.

The scripts I'm writing will be published in SudoRules after I've finished testing them.
.

[denis_berthier]

.
Once the layered structure of T&E(n) is defined, it's easy to define the distance of a puzzle in T&E(n) to the T&E(n-1) boundary: it's the minimum number of (1+BRT)-expansion steps (after an initial BRT-expansion) before reaching the boundary, i.e. one of its T&E(3)-expands.
Note: there may be many expansions paths to the boundary; distance considers only the shortest one(s).

For the moment, let's stick to T&E(3).
I mentioned it previously: any minimal puzzle in T&E(3) may have several (1+BRT) expansions until it reaches one of its T&E(3)-expands and any T&E(3)-expand may come from several minimal puzzles.
As a result, the following distributions are generally different (although the max value for distances can only be ≤ the number of layers):
- the distribution of layers to which the T&E(3)-expands belong (given in my previous post for 9,000 solution grids);
- the distribution of distances of the minimal puzzles to the inner side of the T&E(3) boundary with T&E(<3).

Below are the two distributions for the sample of the first 1000 solution grids.

Code: Select all

Distribution (in %) of layers "on the boundary":
p0     p1      p2      p3      p4      p5     p6     p7     p8     
5.99   15.07   25.94   19.94   18.45   8.80   4.12   1.31   0.37

Code: Select all

Distribution (in %) of distances of minimals to the boundary:
0      1      2       3       4       5       6       7       8       
0.65   4.31   13.21   11.51   21.70   18.59   17.34   8.85    3.84

.

[denis_berthier]

.
I've now analysed 13,000 solution grids (about 19%) of the above-mentioned T&E(3) collection.
The max number of layers within T&E(3) is now 10 and the updated distribution of layers (in %) on the T&E(3) side of the T&E(3) to T&E(<3) boundary is:

Code: Select all

p0     p1      p2      p3      p4      p5     p6     p7     p8     p9     p10
6,17   17,35   24,61   22,48   16,08   7,87   3,86   1,20   0,34   0,04   0,01

.

[coloin]

Perhaps you could post the minimal puzzle with 10 layers !! ?

Perhaps an example of a puzzle expansion is useful to explain ..?

Here is a minimal puzzle from the WheresMyHammer puzzle ... TE3

Code: Select all

+---+---+---+
|89.|..7|..5|
|5.7|4..|.96|
|...|...|...|
+---+---+---+
|...|.4.|...|
|4..|.75|6..|
|65.|8.9|4..|
+---+---+---+
|.8.|...|.61|
|76.|...|.32|
|...|.8.|9..|
+---+---+---+    28 clues minimal   -->  with 3 singles..

+---+---+---+
|89.|..7|..5|
|5.7|4.8|.96|
|...|...|...|
+---+---+---+
|.7.|.4.|...|
|4..|.75|6..|
|65.|8.9|4..|
+---+---+---+
|.8.|...|.61|
|76.|...|832|
|...|.8.|9..|
+---+---+---+  31 clues  --->   3 more singles after pointing on row9

+---+---+---+
|89.|..7|.45|
|5.7|4.8|.96|
|.4.|...|...|
+---+---+---+
|.7.|.4.|...|
|4..|.75|6..|
|65.|8.9|4..|
+---+---+---+
|.8.|...|.61|
|76.|...|832|
|...|.8.|9.4|
+---+---+---+  34 clues  -->   2 more singles after claiming and hidden pair box 2

+---+---+---+
|89.|.67|.45|
|5.7|4.8|.96|
|.46|...|...|
+---+---+---+
|.7.|.4.|...|
|4..|.75|6..|
|65.|8.9|4..|
+---+---+---+
|.8.|...|.61|
|76.|...|832|
|...|.8.|9.4|
+---+---+---+  36 clues     TE3 limit reached...

dratted uniqeness r8c45 inserts a 4@r8c6

+---+---+---+
|89.|.67|.45|
|5.7|4.8|.96|
|.46|...|...|
+---+---+---+
|.7.|.4.|...|
|4..|.75|6..|
|65.|8.9|4..|
+---+---+---+
|.84|...|.61|
|76.|..4|832|
|...|.8.|9.4|
+---+---+---+  38 clues not TE3 anymore

so how many layers / depth has this original minimal puzzle ?

EDIT
The 36 clue "max-expand" has 175 minimal puzzles
on applying my expansion [gsf -E] this gives 3 expands....

Code: Select all

89..67.455.74.8.96.46.......7..4....4...756..65.8.94.........6.76....832....8.9.4 #  34 clues           
89..67.455.74.8.96.46.......7..4....4...756..65.8.94...8.....6.76....832....8.9.4 #  35 clues           
89..67.455.74.8.96.46.......7..4....4...756..65.8.94...8.....6176....832....8.9.4 #  36 clues           
                                                                                                       
89..67.455.74.8.96.46.......7..4....4...756..65.8.94...8.....6176....832....8.9.4 #  36 clues max expand


[P.O.]

Perhaps an example of a puzzle expansion is useful to explain ..?

i would also like to see the details of what Denis does when he talks about (1+BRT)-expansion
same analysis for this puzzle:
89...7..55.74...96.............4....4...756..65.8.94...8.....6176.....32....8.9..
basics:

Hidden Text: Show

Code: Select all

( n7r4c2   n8r8c7   n8r2c6 )

intersections:
((((6 0) (1 5 2) (1 2 3 6)) ((6 0) (3 5 2) (1 2 3 5 6 9)))
 (((4 0) (9 8 9) (4 5 7)) ((4 0) (9 9 9) (4 7))) ( n4r1c8   n4r9c9   n4r3c2 ))

TRIPLET BOX: ((1 4 2) (1 2 3)) ((2 5 2) (1 2 3)) ((3 6 2) (1 2 3))
(((1 5 2) (1 2 3 6)) ((3 4 2) (1 2 3 5 9)) ((3 5 2) (1 2 3 5 6 9)))

( n6r1c5   n6r3c3 )


Code: Select all

after basics:
8       9       123     123     6       7       123     4       5               
5       123     7       4       123     8       123     9       6               
123     4       6       59      59      123     1237    1278    378             
1239    7       12389   1236    4       1236    1235    1258    389             
4       123     12389   123     7       5       6       128     389             
6       5       123     8       123     9       4       127     37               
239     8       23459   23579   2359    234     57      6       1               
7       6       1459    159     159     14      8       3       2               
123     123     1235    123567  8       1236    9       57      4               
151 candidates. 36 values.

89..67.455.74.8.96.46.......7..4....4...756..65.8.94...8.....6176....832....8.9.4

after T&E(2,Singles):
8     9     123   123   6     7     123   4     5             
5     123   7     4     123   8     123   9     6             
123   4     6     59    59    123   1237  278   78             
1239  7     89    16    4     1236  25    1258  389           
4     123   289   123   7     5     6     128   389           
6     5     123   8     123   9     4     127   37             
29    8     45    2357  2359  234   57    6     1             
7     6     459   159   159   14    8     3     2             
123   123   1235  67    8     26    9     57    4             
128 candidates. 36 values.


the format is (cell value)
becomes te1
((25 7) (26 2) (28 9) (31 1) (33 6) (34 2) (35 5) (39 2) (55 2) (58 7) (59 9) (61 5) (66 9) (75 5)
(76 6) (78 2) (80 7))
becomes te2
((3 1) (4 2) (7 3) (11 2) (14 3) (16 1) (19 3) (22 9) (23 5) (24 1) (27 8) (30 8) (36 3) (38 1)
(40 3) (44 8) (45 9) (48 3) (50 2) (53 1) (54 7) (57 4) (60 3) (67 5) (68 1) (69 4) (73 1) (74 3))

[denis_berthier]

.
The puzzle you call "WheresMyHammer" has only 2 expansion phases above p0 (all in gsf's solution minlex form; notations as defined in previous post):

Code: Select all

T&E(3) expansion phase p0:
1 mins puzzle:
...4.....4...892.66..7.2..4.65...8...31...6.79..8.......2..79.8.96.4..72.........; 28c
1 ME puzzle:
...4..7..4...892.66..7.2..4.65...8..831...6.79..8.......2..79.8.96.48.72.........; 31c
1 MEU puzzle:
...4..7..4...892.66..7.2..4.65...8..831...6.79..8.......2..79.8.96.48.72.........; 31c

T&E(3) expansion phase p1:
50 p1 puzzles
50 p1U puzzles
5 p1U-d3 puzzles
2 p1EU-d3 puzzles:
...4..7..4...892.66..7.2..4.65...8..831...6.79.48......42..79.8.96.48.72......4..; 34c
...4..7..4...892.66..7.2..4.65...8..831...6.79..8.......26.79.8.96.48.72.......6.; 33c

T&E(3) expansion phase p2:
95 p1EU-d3-p2 puzzles
95 p1EU-d3-p2U puzzles
5 p1EU-d3-p2U-d3 puzzles
1 p1EU-d3--p2EU-d3 puzzles:
...4..7..4...892.66..7.2..4.65...8..831...6.79.48......426.79.8.96.48.72......46.; 36c

T&E(3) expansion phase p3:
45 p1EU-d3--p2EU-d3-p3 puzzles
45 p1EU-d3--p2EU-d3-p3U puzzles
0 p1EU-d3--p2EU-d3-p3U-d3 puzzles
0 p1EU-d3--p3EU-d3 puzzles

For the puzzle(s) with 10 expansion phases, it will take more time. I haven't yet written the scripts to extract individual paths to the boundary. It's more complicated than here when there are hundreds of thousands of puzzles.

[Edit]: in aider to avoid any ambiguities, I've replaced the word "layer" by "expansion phase".
.

[denis_berthier]

Perhaps an example of a puzzle expansion is useful to explain ..?

i would also like to see the details of what Denis does when he talks about (1+BRT)-expansion
same analysis for this puzzle:
89...7..55.74...96.............4....4...756..65.8.94...8.....6176.....32....8.9..

It's the same puzzle !
(1+BRT)-expansion is 1-expansion followed by BRT-expansion (or exp. by Singles)
.

[coloin]

.
The puzzle you call "WheresMyHammer" has only 2 layers above p0

I can see now what each layer of singles is ... 28->31->34->36 clues .... so the 3 layers are as outlined .. thanks for that
Certainly there are numerous minimal puzzles associated with each "max-expand" and even more numerus non-minimal puzzles [29 to 35 clues]

I was perhaps thinking that those minimal puzzles which terminate at the max-expand with fewer additional clues would tend to be more complex ... ?

[denis_berthier]

I was perhaps thinking that those minimal puzzles which terminate at the max-expand with fewer additional clues would tend to be more complex ... ?

At this point, I have no data to support this idea. Don't forget that the layers are purely descriptive and a priori unrelated to any solution method. But it'd be worth checking.
The main point here is taking BRT-equivalence seriously: instead of adding clues one by one until you reach the T&E(3) boundary, any time you add a clue, you also do a BRT-expansion; you are sure to keep the same classifs/ratings. This will make fewer steps to the boundary and fewer T&E-depth calculations.
.