The New Sudoku Players' Forum

[P.O.]

in this case basics is very relevant, it gathers all the values ​​that keep the puzzle in te1, that's 36 values, ​​11 more than what you find

[denis_berthier]

.
You are not providing any (1+BRT)-expansion path that would have more than my 18 steps.
Anyway, where did I say that I was giving the longest possible expansion path in T&E(1) ?
Currently, expansion paths in T&E(1) are restricted to 20 (1+BRT) steps. No "basics" are used in the calculations.

Note that the hard part in my calculations is not to find the expansions of some given minimal. It's to find the minimals that allow such expansions.
If you want to prove anything, try to start from different minimals (with different expansions).
.

[P.O.]

for a puzzle at a t&e(n) depth, the maximum number of values ​​that can be added to this puzzle while maintaining its t&e(n) depth seems to me to be the basis from which to build the organization of its layers, any other approach seems artificial to me

[denis_berthier]

for a puzzle at a t&e(n) depth, the maximum number of values ​​that can be added to this puzzle while maintaining its t&e(n) depth seems to me to be the basis from which to build the organization of its layers, any other approach seems artificial to me

Your opinions are worth the amount of data they rely on: 0. You're welcome to open another thread to explain your results when you have any.

BTW, the puzzle with 65 clues (123456789456789...7981325..234561897815974632967328.5.34.695.7858.247...67.813..5) is reachable in only 6 (1+BRT)-expansion steps.
.

[denis_berthier]

.

I noticed that (p1+BRT) followed by (p2+BRT) is equivalent to (p1+p2+BRT). With your progressive (1+BRT) expansions, you don't get all the puzzles in T&E(d). Why don't you first do all the pk expansions and only then a unique BRT-expansion?

First, you are right about the equivalence. This is largely used in my scripts (together with p1+p2 = p2+p1) in order to eliminate redundancies at every stage.

You are also right about your assertion: I don't get all the puzzles in T&E(d) - but I claim I get all those of interest.


Now, about the question.

1) This thread relies on the (trivial) observation that two puzzles that have the same BRT-expansion are equivalent for all practical solving purposes. In particular, they have the same T&E-depth, B, BxB, BxBB classifications - which is what matters most in my approach.
As a result, only puzzles that are their own BRT-expands are relevant to a solver. Also 1-expands of such puzzles are relevant, because they allow to fully describe expansion paths. Puzzles in between those two categories may not be reached by my scripts.

2) For a solver, a puzzle being minimal is totally irrelevant. All the puzzles of interest to a solver are reached by my scripts.

3) As of a few years ago, any large scale collection of puzzles had been about minimals. More recently mith introduced the expansion of minimals in T&E(3) by Singles (= BRT-expands) and their max-expands (= T&E(3)-expands). My approach in this thread generalises and systematises these ideas.

4) There's one point that may make puzzles with the same BRT-expand different: they may not have the same sets of minimals. This is of interest only to the puzzle creators. The basic point here is, if you look for the minimals of some puzzle P, you can be sure they'll be at least as hard as P - for any reasonable rating/classification system (which excludes the SER or any system taking uniqueness into account). I've used this extensively to find hundreds of thousands of extremely high B rating (B ≥ 12) puzzles from (T&E(3)+1)-expansions of T&E(3) puzzles.

5) You can also be sure that the minimals of the BRT-expands of P will also be at least as hard as P - thus possibly getting many more minimals than for P.

6) Finding minimals of puzzles is computationally hard. If P2 is an expansion of P1, it's harder for P2 than for P1. How much harder depends on how much the two puzzles differ.

7) As of now, for T&E(3) puzzles, what has been computed is minimals of their BRT-expands. A much wider search might be based on their T&E(3)-expands. However, that would probably lead to untractable computations.
What the progressive (1+BRT)-expansions allow is a better controlled possibility of extending the search for minimals.
In this regard, the most interesting possibilties may not be obtained by using the puzzles appearing in the fastest expansion path out of T&E(3), but on the contrary those on some slowest path. Much remains to be done.
.

[P.O.]

BTW, the puzzle with 65 clues (123456789456789...7981325..234561897815974632967328.5.34.695.7858.247...67.813..5) is reachable in only 6 (1+BRT)-expansion steps.

i don't know what you mean by 'reachable' but 6 is neither the smallest number of layers nor the largest.
here's a consistent way to decide which values keep a puzzle in te1 and which put it in te0:
initialize the puzzle with Singles, which corresponds to min-expand, then collect all size 1 backdoors in Singles: all these values put the puzzle in te0, all others keep it in te1.

