The New Sudoku Players' Forum

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

[P.O.]

It's the same puzzle !

the same puzzle that Coloin analyzed, yes.
i remain there in my observation of what you do:
layer p0
after singles:
...4..7..4...892.66..7.2..4.65...8..831...6.79..8.......2..79.8.96.48.72.........; 31c
layer p1
after intersections:
...4..7..4...892.66..7.2..4.65...8..831...6.79.48......42..79.8.96.48.72......4..; 34c
after triplet:
...4..7..4...892.66..7.2..4.65...8..831...6.79..8.......26.79.8.96.48.72.......6.; 33c
layer p2
after basics:
...4..7..4...892.66..7.2..4.65...8..831...6.79.48......426.79.8.96.48.72......46.; 36c

[denis_berthier]

It's the same puzzle !

the same puzzle that Coloin analyzed, yes.
i remain there in my observation of what you do:

I'm not doing any resolution. Just counting the number of layers of puzzles one can have inside T&E(3) when adding clues (additions that don't have to be justified in any way).
.

[P.O.]

the question I ask myself is: what groups the clues in the layers?

[denis_berthier]

.
One more point about the previous example: the distribution of its T&E(3)-expands on the various layers:

Code: Select all

0 terminal puzzles at layer 0
0 terminal puzzles at layer 1
1 terminal puzzles at layer 2
0 terminal puzzles at layer 3

This shows the original puzzle has only one T&E(3)-expand, at layer 2.
This also shows that the distance of this puzzle to the inner side of the T&E(3) border with T&E(<3) is 2.
.

[denis_berthier]

.
Now comes the turn of T&E(2) puzzles in BxB, x ≥ 7
My starting point is Coloin's list of 4 lists (adapted as explained here: http://forum.enjoysudoku.com/the-bxb-classification-of-t-e-2-puzzles-t41922-203.html). A few more puzzles have been found since the 4 lists were published, but my calculations were already running.
There are 6259 minimal puzzles in T&E(2) with BxB ≥ 7, and 776 solution grids.
We know that, apart from 3 old puzzles, they all have a tridagon.
This is a vey special T&E(2) collection and the results below can't be generalised to other collections in T&E(2).

By applying successive (1+BRT)-expansions, I find 11 expansion phases in B7B+.
The details below show the huge numbers of puzzles involved in the intermediate calculations (upto 14+ M)
Notations are similar as for T&E(3), with "d2" meaning T&E-depth 2.

Code: Select all

T&E(2) expansion phase p0:
6259 mins puzzles
6259 ME puzzles
2543 MEU puzzles

T&E(2) expansion phase p1:
126396 p1 puzzles
125694 p1U puzzles
98216 p1U-d2 puzzles
81929 p1EU-d2 puzzles

T&E(2) expansion phase p2:
3947931 p1EU-d2-p2 puzzles
3312771 p1EU-d2-p2U puzzles
551639 p1EU-d2-p2U-d2 puzzles
241610 p1EU-d2--p2EU-d2 puzzles

T&E(2) expansion phase p3:
11338352 p1EU-d2--p2EU-d2-p3 puzzles
10025163 p1EU-d2--p2EU-d2-p3U puzzles
996431 p1EU-d2--p2EU-d2-p3U-d2 puzzles
312472 p1EU-d2--p3EU-d2 puzzles

T&E(2) expansion phase p4:
14369342 p1EU-d2--p3EU-d2-p4 puzzles
13068747 p1EU-d2--p3EU-d2-p4U puzzles
966085 p1EU-d2--p3EU-d2-p4U-d2 puzzles
251206 p1EU-d2--p4EU-d2 puzzles

T&E(2) expansion phase p5:
11336920 p1EU-d2--p4EU-d2-p5 puzzles
10505622 p1EU-d2--p4EU-d2-p5U puzzles
614104 p1EU-d2--p4EU-d2-p5U-d2 puzzles
144220 p1EU-d2--p5EU-d2 puzzles

T&E(2) expansion phase p6:
6382205 p1EU-d2--p5EU-d2-p6 puzzles
6007796 p1EU-d2--p5EU-d2-p6U puzzles
279636 p1EU-d2--p5EU-d2-p6U-d2 puzzles
61763 p1EU-d2--p6EU-d2 puzzles

T&E(2) expansion phase p7:
2675538 p1EU-d2--p6EU-d2-p7 puzzles
2556015 p1EU-d2--p6EU-d2-p7U puzzles
96033 p1EU-d2--p6EU-d2-p7U-d2 puzzles
20489 p1EU-d2--p7EU-d2 puzzles

T&E(2) expansion phase p8:
867014 p1EU-d2--p7EU-d2-p8 puzzles
839692 p1EU-d2--p7EU-d2-p8U puzzles
25249 p1EU-d2--p7EU-d2-p8U-d2 puzzles
5132 p1EU-d2--p8EU-d2 puzzles

