The New Sudoku Players' Forum

[P.O.]

a 31-step expansion path for a 17c puzzle
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 2 5 6)

Hidden Text: Show

Code: Select all

.................1..2..3.45.............52..3.6....7.....6..8....57.....4.1.....2   17c   minimal
.................1..2..3.45.............52..3.6....7.....6..8..6.57.....4.1.....2   18c   min-expand
.................1..2..3.45...3.........52..3.6....7.....6..8..6.57.....4.1.....2   19c   p1
.................1..2..3.45...3.........52..3.6....7.....6..8..6.572....4.1.....2   20c   p2
.................1..2..3.45...3.........52..3.6.1..7.....6..8..6.572....4.1.....2   21c   p3
.................1..2..3.45...3.........52..3.6.1..7.....6..8..68572....4.1.....2   22c   p4
.................1..2..3.45...3.........52..3.6.1..7.....6..8..68572....471.....2   23c   p5
.................1..2..3.45...3.......7.52..3.6.1..7.....6..8..68572....471.....2   24c   p6
....1............1..2..3.45...3.......7.52..3.6.1..7.....6..8..68572....471.....2   25c   p7
....1............1..2..3.45...3.......7.52..3.6.1..7.....6..8..68572....471.3...2   26c   p8
....1............1.12..3.45...3.......7.52..3.6.1..7.....6..8..68572....471.3...2   27c   p9
....1............1.12..3.45...3.......7.52..3.6.1..7.....6..8.768572....471.3...2   28c   p10
....1............1712..3.45...3.......7.52..3.6.1..7.....6..8.768572....471.3...2   29c   p11
....1............1712..3.45...3.......7.52..3.6.1..7.....64.8.768572....471.3...2   30c   p12
....1............1712..3.45...3......97.52..3.6.1..7.....64.8.768572....471.3...2   31c   p13
....1............1712..3.45...3......97.52..3.6.1..7.....64.8.768572..3.471.3...2   32c   p14
...21............1712..3.45...3......97.52..3.6.1..7.....64.8.768572..3.471.3...2   33c   p15
...21............1712..3.45...3......97.52..3.6.1..7....964.8.768572..3.471.3...2   34c   p16
9..21............1712..3.45...3......97.52..3.6.1..7....964.8.768572..3.471.3...2   35c   p17
9..21.3..........1712..3.45...3......97.52..3.6.1..7....964.8.768572..3.471.3...2   36c   p18
95.21.3..........1712..3.45...3......97.52..3.6.1..7....964.8.768572..3.471.3...2   37c   p19
95.21.3..........1712..3.45...3......97452..3.6.1..7....964.8.768572..3.471.3...2   38c   p20
95.21.37.........1712..3.45...3......97452..3.6.1..7....964.8.768572..3.471.3...2   39c   p21
95.21.37.......2.1712..3.45...3......97452..3.6.1..7....964.8.768572..3.471.3...2   40c   p22
95.21.37....5..2.1712..3.45...3......97452..3.6.1..7....964.8.768572..3.471.3...2   41c   p23
95.21437....5..2.1712..3.45...3......97452..3.6.1..7....964.8.768572..3.471.3...2   42c   p24
95.21437....5..2.1712..3.45...3......97452..3.6.1..7....964.81768572..3.471.3...2   43c   p25
95.21437....5..2.1712..3.45...3......97452..3.6.1..7....9645817685721.3.471.3...2   45c   brt
95.21437....5..2.1712..3.45...3......97452..3.6.1..7....964581768572143.471.3...2   46c   p26
95.21437....5..2.1712..3.45...3......97452..3.6.1..7....9645817685721439471.3...2   47c   brt
95.21437....5..2.1712..3.45...3......97452..3.6.1..7.4..9645817685721439471.3...2   48c   p27
95.21437....5..2.1712..3.45...3......97452..3.631..7.4..9645817685721439471.3...2   49c   p28
95.21437....5..2.1712..3.45...3......97452..3.631..724..9645817685721439471.3...2   50c   p29
95.21437....5..2.1712..3.45...3......97452..35631..724..9645817685721439471.3...2   51c   brt
95.21437....5..2.1712..3.45...3......97452..35631.9724..9645817685721439471.3...2   52c   p30
95.21437....5..2.17128.3.45...3......97452..3563189724..9645817685721439471938..2   56c   brt
95.21437....5..2.17128.3.45...3......97452..3563189724.39645817685721439471938..2   57c   p31
95.21437.34.5..2.17128.3.45.243......97452..3563189724239645817685721439471938..2   62c   brt


[denis_berthier]

.
interesting to see the first 24 1-expands are their own BRT-expands.
.