[denis_berthier]

BTW, the puzzle with 65 clues (123456789456789...7981325..234561897815974632967328.5.34.695.7858.247...67.813..5) is reachable in only 6 (1+BRT)-expansion steps.

i don't know what you mean by 'reachable'

It's perfectly clear in the context: there's a (1+BRT)-expansion path of length 6 from the minimal puzzle under discussion (i.e. ..3...789.56......7..1..5...345..8..8.....6.2.......5.....9..7.58..47...6....3...) to the one above:

Code: Select all

123456789456789...7981325..234561897815974632967328.5.34.695.7858.247...67.813..5 65c +BRT -> --p6EU
12345.789456789...7981325..2345..897815974632967328.5.34..9..7.58..47...67...3... 55c +p6
1234..789456789...7981325..2345..897815974632967328.5.34..9..7.58..47...67...3... 54c +BRT -> --p5EU
1234..789456789...7981325..2345..8978.59.463296.328.5.3...9..7.58..47...6....3... 49c +p5
..3...789.56789...79813.5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 34c +BRT -> --p4EU
..3...789.56789...7.813.5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 33c +p4
..3...789.5678....7.813.5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 32c +BRT -> --p3EU
..3...789.5678....7.813.5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 32c +p3
..3...789.567.....7.813.5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 31c +BRT -> --p2EU
..3...789.567.....7.813.5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 31c +p2
..3...789.567.....7.81..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 30c +BRT -> --p1EU
..3...789.567.....7.81..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 30c +p1
..3...789.56......7.81..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 29c +BRT -> --p0EU = min-expand
..3...789.56......7..1..5...345..8..8.....6.2.......5.....9..7.58..47...6....3... 25c +p0 = minimal

And, no, there's no shorter (1+BRT)-expansion path between those two.


As for the rest, I don't know what you're talking about, besides a tautology about backdoors.
.

[P.O.]

after min-expand there are 4 backdoors which leaves 81-(29+4)=48 values which keep the puzzle in te1
so the goal of the game is to find a subset of these values which collectively leaves the puzzle in te1 and to distribute these values in a maximum number of layers using the operator 1+BRT
the largest number of values in the largest number of layers being considered the best result
your procedure distributes 25 of these values into 18 layers
what i did, min-expand + basics, got 36 of these values and i'm looking for an optimal distribution of these values into layers
smallest number of layers: 1

Code: Select all

..3...789.56......7.81..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 29c min-expand
..3..6789.56......7.81..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 30c 1+brt => 65c


for the largest number of layers i only have partial results: 10

Code: Select all

..3...789.56......7.81..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3...   29c min-expand
..3...789.56......7981..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3...   30c brt 0
..3...789456......7981..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3...   31c brt 0
..34..789456......7981..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3...   32c brt 0
..34..789456..9...7981..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3...   33c brt 0
..34..789456..9...79813.5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3...   34c brt 0
..34..789456..9...79813.5...345..8..8.5...6.2.6.....5.34..9..7.58..47...6....3...   35c brt 0
..34..789456..9...79813.5...345..8..8.5..46.2.6.....5.34..9..7.58..47...6....3...   36c brt 0
..34..789456..9...79813.5...345..8.78.5..46.2.6.....5.34..9..7.58..47...6....3...   37c brt 0
..34..789456..9...7981325...345..8.78.5..46.2.6.....5.34..9..7.58..47...6....3...   38c brt 0
1234..789456..9...7981325...345..8.78.5..46.2.6.....5.34..9..7.58..47...6....3...   40c brt 1 


here are the results of applying 1+BRT to each of the 48 values
the first number indicates the number of values placed
1+BRT is broken down into:
1: the first pair (cell value)
BRT: the other pairs (cell value)

Hidden Text: Show

Code: Select all

