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