[P.O.]

the algorithm builds several expansion paths simultaneously and for each of them among the 1brt possible for the next step chooses the one(s) with the smallest number of values
for this puzzle i made three attempts, the first with a sample of 1000 paths at each step and i obtained an expansion path of 28 steps (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 1 13), then with a sample of 3000 paths and i obtained this expansion path of 31 steps, and finally with a sample of 5000 paths and i obtained an expansion path of 29 steps (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 1 13)
31 steps may not be the longest expansion path for this puzzle, but it is impossible for me to be exhaustive, and a larger sample size does not guarantee a longer expansion path

[denis_berthier]

.
I've now finished analysing mith's collection of 4,634,101 minimal puzzles in T&E(3) (for 67,539 solutions grids).
The largest number of (1+BRT)-expansion steps within T&E(3) is 10.
The largest distance of minimals to the T&E(3) boundary is 4.
The number of T&E(3)-expands is 72,883.

It's noticeable that the ratio T&E(3)-expands / solution-grids is only 1,079. This means, in most cases, there's only one T&E(3)-expand per solution grid. It may be a bias of the collection or it may be some property of solution grids wrt puzzles in T&E(3) and/or puzzles that have the tridagon pattern.

After analysing only the puzzles for 26,000 solution grids as explained before, in the search for high B ratings, I also have found 398,269 minimal puzzles in T&E(1) with B ≥ 12. The max B rating I found this way is 24.

While doing these analyses, I've developed a full set of:
- scripts for running all the necessary calculations (written in CLIPS, the language of CSP-Rules);
- statistical functions for dealing directly with samples spread in multiple files (in my calculations, in a separate directory for each solution grid) and for gluing the results of multiple samples (the 68 samples I used for the full set of 67,539 solutions grids).
This hierarchical organisation allows to start calculations on a sample and to easily extend them progressively to several samples.

For each solution grid, many files are generated by the scripts, but only those necessary (files that would be empty are not generated). The statistical analyses allow to deal automatically with non-existent files.
.

[denis_berthier]

.
.
Here's some detail about the B12+ puzzles:

Starting point:
28,000 solution grids
1,763,230 "mins" (T&E(3) minimal puzzles for those grids)

leading to:
269,690 "MEU" (BRT-expands of the above, with no duplicates)
13,248,975 "p1" puzzles (1-expands of the "MEU")
13,122,328 "p1U" puzzles (the "p1" with no duplicates) - note that there were not many duplicates at this stage
3,168,142 "p1U-d1" puzzles (the "p1U" that are in T&E(1))
54,062 "p1U-B12" puzzles (the "p1U-d1" with B ≥ 12)
747,190 "p1U-B12-mins" puzzles (minimals of the "p1U-B12") - note that we can be sure that they all have B ≥ 12 (and some of them can have their T&E-depth > 1)
344,208 "p1U-B12-mins-B12" puzzles (the "p1U-B12-mins" that are in T&E(1)) - note that we can be sure that they all have B ≥ 12 and B finite

