(1+BRT) expansion paths within T&E(n) and beyond

Everything about Sudoku that doesn't fit in one of the other sections

Re: The layered structure of T&E-depth d

Postby denis_berthier » Wed May 07, 2025 5:37 am

.
One thing possibly worth noticing about the above puzzle with a very large number of expansion steps within T&E(3) is, if you consider both the original puzzle (or its BRT-expand) and the max-expanded one (1st line), they have the same resolution state after Singles, whips[1] and Pairs - and the same tridagon (with the same unique guardian).

Code: Select all
   +----------------------+----------------------+----------------------+
   ! 1      248#   3      ! 45     2458   6      ! 7      248#   9      !
   ! 248#   5      7      ! 19     248    19     ! 248#   36     36     !
   ! 9      6      248#   ! 3      248    7      ! 5      1      248#   !
   +----------------------+----------------------+----------------------+
   ! 248    248    248    ! 56     9      3      ! 1      56     7      !
   ! 5      39     6      ! 7      1      2      ! 489    348    348    !
   ! 7      39     1      ! 456    45     8      ! 29     2356   2356   !
   +----------------------+----------------------+----------------------+
   ! 3      248#   9      ! 128    7      145    ! 6      2458#@ 12458  !
   ! 6      7      248#   ! 128    3      145    ! 248#   9      12458  !
   ! 248#   1      5      ! 289    6      49     ! 3      7      248#   !
   +----------------------+----------------------+----------------------+