1: ((13 7))
1: ((16 1))
1: ((17 2))
1: ((20 9))
1: ((23 3))
1: ((26 6))
1: ((28 2))
1: ((35 9))
1: ((36 7))
1: ((40 9))
1: ((42 4))
1: ((44 3))
1: ((51 8))
1: ((52 4))
1: ((56 4))
1: ((66 9))
1: ((70 3))
2: ((10 4) (20 9))
2: ((15 9) (20 9))
2: ((18 3) (23 3))
2: ((24 2) (20 9))
2: ((32 6) (36 7))
2: ((46 9) (20 9))
2: ((49 3) (44 3))
2: ((50 2) (28 2))
2: ((79 9) (66 9))
2: ((80 4) (56 4))
3: ((4 4) (10 4) (20 9))
3: ((14 8) (13 7) (23 3))
3: ((27 4) (26 6) (23 3))
3: ((54 1) (35 9) (36 7))
3: ((71 1) (35 9) (26 6))
4: ((1 1) (10 4) (20 9) (2 2))
4: ((2 2) (1 1) (10 4) (20 9))
4: ((48 7) (36 7) (74 7) (56 4))
4: ((74 7) (56 4) (48 7) (36 7))
6: ((41 7) (48 7) (36 7) (74 7) (13 7) (56 4))
9: ((38 1) (1 1) (10 4) (48 7) (74 7) (20 9) (2 2) (56 4) (36 7))
36: ((5 5) (81 5) (60 5) (63 8) (77 1) (58 6) (76 8) (67 2) (4 4) (10 4) (6 6) (20 9) (24 2) (23 3)
     (41 7) (14 8) (15 9) (33 1) (35 9) (36 7) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2) (13 7)
     (28 2) (32 6) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))
36: ((6 6) (60 5) (5 5) (32 6) (36 7) (77 1) (81 5) (63 8) (76 8) (58 6) (67 2) (4 4) (10 4) (20 9)
     (24 2) (23 3) (41 7) (14 8) (15 9) (33 1) (35 9) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2)
     (13 7) (28 2) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))
36: ((33 1) (35 9) (36 7) (28 2) (32 6) (77 1) (81 5) (60 5) (5 5) (63 8) (76 8) (58 6) (67 2)
     (4 4) (1 1) (2 2) (6 6) (46 9) (10 4) (20 9) (24 2) (23 3) (41 7) (49 3) (14 8) (15 9) (38 1)
     (40 9) (42 4) (44 3) (48 7) (50 2) (51 8) (56 4) (74 7) (13 7))
36: ((58 6) (67 2) (76 8) (4 4) (10 4) (63 8) (20 9) (81 5) (60 5) (77 1) (5 5) (6 6) (24 2) (23 3)
     (41 7) (14 8) (15 9) (33 1) (35 9) (36 7) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2) (13 7)
     (28 2) (32 6) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))
36: ((60 5) (77 1) (81 5) (5 5) (63 8) (76 8) (58 6) (67 2) (4 4) (10 4) (6 6) (20 9) (24 2) (23 3)
     (41 7) (14 8) (15 9) (33 1) (35 9) (36 7) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2) (13 7)
     (28 2) (32 6) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))
36: ((63 8) (81 5) (60 5) (58 6) (67 2) (76 8) (77 1) (4 4) (10 4) (5 5) (6 6) (20 9) (24 2) (23 3)
     (41 7) (14 8) (15 9) (33 1) (35 9) (36 7) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2) (13 7)
     (28 2) (32 6) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))
36: ((67 2) (76 8) (58 6) (4 4) (10 4) (63 8) (20 9) (81 5) (60 5) (77 1) (5 5) (6 6) (24 2) (23 3)
     (41 7) (14 8) (15 9) (33 1) (35 9) (36 7) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2) (13 7)
     (28 2) (32 6) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))
36: ((76 8) (63 8) (81 5) (60 5) (58 6) (67 2) (77 1) (4 4) (10 4) (5 5) (6 6) (20 9) (24 2) (23 3)
     (41 7) (14 8) (15 9) (33 1) (35 9) (36 7) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2) (13 7)
     (28 2) (32 6) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))
36: ((77 1) (81 5) (60 5) (5 5) (63 8) (76 8) (58 6) (67 2) (4 4) (10 4) (6 6) (20 9) (24 2) (23 3)
     (41 7) (14 8) (15 9) (33 1) (35 9) (36 7) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2) (13 7)
     (28 2) (32 6) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))
36: ((81 5) (60 5) (5 5) (63 8) (77 1) (58 6) (76 8) (67 2) (4 4) (10 4) (6 6) (20 9) (24 2) (23 3)
     (41 7) (14 8) (15 9) (33 1) (35 9) (36 7) (38 1) (42 4) (44 3) (50 2) (51 8) (2 2) (13 7)
     (28 2) (32 6) (40 9) (46 9) (48 7) (49 3) (56 4) (74 7) (1 1))


[denis_berthier]

after min-expand there are 4 backdoors which leaves 81-(29+4)=48 values which keep the puzzle in te1