T&E(2) expansion phase p9:
211585 p1EU-d2--p8EU-d2-p9 puzzles
207510 p1EU-d2--p8EU-d2-p9U puzzles
4768 p1EU-d2--p8EU-d2-p9U-d2 puzzles
908 p1EU-d2--p9EU-d2 puzzles

T&E(2) expansion phase p10:
36366 p1EU-d2--p9EU-d2-p10 puzzles
35998 p1EU-d2--p9EU-d2-p10U puzzles
505 p1EU-d2--p9EU-d2-p10U-d2 puzzles
98 p1EU-d2--p10EU-d2 puzzles

T&E(2) expansion phase p11:
3791 p1EU-d2--p10EU-d2-p11U puzzles
18 p1EU-d2--p10EU-d2-p11U-d2 puzzles
3 p1EU-d2--p11EU-d2 puzzles

T&E(2) expansion phase p12:
117 p1EU-d2--p11EU-d2-p12
117 p1EU-d2--p11EU-d2-p12U puzzles
0 p1EU-d2--p11EU-d2-p12U-d2 puzzles
0 p1EU-d2--p12EU-d2 puzzles

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

[denis_berthier]

.
The next step should have been puzzles in T&E(2) with BxB < 7 but calculations are still running.
Here are therefore results for T&E(1) puzzles.
The natural collection for this is the controlled-bias one (https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection)
In order to keep computation times reasonable, I kept only the first sub-collection, cbg-000.
In order to consider only T&E(1) minimal puzzles, I eliminated the T&E(0) ones. The result is a collection of 13,886 minimal puzzles, corresponding by construction to 13,886 different solution grids.
The next step was to extract a random sample of 100 solution grids (and corresponding 100 minimals).

By applying successive (1+BRT)-expansions, I find 18 expansion phases in T&E(1):

Code: Select all

T&E(1) expansion phase p0:
100 mins puzzles
100 ME puzzles
100 MEU puzzles

T&E(1) expansion phase p1:
4070 p1 puzzles
4070 p1U puzzles
2306 p1U-d1 puzzles
1698 p1EU-d1 puzzles

T&E(1) expansion phase p2:
71594 p1EU-d1-p2 puzzles
68929 p1EU-d1-p2U puzzles
34288 p1EU-d1-p2U-d1 puzzles
11873 p1EU-d1--p2EU-d1 puzzles

T&E(1) expansion phase p3:
502419 p1EU-d1--p2EU-d1-p3 puzzles
471371 p1EU-d1--p2EU-d1-p3U puzzles
201247 p1EU-d1--p2EU-d1-p3U-d1 puzzles
43041 p1EU-d1--p3EU-d1 puzzles

T&E(1) expansion phase p4:
1815310 p1EU-d1--p3EU-d1-p4 puzzles
1674022 p1EU-d1--p3EU-d1-p4U puzzles
613710 p1EU-d1--p3EU-d1-p4U-d1 puzzles
92620 p1EU-d1--p4EU-d1 puzzles

T&E(1) expansion phase p5:
3887766 p1EU-d1--p4EU-d1-p5 puzzles
3552467 p1EU-d1--p4EU-d1-p5U puzzles
1132718 p1EU-d1--p4EU-d1-p5U-d1 puzzles
131997 p1EU-d1--p5EU-d1 puzzles

T&E(1) expansion phase p6:
5504464 p1EU-d1--p5EU-d1-p6 puzzles
5014584 p1EU-d1--p5EU-d1-p6U puzzles
1413451 p1EU-d1--p5EU-d1-p6U-d1 puzzles
137191 p1EU-d1--p6EU-d1 puzzles

T&E(1) expansion phase p7:
5667763 p1EU-d1--p6EU-d1-p7 puzzles
5170988 p1EU-d1--p6EU-d1-p7U puzzles
1312155 p1EU-d1--p6EU-d1-p7U-d1 puzzles
112947 p1EU-d1--p7EU-d1 puzzles

T&E(1) expansion phase p8:
4606317 p1EU-d1--p7EU-d1-p8 puzzles
4222768 p1EU-d1--p7EU-d1-p8U puzzles
981512 p1EU-d1--p7EU-d1-p8U-d1 puzzles
78346 p1EU-d1--p8EU-d1 puzzles

T&E(1) expansion phase p9:
3142478 p1EU-d1--p8EU-d1-p9 puzzles
2901389 p1EU-d1--p8EU-d1-p9U puzzles
626038 p1EU-d1--p8EU-d1-p9U-d1 puzzles
47363 p1EU-d1--p9EU-d1 puzzles

T&E(1) expansion phase p10:
1861535 p1EU-d1--p9EU-d1-p10 puzzles
1733347 p1EU-d1--p9EU-d1-p10U puzzles
349238 p1EU-d1--p9EU-d1-p10U-d1 puzzles
25262 p1EU-d1--p10EU-d1 puzzles