tridagon for digits 2, 4 and 8 in blocks:
        b9, with cells (marked #): r7c8 (target cell, marked @), r9c9, r8c7
        b7, with cells (marked #): r7c2, r9c1, r8c3
        b3, with cells (marked #): r1c8, r3c9, r2c7
        b1, with cells (marked #): r1c2, r3c3, r2c1
 ==> r7c8≠2,4,8
naked-single ==> r7c8=5


It means we've been able to add 10 independent clues with the following BRT-expansions, for a total of 14 clues added, without essentially changing the puzzle.

From:
Code: Select all
     +-------+-------+-------+
     ! 1 . . ! . . . ! 7 . 9 !
     ! . 5 . ! . . . ! . . . !
     ! 9 . . ! 3 . . ! 5 1 . !
     +-------+-------+-------+
     ! . . . ! . 9 . ! . . 7 !
     ! 5 . 6 ! . . 2 ! . . . !
     ! . . 1 ! . . 8 ! . . . !
     +-------+-------+-------+
     ! 3 . . ! . 7 . ! 6 . . !
     ! . . . ! . 3 . ! . 9 . !
     ! . 1 5 ! . 6 . ! 3 . . !
     +-------+-------+-------+

to:
Code: Select all
     +-------+-------+-------+
     ! 1 . 3 ! . . 6 ! 7 . 9 !
     ! . 5 7 ! . . . ! . . . !
     ! 9 6 . ! 3 . 7 ! 5 1 . !
     +-------+-------+-------+
     ! . . . ! . 9 3 ! 1 . 7 !
     ! 5 . 6 ! 7 1 2 ! . . . !
     ! 7 . 1 ! . . 8 ! . . . !
     +-------+-------+-------+
     ! 3 . 9 ! . 7 . ! 6 . . !
     ! 6 7 . ! . 3 . ! . 9 . !
     ! . 1 5 ! . 6 . ! 3 7 . !
     +-------+-------+-------+

.
denis_berthier
2010 Supporter
 
Posts: 4460
Joined: 19 June 2007
Location: Paris

Re: The layered structure of T&E-depth d

Postby P.O. » Wed May 07, 2025 7:09 am

what i think about it so far:
there are 3 categories of values: the one that keeps the puzzle in te3, the one that puts it in te2 and the one that puts it in te1
Code: Select all
te3
 ((3 3) (6 6) (12 7) (20 6) (24 7) (33 3) (34 1) (40 7) (41 1) (46 7) (57 9) (64 6) (65 7) (80 7))
te2:
 ((2 2) (4 4) (5 5) (8 8) (10 4) (13 1) (14 8) (15 9) (16 2) (17 3) (18 6) (21 8) (23 2) (27 4)
 (28 2) (29 8) (30 4) (38 9) (43 8) (44 4) (45 3) (47 3) (50 4) (52 9) (53 2) (56 4) (58 2) (60 1)
 (66 2) (67 8) (69 5) (70 4) (72 1) (73 8) (76 9) (78 4) (81 2))
te1
 ((31 5) (35 6) (49 6) (54 5) (62 5) (63 8))

once again the values that keep the puzzle in te3 are all placed ’after basics’
basics:
Hidden Text: Show
Code: Select all
( n3r4c6   n7r9c8   n9r7c3 )

intersections:
((((8 0) (7 4 8) (1 2 4 5 8)) ((8 0) (8 4 8) (1 2 4 5 8)) ((8 0) (9 4 8) (2 4 8 9)))
 (((7 0) (2 6 2) (1 4 6 7 9)) ((7 0) (3 6 2) (4 6 7)))
 (((6 0) (1 6 2) (4 5 6)) ((6 0) (2 6 2) (1 4 6 7 9)) ((6 0) (3 6 2) (4 6 7)))
 (((3 0) (5 2 4) (3 4 7 8 9)) ((3 0) (6 2 4) (2 3 4 7 9)))
 (((2 0) (7 4 8) (1 2 4 5 8)) ((2 0) (8 4 8) (1 2 4 5 8)) ((2 0) (9 4 8) (2 4 8 9))) NIL)

TRIPLET ROW: ((4 1 4) (2 4 8)) ((4 2 4) (2 4 8)) ((4 3 4) (2 4 8))
(((4 4 5) (1 4 5 6)) ((4 7 6) (1 2 4 8)) ((4 8 6) (2 4 5 6 8)) ((5 2 4) (3 4 7 8 9))
 ((6 1 4) (2 4 7)) ((6 2 4) (2 3 4 7 9)))

( n1r4c7   n7r6c1   n7r5c4   n1r5c5 )

intersections:
((((4 0) (6 4 5) (4 5 6)) ((4 0) (6 5 5) (4 5))))

TRIPLET COL: ((1 4 2) (4 5)) ((4 4 5) (5 6)) ((6 4 5) (4 5 6))
(((2 4 2) (1 4 9)) ((7 4 8) (1 2 4 5 8)) ((8 4 8) (1 2 4 5 8)) ((9 4 8) (2 4 8 9)))

intersections:
((((5 0) (7 6 8) (1 4 5)) ((5 0) (8 6 8) (1 4 5)))
 (((4 0) (7 6 8) (1 4 5)) ((4 0) (8 6 8) (1 4 5)) ((4 0) (9 6 8) (4 9)))
 ( n6r3c2   n6r8c1   n3r1c3   n7r2c3   n7r8c2   n7r3c6   n6r1c6 ))

TRIPLET ROW: ((2 1 1) (2 4 8)) ((2 5 2) (2 4 8)) ((2 7 3) (2 4 8))
(((2 8 3) (2 3 4 6 8)) ((2 9 3) (2 3 4 6 8)))

Code: Select all
after basics:
1      248    3      45     2458   6      7      248    9               
248    5      7      19     248    19     248    36     36             
9      6      248    3      248    7      5      1      248             
248    248    248    56     9      3      1      56     7               
5      39     6      7      1      2      489    348    348             
7      39     1      456    45     8      29     2356   2356           
3      248    9      128    7      145    6      2458   12458           
6      7      248    128    3      145    248    9      12458           
248    1      5      289    6      49     3      7      248         
125 candidates. 38 values.
 
1.3..67.9.57......96.3.751.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37.

leaving aside the 3 singles of the initialization that you place in layer 0 there remain 11 values to constitute the layers, so the question is: what justifies the order of the values, because if a different order is chosen another organization of layers is obtained
for example taking the reverse order of yours:
Code: Select all
p1 6r1c6 28c brt
p2 6r3c2 29c brt 6r8c1 30c
p3 7r3c6 31c brt
p4 7r2c3 32c brt 7r8c2 7r6c1 7r5c4 3r1c3 36c
p5 1r5c5 37c brt 1r4c7 38c
P.O.
 
Posts: 1904
Joined: 07 June 2021

Re: The layered structure of T&E-depth d

Postby denis_berthier » Wed May 07, 2025 7:21 am

.
Back to another topic of this thread: the generation of puzzles in T&E(1), with extreme B ratings.

Starting from minimal puzzles in some T&E(n), one can first expand them by Singles (not changing their rating/classification) and then expand them by adding a single clue (1-expansion). Some will remain in T&E(d), some will fall into a shallower T&(n-x).
The question here is: what about those that fall into T&E(1) and that have a high B rating, say B ≥ 12 ?
One can look for their minimals, all of which are guaranteed to be in T&E(1) and to have B ≥ 12.

The question is: can we produce many new puzzles with extremely high B ratings that way?
In a previous post, I gave an answer in the following case:
- starting from minimal puzzles in T&E(3), one can get lots of puzzles in T&E(1) with B ≥ 12.
I can now add that, based on 950,685 minimal puzzles (corresponding to 145,614 unique min-expands), one can produce 175,453 minimal puzzles in T&E(1) with B ≥ 12, some exceptional ones of which reach B = 22.
This is about 1.2 minimal puzzles with B ≥ 12 produced for each min-expand in T&E(3).

Here's my new result:
- starting from minimal 6259 puzzles in T&E(2) with BxB ≥ 7 (noted B 7B+ below), assembled from coloin's 4 Mastermind collections, (corresponding to 2,543 unique min-expands), one can produce 10,979 minimal puzzles in T&E(1) with B ≥ 12, some exceptional ones of which reach B = 21.
This is about 4.3 minimal puzzles with B ≥ 12 produced for each min-expand in B7B+ .

The common point between the two starting collections is the presence of a non-degenerate tridagon in all their minimals (except 3 old ones in the B7B+ collection).
In both cases, the process is extremely productive. I'm not sure about why it is still more productive when starting from B7B+ puzzles.
.
Last edited by denis_berthier on Wed May 07, 2025 1:46 pm, edited 2 times in total.
denis_berthier
2010 Supporter
 
Posts: 4460
Joined: 19 June 2007
Location: Paris

Re: The layered structure of T&E-depth d

Postby denis_berthier » Wed May 07, 2025 7:23 am

.
P.O.
Basics are irrelevant to the definition of the expansions.
.
denis_berthier
2010 Supporter
 
Posts: 4460
Joined: 19 June 2007
Location: Paris

Re: The layered structure of T&E-depth d

Postby P.O. » Wed May 07, 2025 7:31 am

denis_berthier wrote:Basics are irrelevant to the definition of the expansions.

i know you've already said it, but it's a recurring observation.
what about the order of the values ​​to build the layers?
P.O.
 
Posts: 1904
Joined: 07 June 2021

Re: Expansion paths within T&E(n) and beyond

Postby denis_berthier » Wed May 07, 2025 7:36 am

.
I've changed the title of the thread in order to better reflect what's common to all the sub-topics dealt with in it.
denis_berthier
2010 Supporter
 
Posts: 4460
Joined: 19 June 2007
Location: Paris

Re: The layered structure of T&E-depth d

Postby denis_berthier » Wed May 07, 2025 8:00 am

P.O. wrote:what about the order of the values ​​to build the layers?

The layers have been abstractly defined in the 1st post.
Layers and expansion paths are different things.

Suppose you're on the top of a 100 meter high hill (say a convex one to make things simple) - the top is the minimal puzzle.
Every step you make can only make you go down by at least 1m (the 1-expansion), but it may be more (the BRT expansion following it).

You want to reach a bar on the sunny side at the base of the hill (the puzzle on the T&E(3) border).

There are zillions of paths to achieve this goal: one that uses the steepest descent at any time, some that slowly slither down on the sunny side, some that make several complete turns around the hill.
.
denis_berthier
2010 Supporter
 
Posts: 4460
Joined: 19 June 2007
Location: Paris

Re: (1+BRT) expansion paths within T&E(n) and beyond

Postby P.O. » Wed May 07, 2025 8:15 am

exactly, there are 39,916,800 permutations of the 11 values which will define a large number of different layer organizations, what is the rationale for choosing one rather than another to characterize the puzzle?
P.O.
 
Posts: 1904
Joined: 07 June 2021

Re: (1+BRT) expansion paths within T&E(n) and beyond

Postby denis_berthier » Wed May 07, 2025 8:36 am

.
The shortest path intrinsically characterises the puzzle; that's what I've defined as the distance to the boundary.
But that doesn't mean the longest paths are not interesting. On the contrary, they show that without any previous knowledge of the effect of adding a clue, one can keep adding clues that don't bring us much closer to the boundary.

This example doesn't show it, but there are cases where the minimal puzzle has lots of guardians and intermediate puzzles progressively have fewer ones.
.
denis_berthier
2010 Supporter
 
Posts: 4460
Joined: 19 June 2007
Location: Paris

Re: (1+BRT) expansion paths within T&E(n) and beyond

Postby P.O. » Wed May 07, 2025 8:50 am

ok why not maximize the number of layers, so for each puzzle the maximum limit is the number of values that keep the puzzle in te3 minus that of the min-expand, which implies no brt expansion and maybe for this puzzle there is such a permutation of the 11 values
P.O.
 
Posts: 1904
Joined: 07 June 2021

Re: (1+BRT) expansion paths within T&E(n) and beyond

Postby denis_berthier » Wed May 07, 2025 9:52 am

.
This thread is about (1+BRT) expansions, not about 1-expansions alone. The motivation is to take BRT-equivalence seriously.
In [HCCS2], I've already given stats about the number of clues of minimals in T&E(3) and of their T&E(3)-expands, e.g. for their mean values: 27.11 vs 34.03.
.
denis_berthier
2010 Supporter
 
Posts: 4460
Joined: 19 June 2007
Location: Paris

Re: (1+BRT) expansion paths within T&E(n) and beyond

Postby denis_berthier » Wed May 07, 2025 3:08 pm

.
One practical good reason for doing slow expansion will appear when you want to search for the minimals of the expanded puzzle(s).
A problem familiar to the puzzle diggers is, the more expansion we do, the more minimals there will be and the longer finding them will take.
Having an expansion path such that each step makes the minimum difference allows some control on this problem.
.
denis_berthier
2010 Supporter
 
Posts: 4460
Joined: 19 June 2007
Location: Paris

Previous

Return to General