OK for T&E(1) but using backdoors wouldn't work for deeper T&E-depths.

so the goal of the game is to find a subset of these values which collectively leaves the puzzle in te1 and to distribute these values in a maximum number of layers using the operator 1+BRT

OK, though It's not "layers" but "expansion steps".

smallest number of layers: 1

Code: Select all

..3...789.56......7.81..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 29c min-expand
..3..6789.56......7.81..5...345..8..8.5...6.2.6.....5.3...9..7.58..47...6....3... 30c 1+brt => 65c

Good! I had some too strict condition on my code for terminal puzzles. Fortunately it can easily be fixed.

for the largest number of layers i only have partial results: 10

combinatorial explosion?
.

[P.O.]

OK for T&E(1) but using backdoors wouldn't work for deeper T&E-depths.

with the puzzles in te2 and te3, the procedures T&E(1,Singles) and T&E(2,Singles) clearly define the sets of values that keep the puzzles in te2 or te3
for the puzzles in te1 using backdoors allows the same clear definition of the values to be considered

combinatorial explosion?

absolutely, the simplest thing would be to test all the permutations of the values, but that quickly becomes impossible
so i proceed in stages, by taking subsets of the values, trying to minimize the size of the BRT-expansion but that's still a lot to test and my programming environment is slow

[denis_berthier]

OK for T&E(1) but using backdoors wouldn't work for deeper T&E-depths.

with the puzzles in te2 and te3, the procedures T&E(1,Singles) and T&E(2,Singles) clearly define the sets of values that keep the puzzles in te2 or te3
for the puzzles in te1 using backdoors allows the same clear definition of the values to be considered

That's obviously what I'm doing - sort of. It's just that I don't need to call it something-backdoor.
There's one more point. This puzzle has backdoor size 1 - but it's not true of all the puzzles. For my calculations, it doesn't change anything.
.

[P.O.]

That's obviously what I'm doing - sort of. It's just that I don't need to call it something-backdoor.
There's one more point. This puzzle has backdoor size 1 - but it's not true of all the puzzles. For my calculations, it doesn't change anything.

ok, it's just for me, that way i know all the values i work with

[denis_berthier]

.
In order to see what I mean about backdoor-size >1, try any puzzle in cbg-000 that has backdoor size > 1.
.

[P.O.]

In order to see what I mean about backdoor-size >1, try any puzzle in cbg-000 that has backdoor size > 1.

it is true that selecting a subset of values that keeps the puzzle in te1 takes care of backdoors whatever their size
but knowing the size of the BRT-expansion of each value allows me to pre-select values for combinations.
for example, for this puzzle, all values with a BRT-expansion of 36 can be eliminated from searches and used only last.

this puzzle has backdoors of size 4
here two of them:

Code: Select all

n3r1c3 n5r1c5 n2r4c1 n7r4c2
n5r5c6 n6r5c9 n5r6c1 n4r6c2


and its BRT-expansion

Hidden Text: Show

Code: Select all