T&E(1) expansion phase p11:
969223 p1EU-d1--p10EU-d1-p11 puzzles
910790 p1EU-d1--p10EU-d1-p11U puzzles
171945 p1EU-d1--p10EU-d1-p11U-d1 puzzles
11960 p1EU-d1--p11EU-d1 puzzles

T&E(1) expansion phase p12:
445977 p1EU-d1--p11EU-d1-p12 puzzles
423048 p1EU-d1--p11EU-d1-p12U puzzles
75134 p1EU-d1--p11EU-d1-p12U-d1 puzzles
5099 p1EU-d1--p12EU-d1 puzzles

T&E(1) expansion phase p13:
183838 p1EU-d1--p12EU-d1-p13 puzzles
175909 p1EU-d1--p12EU-d1-p13U puzzles
29223 p1EU-d1--p12EU-d1-p13U-d1 puzzles
2010 p1EU-d1--p13EU-d1 puzzles

T&E(1) expansion phase p14:
69748 p1EU-d1--p13EU-d1-p14 puzzles
67169 p1EU-d1--p13EU-d1-p14U puzzles
10223 p1EU-d1--p13EU-d1-p14U-d1 puzzles
754 p1EU-d1--p14EU-d1 puzzles

T&E(1) expansion phase p15:
25069 p1EU-d1--p14EU-d1-p15 puzzles
24264 p1EU-d1--p14EU-d1-p15U puzzles
3261 p1EU-d1--p14EU-d1-p15U-d1 puzzles
256 p1EU-d1--p15EU-d1 puzzles

T&E(1) expansion phase p16:
8101 p1EU-d1--p15EU-d1-p16 puzzles
7887 p1EU-d1--p15EU-d1-p16U puzzles
891 p1EU-d1--p15EU-d1-p16U-d1 puzzles
74 p1EU-d1--p16EU-d1 puzzles

T&E(1) expansion phase p17:
2191 p1EU-d1--p16EU-d1-p17 puzzles
2150 p1EU-d1--p16EU-d1-p17U puzzles
182 p1EU-d1--p16EU-d1-p17U-d1 puzzles
19 p1EU-d1--p17EU-d1 puzzles

T&E(1) expansion phase p18:
520 p1EU-d1--p17EU-d1-p18 puzzles
513 p1EU-d1--p17EU-d1-p18U puzzles
25 p1EU-d1--p17EU-d1-p18U-d1 puzzles
3 p1EU-d1--p18EU-d1 puzzles

T&E(1) expansion phase p19:
78 p1EU-d1--p18EU-d1-p19 puzzles
77 p1EU-d1--p18EU-d1-p19U puzzles
0 p1EU-d1--p18EU-d1-p19U-d1 puzzles
0 p1EU-d1--p19EU-d1 puzzles


Considering the small size of the sample, I have no doubt one could find still more expansion phases for larger collections.

Note: here again, notice the very large numbers of intermediate puzzles (up to 5.6M+ for a sample of size 100).


[Edit]: in order to avoid any ambiguity, I replaced the word "layer" by "expansion phase"
.

[coloin]

Note: here again, notice the very large numbers of intermediate puzzles (up to 5.6M+ for a sample of size 100).

... yes a very large grey area !!!

interestingly
More than 20 years ago ...early pioneers were finding hardest puzzles here
They found a puzzle with 12 "steps" .. which I think looks fairly similar to what you are doing...
I cant find the thread where they published other higher "multi-stepper" puzzles.

Code: Select all

1) ...5..7...2..6..4...6..1..39..2..4...3.....1...7..3..81..7..6...5..4..7...9..8...
2) .....1....1..2..3.4..5..1....6..7..3.8..3..1.2..9..4....9.....2.7..8..6.8..3..5..
3) ..1.....2.3..4....5..6..3....7..8..1.6..1..3.1..9..8....5..9..4.8..5..7.2..1..9..
4) 7.....4...2..7..8...3..8..9...5..3...6..2..9...1..7..6...3..9...3..4..6...9..1..5

#1) is the "12 step" 144: tso #7/31
#2) is Ocean's 11 step 165: Ocean #1/3
#3) is Ocean's 11 step 167: Ocean #3/3
#4) is the 10 step top1465 #77 "the toughest known"

Just for comparision purposes, here are ratings of these four puzzles from other sources...

[denis_berthier]

.
The number of expansion phases and the distance to the boundary are different things. The 1st can be much larger than the 2nd one.
From the post you mention, I'm unable to understand what they are talking about. At first sight, it seems to me they are talking about backdoors. In any case, they are not mentioning remaining in some fixed T&E(n).