Note that there are two stages where we get T&E(1) puzzles with B ≥ 12: 54,062 "p1U-B12" and 344,208 "p1U-B12-mins-B12" - and between the two, a long process of minimisation occurs.
Is this process worth the extra work?
- the gain factor is (/ 344208 54062) = 6.37;
- the "p1U-B12-mins-B12" are minimal, while the "p1U-B12" may not be;
- in terms of max B value reached, the difference is not large: 23 for the "p1U-B12" and 24 for the"p1U-B12-mins-B12"; note that if one considers the details for each solution grid, for some grids the max B-value may be smaller after minimisation, because the minimals may not be in T&E(1) (I've already given an example).

- as for the distribution of B values above 12 (in %, from 12 to 24), surprisingly, they are very close:
(45.55 25.97 14.04 8.23 3.41 1.75 0.65 0.31 0.050 0.030 0.0055 0.0037 0.00) for the "p1U-B12"
(45.69 25.40 14.43 8.46 3.50 1.52 0.63 0.27 0.069 0.020 0.0044 0.00058 0.00030) for the "p1U-B12-mins-B12"

Finally, the minimisation process allows to find more extreme minimal puzzles in T&E(1) and slightly higher max values for B, but it doesn't significantly change the distribution of the B≥12 values.
.

[denis_berthier]

.
Here is some challenge.

All the puzzles considered below will be either minimals or expansions "by Singles" of minimals.
If P is a puzzle, I'll note BRT-expand(P) its (unique) expansion by the Basic Resolution Theory BRT ("expansions by Singles")
So, the game is quite easy to describe.

Find some minimal puzzle P0.
n=1: Compute all the minimals of BRT-expand(P0). Among them, find some minimal puzzle P1 such that BRT-expand(P1) is a strict sub-puzzle of BRT-expand(P0).
n=2: Compute all the minimals of BRT-expand(P1). Among them, find some minimal puzzle P2 such that BRT-expand(P2) is a strict sub-puzzle of BRT-expand(P1).
...
The question is, how far can one go?

It's easy to find cases in the T&E(3) collection (and probably in other collections) with n=1.
Can you find longer chains (not necessarily in T&E(3)) of such strict inclusions?

Let me be clear: it's an open question. I don't have the answer. I haven't yet investigated the question beyond the n=1 case.

.

[P.O.]

is this what you are looking for

Code: Select all

.......195..6..............6...8.5...4....3......1....38.....4....2..7...1.9.....   17c minimal
7648532195216948..9381..4..69348.5.114...938.87.31.9.4389...1424562317982179486..   61c brt-expansion

7....32.9.216.......81........48.5..14...9.8..........3.9....4.4......98.....86..   24c minimal
764853219.216.48...381..4..69.48.5.114...9.8.8.....9.4389....424.6....9821.9486..   46c brt-expansion

76...3..9..16.4....381...........5..1....9.8.8.......4.......424.6....982..9.86..   26c minimal
7648.3..9.216.48...381..4..69.48.5..14...9.8.8.....9.4389....424.6....982..9486..   41c brt-expansion

76...3..9..16......3.1..4..6...8.5..1....9.8.........4389.....2.......98....4.6..   24c minimal
7648.3..9..16.48...3.1..4..69.48.5..14...9.8.......9.4389....424.6....98...9486..   37c brt-expansion

7....3..9..16......3.1..4...9.48.5..14...9.8.......9..3.......2........8...9486..   24c minimal
7.48.3..9..16.48...3.1..4...9.48.5..14...9.8.......9.4389....424......98...9486..   34c brt-expansion


[denis_berthier]

.
yes, I wonder how long one can go.
One can also ask the question for each T&E(n) separately.
.

[P.O.]

a slight improvement:

Hidden Text: Show

Code: Select all

.......7193...................62.4......3.....7.......65...7.8.2.....9.....1.8...   17c minimal
824963571936571842715482693198625437462739158573814269651297384287346915349158726   81c brt-expansion

8.49...7.........2.15..26........4.7....39.5..7.81....651...3.......69..3........   24c minimal
82496..7........42.154.26.....6254.7...739.5.57.8142..651297384...3.69..3.....7..   42c brt-expansion

8.49...7.........2.1.4.26........4.....73..5.57.81....651...3.......69..3........   24c minimal
82496..7........42.1.4.26.....6254.7...739.5.57.8142..651297384...3.69..3.....7..   41c brt-expansion

8.49...7........42.1...26.....6..4......3..5.57..14......2.7.84.....69..3........   24c minimal
82496..7........42.1...26.....6254.7...739.5.57.8142.....2.7384...3.69..3.....7..   36c brt-expansion

82.9...7........42.1....6.....62.4......3..5.57..14......2.7.84.....69..3........   24c minimal
82.9...7........42.1...26.....6254.7...739.5.57.8142.....2.7384...3.69..3.....7..   34c brt-expansion

82.9...7........42.1....6.......54.7....39.5.57.8.42.....2.7.84.....69..3........   26c minimal
82.9...7........42.1...26......254.7...739.5.57.8.42.....2.7384...3.69..3.....7..   32c brt-expansion

82.9...7........42.1....6......2.4.7....3..5.57.8.4......2.7.84.....69..3........   24c minimal
82.9...7........42.1...26......2.4.7...73..5.57.8.4......2.7384...3.69..3.....7..   29c brt-expansion

82.9...7........42.1...26......2.4.....73..5.57.8.4........7.84...3.69..3........   25c minimal
82.9...7........42.1...26......2.4.7...73..5.57.8.4........7384...3.69..3.....7..   28c brt-expansion

82.9...7........42.1...26......2.4......3..5.57.8.4........7384.....69..3.....7..   25c minimal
82.9...7........42.1...26......2.4......3..5.57.8.4........7384...3.69..3.....7..   26c brt-expansion


[denis_berthier]

.
wow, good
I didn't think one could have so long descending chains.
.

[denis_berthier]

.
Let's make the challenge harder, by replacing strict-expands by (1+BRT)-expands.

Find some minimal puzzle P0.
n=1: Compute all the minimals of BRT-expand(P0). Among them, find some minimal puzzle P1 such that BRT-expand(P0) is a (1+BRT)-expand of BRT-expand(P1).
n=2: Compute all the minimals of BRT-expand(P1). Among them, find some minimal puzzle P2 such that BRT-expand(P1) is a (1+BRT)-expand of BRT-expand(P2).
...
The question is the same, how far can one go?

Said otherwise:

Code: Select all

P0 minimal      P'0=BRT-expand(P0)
P1 minimal      P'1 = BRT-expand(P1)       P''1 = some 1-expand of P'1      BRT-expand(P''1) = P'0
P2 minimal      P'2 = BRT-expand(P2)       P''2 = some 1-expand of P'2      BRT-expand(P''2) = P'1


.

[P.O.]

if i understood correctly

Hidden Text: Show

Code: Select all

......2.5...8..9......3....9.1....6....72....6....5......1...4.52........3.......   17c minimal
489671235213854976765239418951483762348726159672915384897162543526347891134598627   81c brt-expansion p0

.......35..38..9.676.2.....9.1..3..2.4...61.......5..4..71..54..2...7............   24c minimal
...6712352138549767652394..9.1483..2.48.261..6.2.15..4..716254..2...7........8.2.   48c brt-expansion p1

....712.5..38...76.6....4..9....3..2.4....1..6.2..5.....71.254..2............8...   25c minimal
...671235213854976765..94..9.1483..2.48..61..6.2.15..4..716254..2...7........8.2.   45c brt-expansion p2

......2.5.13....7676....4..9..4....2.48..61....2.15......16254......7........8.2.   27c minimal
...671235213854976765..94..9.1483..2.48..61..6.2.15..4...16254..2...7........8.2.   44c brt-expansion p3

......23..1.85..7..65...4..9..483....48...1..6.2.1.......16254......7..........2.   26c minimal
...671235213854.7.765..94..9.1483..2.48..61..6.2.15..4...16254..2...7........8.2.   42c brt-expansion p4

.....1.352..8.4.7..65...4..9.14.3..2.48..61..............16254......7..........2.   26c minimal
...671235213854.7.765..94..9.1483..2.48..61......15..4...16254......7........8.2.   39c brt-expansion p5

......23521.8.4.7.7.5...4..9..483....48..61..............16254......7..........2.   26c minimal
...671235213854.7.765..94..9.1483....48..61......15..4...16254......7........8.2.   38c brt-expansion p6

...6....52.3.5..7.7.5..94..9..4.3....48..61......1.......16.54......7........8.2.   25c minimal
...6712352.3854.7.7.5..94..9..483....48..61......15..4...16254......7........8.2.   35c brt-expansion p7

...6...3.2.38...7.7.5..9...9.........48..61......15..4...16254......7........8.2.   25c minimal
...67.2352.385..7.7.5..9...9..483....48..61......15..4...16254......7........8.2.   32c brt-expansion p8

...6....52.3....7.7.5..9...9...83....48...1.......5..4...16.54......7........8.2.   23c minimal
...67.2352.3....7.7.5..9...9..483....48..61......15..4...16254......7........8.2.   30c brt-expansion p9

...6....52.3....7.7.5..9...9...83....48..61..........4...16.54......7........8.2.   23c minimal
...67.2352.3....7.7.5..9...9..483....48..61..........4...16254......7........8.2.   28c brt-expansion p10


this reads: 1brt-expansion of p1 with value 5 in cell 29 = p0 / (...)

Code: Select all

p1 + (29 5) = p0 / p2 + (22 2) = p1 / p3 + (57 7) = p2 / p4 + (16 9) = p3 / p5 + (48 2) = p4
p6 + (36 2) = p5 / p7 + (11 1) = p6 / p8 +  (6 1) = p7 / p9 + (13 8) = p8 / p10 + (50 1) = p9


[denis_berthier]

if i understood correctly

Code: Select all

......2.5...8..9......3....9.1....6....72....6....5......1...4.52........3.......   17c minimal
489671235213854976765239418951483762348726159672915384897162543526347891134598627   81c brt-expansion p0

.......35..38..9.676.2.....9.1..3..2.4...61.......5..4..71..54..2...7............   24c minimal
...6712352138549767652394..9.1483..2.48.261..6.2.15..4..716254..2...7........8.2.   48c brt-expansion p1

this reads: 1brt-expansion of p1 with value 5 in cell 29 = p0 / (...)

Code: Select all

p1 + (29 5) = p0

There must be an error here. r2c9 is already equal to 6 in P1.
.

[P.O.]

(29 5) means n5r4c2

[denis_berthier]

(29 5) means n5r4c2

OK, sorry for the misunderstanding.
and congrats for such a long chain.

Have you tried what your algorithm gives when you restrict it to T&E(3) or T&E(2)?
.