1: ((3 3))
1: ((6 6))
1: ((15 9))
1: ((46 5))
2: ((10 4) (27 4))
2: ((27 4) (10 4))
3: ((9 9) (3 3) (6 6))
4: ((16 6) (52 3) (37 3) (45 6))
4: ((37 3) (45 6) (16 6) (52 3))
4: ((45 6) (37 3) (16 6) (52 3))
4: ((52 3) (37 3) (16 6) (45 6))
8: ((30 8) (57 2) (63 8) (73 9) (79 2) (34 5) (64 8) (70 9))
8: ((34 5) (70 9) (79 2) (63 8) (64 8) (73 9) (57 2) (30 8))
8: ((57 2) (63 8) (73 9) (79 2) (34 5) (64 8) (70 9) (30 8))
8: ((63 8) (57 2) (73 9) (79 2) (34 5) (64 8) (70 9) (30 8))
8: ((64 8) (57 2) (63 8) (73 9) (79 2) (34 5) (70 9) (30 8))
8: ((70 9) (79 2) (34 5) (63 8) (64 8) (73 9) (57 2) (30 8))
8: ((73 9) (79 2) (34 5) (63 8) (64 8) (70 9) (57 2) (30 8))
8: ((79 2) (34 5) (63 8) (70 9) (73 9) (57 2) (64 8) (30 8))
9: ((19 6) (27 4) (10 4) (45 6) (48 6) (37 3) (16 6) (6 6) (52 3))
9: ((28 2) (34 5) (70 9) (73 9) (79 2) (63 8) (64 8) (57 2) (30 8))
9: ((48 6) (16 6) (45 6) (52 3) (37 3) (19 6) (6 6) (27 4) (10 4))
9: ((54 2) (63 8) (34 5) (57 2) (70 9) (73 9) (79 2) (64 8) (30 8))
9: ((72 5) (70 9) (79 2) (34 5) (63 8) (64 8) (73 9) (57 2) (30 8))
10: ((18 3) (52 3) (37 3) (3 3) (27 4) (10 4) (16 6) (45 6) (9 9) (6 6))
11: ((5 5) (8 8) (17 2) (26 5) (41 7) (14 8) (40 2) (42 5) (22 7) (24 2) (12 7))
11: ((8 8) (17 2) (26 5) (5 5) (41 7) (14 8) (40 2) (42 5) (22 7) (24 2) (12 7))
11: ((12 7) (14 8) (17 2) (26 5) (5 5) (8 8) (41 7) (40 2) (42 5) (22 7) (24 2))
11: ((14 8) (17 2) (26 5) (5 5) (8 8) (41 7) (40 2) (42 5) (22 7) (24 2) (12 7))
11: ((17 2) (26 5) (8 8) (5 5) (41 7) (14 8) (40 2) (42 5) (22 7) (24 2) (12 7))
11: ((22 7) (40 2) (14 8) (17 2) (26 5) (5 5) (8 8) (41 7) (42 5) (24 2) (12 7))
11: ((24 2) (26 5) (8 8) (17 2) (22 7) (40 2) (5 5) (14 8) (41 7) (42 5) (12 7))
11: ((26 5) (8 8) (17 2) (5 5) (41 7) (14 8) (40 2) (42 5) (22 7) (24 2) (12 7))
11: ((29 7) (47 4) (77 4) (33 4) (50 1) (36 1) (78 1) (71 1) (81 7) (69 7) (53 7))
11: ((33 4) (29 7) (47 4) (50 1) (36 1) (77 4) (78 1) (71 1) (81 7) (69 7) (53 7))
11: ((36 1) (71 1) (50 1) (33 4) (77 4) (53 7) (29 7) (47 4) (69 7) (78 1) (81 7))
11: ((40 2) (22 7) (14 8) (17 2) (26 5) (5 5) (8 8) (41 7) (42 5) (24 2) (12 7))
11: ((41 7) (14 8) (17 2) (26 5) (40 2) (42 5) (5 5) (8 8) (22 7) (24 2) (12 7))
11: ((42 5) (41 7) (14 8) (17 2) (26 5) (40 2) (5 5) (8 8) (22 7) (24 2) (12 7))
11: ((47 4) (29 7) (77 4) (33 4) (50 1) (36 1) (78 1) (71 1) (81 7) (69 7) (53 7))
11: ((50 1) (71 1) (36 1) (33 4) (77 4) (53 7) (29 7) (47 4) (69 7) (78 1) (81 7))
11: ((53 7) (47 4) (29 7) (71 1) (77 4) (33 4) (69 7) (78 1) (50 1) (36 1) (81 7))
11: ((69 7) (81 7) (53 7) (47 4) (29 7) (71 1) (77 4) (33 4) (78 1) (50 1) (36 1))
11: ((71 1) (69 7) (81 7) (53 7) (47 4) (29 7) (77 4) (33 4) (78 1) (50 1) (36 1))
11: ((77 4) (50 1) (33 4) (29 7) (47 4) (71 1) (36 1) (53 7) (69 7) (78 1) (81 7))
11: ((78 1) (69 7) (77 4) (50 1) (36 1) (33 4) (81 7) (53 7) (29 7) (47 4) (71 1))
11: ((81 7) (69 7) (53 7) (47 4) (29 7) (71 1) (77 4) (33 4) (78 1) (50 1) (36 1))
12: ((21 9) (12 7) (14 8) (17 2) (26 5) (5 5) (8 8) (41 7) (40 2) (42 5) (22 7) (24 2))


what do you mean?

[denis_berthier]

.
In your example, you keep 8 potential clues until the end.
This makes it impossible to guarantee that the longest expansion path can be found.

Note: when I agreed that (p1+BRT) + (p2+BRT) = (p2+BRT) + (p1+BRT) = p1+p2+BRT, I meant in terms of resulting puzzles - but it's not true in terms of lengths of expansion paths.
.