To make it simple, after recalling that a puzzle has only one BRT-expansion but lots of 1-expansions and therefore lots of (1+BRT)-expansions:
- the number of T&E(n) expansion phases associated with a puzzle P in T&E(n) is the maximum number of (1+BRT)-expansion steps of some expansion path in T&E(n);
- the distance of P to the boundary is the minimum number of such steps in T&E(n) needed for some expansion path to reach the boundary.

If any of the two is somehow linked to the difficulty of a puzzle, it should be the distance.

Notice that the largest number of expansion phases I found is for puzzles in T&E(1), i.e. very far from the hardest ones.

I'll have a look later at the 4 puzzles you mention.

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

[coloin]

Indeed they are not talking about [clue] steps to a difficult boundary, but [solving] steps as in a removal of a pencil mark and applying new singles.. until it is solved with singles to the end. The puzzles do have a SE boundary [hardest step].
Those puzzles they posted [ all SE ~10] may well not be TE1 , in which case its not relevant I guess.
Could you publish the puzzle/max expand ,with 10 layers [TE3] and 18 layers [TE1] so we can see the respective expansions ?

[denis_berthier]

Indeed they are not talking about [clue] steps to a difficult boundary, but [solving] steps as in a removal of a pencil mark and applying new singles.. until it is solved with singles to the end. The puzzles do have a SE boundary [hardest step].

Yes, quite different.

Those puzzles they posted [ all SE ~10] may well not be TE1 , in which case it's not relevant I guess.

The 1st 2 are in T&E(1), the next 2 in T&E(2).
They are relevant: all my definitions work within any fixed T&E(d).
I have long calculations running. I'll see those 4 puzzles tomorrow.

Could you publish the puzzle/max expand ,with 10 layers [TE3] and 18 layers [TE1] so we can see the respective expansions ?

I'll do it, but as I said, I need time to write the scripts that can extract them from large puzzle collections.
.

[denis_berthier]

.
As announced earlier, here's an example of the successive (1+BRT) expansions within T&E(3) of a minimal puzzle in T&E(3), with 10 expansion phases above layer 0.
Format:
puzzle nb-clues +operation-from-puzzle-below (alternating 1-expand and BRT-expand)

Code: Select all

1.3..67.9.57......96.3.751.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37. 38c +BRT
1.3..67.9.57......96.3.751.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37. 38c +p10
1.3...7.9.57......96.3.751.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37. 37c +BRT
1.3...7.9.57......96.3.751.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37. 37c +p9
1.3...7.9.57......9..3.751.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37. 36c +BRT
1.3...7.9.57......9..3..51.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37. 35c +p8
1.3...7.9.5.......9..3..51.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37. 34c +BRT
1.3...7.9.5.......9..3..51.....931.75.6712...7.1..8...3.9.7.6..67..3..9..15.6.37. 34c +p7
1.3...7.9.5.......9..3..51.....931.75.6712...7.1..8...3.9.7.6..6...3..9..15.6.37. 33c +BRT
1.3...7.9.5.......9..3..51.....931.75.6712...7.1..8...3.9.7.6..6...3..9..15.6.37. 33c +p6
1.3...7.9.5.......9..3..51.....931.75.6712...7.1..8...3.9.7.6......3..9..15.6.37. 32c +BRT
1.3...7.9.5.......9..3..51.....931.75.6712...7.1..8...3.9.7.6......3..9..15.6.37. 32c +p5
1.3...7.9.5.......9..3..51.....931.75.6712.....1..8...3.9.7.6......3..9..15.6.37. 31c +BRT
1.3...7.9.5.......9..3..51.....931.75.6712.....1..8...3.9.7.6......3..9..15.6.37. 31c +p4
1.3...7.9.5.......9..3..51.....931.75.6.12.....1..8...3.9.7.6......3..9..15.6.37. 30c +BRT
1.3...7.9.5.......9..3..51.....931.75.6.12.....1..8...3.9.7.6......3..9..15.6.37. 30c +p3
1.3...7.9.5.......9..3..51.....931.75.6..2.....1..8...3.9.7.6......3..9..15.6.37. 29c +BRT
1.3...7.9.5.......9..3..51.....931.75.6..2.....1..8...3.9.7.6......3..9..15.6.37. 29c +p2
1.3...7.9.5.......9..3..51.....93..75.6..2.....1..8...3.9.7.6......3..9..15.6.37. 28c +BRT
1.3...7.9.5.......9..3..51.....93..75.6..2.....1..8...3.9.7.6......3..9..15.6.37. 28c +p1
1.....7.9.5.......9..3..51.....93..75.6..2.....1..8...3.9.7.6......3..9..15.6.37. 27c +BRT -> min-expand
1.....7.9.5.......9..3..51.....9...75.6..2.....1..8...3...7.6......3..9..15.6.3.. 24c in mins

As expected when there's a large number of expansion phases, most of the BRT-expands are null operations.

.