The New Sudoku Players' Forum

[denis_berthier]

Compared the first 26c to Loki (using gsf's Hamming distance algorithm to morph Loki to the closest form):

Code: Select all

........1.....2.34....4.56.....2478...41......728.9....81......42...7..97.9..1...;1;1;1;1;1;n356;b4p357+b5p168+b7p168+b8p348;
........9.....2.35....4.....1..24...8.47..9...728.91....1......24..71..87.9..8...;1;1;1;1;1;n356;b4p357+b5p168+b7p168+b8p348;

Different guardians (8r9c5 vs. 9r8c4), but promising for there being a direct line between the two.
(The first 26c has the smallest distance, 18, to Loki.)

The Hamming distance is one thing, it gives some idea of the number of steps necessary in vicinity search.
However, if you have to apply some isomorphism to get from one puzzle to the next, considering there are (except for extremely rare automorphic grids):
- 3,359,232 "geometric" permutations of a grid
- 362,880 permutations of digits
- i.e. 1,218,998,108,160 possible isomorphisms,
what are the chances that the precisely required isomorphism was applied during vicinity search?

Unless the generation process involved mapping the original puzzles systematically into some standard form (e.g. solution minlex) and the output was submitted to some isomorphism for fun. But then what should count is the Hamming distance between the solution minlex forms. This is not invariant under isomorphisms, but who cares about that in generation?
.

[mith]

The neighborhood searches used take the input puzzle and modify it in every possible way for that search. The isomorphism are irrelevant to this*. If we have a puzzle A as a seed and the neighborhood search results in the set of puzzles B, and were to take a morph (say A’) and apply the same search resulting in B’, B and B’ will be equivalent up to the isomorphism.

*except for cases where there is a nontrivial isomorphism in the solution grid, in which case the same puzzle could be generated twice (similar to the issue pointed out in the max-expand list) but the command I used in gsf suppresses duplicates.

It doesn’t particularly matter what canonical form is used for comparison, and doing a neighborhood search will often result in some puzzles which look very different after converted to the canonical form. For the solution minlex example, consider the case that a new puzzle has a different solution and that solution is not itself in minlex form. Then the puzzle will be morphed to match the (potentially very different) solution minlex.

So for the purpose of hamming distance, what we care about is the distance between a puzzle and some morph of a second puzzle; during the actual path between the two puzzles, we may in fact be taking a morph at every step of the path, but the composition of these morphs will itself be a morph (and the same morph as the hamming distance morph, absent automorphic solution grids).

[mith]

If there's a direct line from Loki to the February 14 batch, it doesn't appear to be through depth 3 puzzles. The closest seed puzzle posted before or on February 27 has a distance of 3 (the other T&E(3) puzzle identified by Denis from that batch), but the closest seed puzzle to these two has a distance of 14 (15 to Loki):

Code: Select all

distance 14
........1.......23.....45.6...45.....478.96..95..678...69.4....4..97...878...5...
...4.........5..23........6..654.....478.96..95..678...69.7....4.598...7.8.......

This puzzle is from hendrick (February 23), which further complicates things of course, since I don't know when these were generated in relation to my own posts (fortunately for mine I was posting new puzzles almost every day) nor what order they were generated in relative to one another.

The large distance from the two puzzles identified by Denis back to the earliest T&E(3) puzzles is not necessarily indicative that there are a lot of steps; while the neighborhood searches can only result in puzzles a distance of at most 4 apart (in the case of -2+2), the singles-expand-and-minimize script could have resulted in much bigger jumps in hamming distance. But it's going to be hard to say much more without running a more thorough backward search (including T&E(2) puzzles with non-degenerate trivalue oddagons), and even then whatever path I find (if any) is going to be "plausible" at best. Which is fine, it was never really realistic to expect to find exactly the path taken between two puzzles distantly related in the database.

[denis_berthier]

.
Hi mith,
We don't really need to know the real path to Loki. What was interesting in the analysis is to understand it was possible to reach puzzles such as Loki by vicinity search.
You have shown:
- it is possible to get to it by starting from lower SER puzzles with a non-degenerate tridagon
- there are many old lower SER puzzles in ph2010 with a non-degenerate tridagon

What remains to understand is how the non-degenerate tridagon with "low" SER could appear in ph2010 or other high SER collections.

I have shown that the degenerate-cyclic tridagon is almost everywhere. Even in the controlled-bias collection, in which there in no non-degenerate tridagon, there are 16,453 puzzles (0.278 % ) with the degenerate-cyclic variant (see http://forum.enjoysudoku.com/the-tridagon-rule-t39859-122.html).
I wonder if you could run your scripts on them (or maybe on a smaller subset of them with high SER or high B rating) and see what happens. This will obviously not be the real way the first tridagon could've appeared (AFAIK, this collection has never been used as a seed), but it would show that it "necessarily" appears after enough search.
.

[mith]

Yes, I agree we don't need to know the specific path. Still, I would like to find a concrete example of a possible path from:

1. The earliest T&E(3) seed puzzles to Loki
2. The earliest NDTO seed puzzles to the earliest T&E(3) puzzles (the non-seed 27c as well as the seed puzzles)
[i]It's worth noting here that while the dobrichev puzzles from 2012 were used as seeds by my scripts, I have no idea *when* they were used; they are 31-32c, and it was pretty late in my process that I started to use such high clue count puzzles as seeds. So it will be interesting to see if the path(s) I find go through other NDTO puzzles which might have been used as seeds earlier.[i]
3. The earliest degenerate-cyclic tridagon puzzles to the earliest NDTO puzzles

For the last, the ordering is going to be very rough. The first thing to do is to identify whether there are any DCT puzzles with ID <= 27706 (puzzles after this are mostly "timestamped" by batch in their names). After this point, we have large batches of puzzles typically corresponding to a specific month, so I can potentially hop from batch to batch in order (that said, I don't know what set of puzzles dobrichev was using as seeds, for example).

[mith]

Slowed down at the moment (have a likely fracture in my dominant hand). The TO script did finish running on the ph2010 puzzles, so I'll get those results up soonish.

[denis_berthier]

* expanded form - these are puzzles which may or may not be minimal, but which do not have any singles available; all minimals of such puzzles will have the same T&E depth WRT singles.
** min-expand - these are expanded forms which cannot have clues removed while remaining expanded forms; such puzzles again may or may not be minimal.
*** max-expand - these are expanded forms which cannot have clues added while remaining depth 3

We had discussed this before and I hadn't read this post in detail.

I think it would be useful to recall in the first post that the min-expands as you define them here are the same thing as the expansions of minimals by Singles.

[Edit, June 13th]:
Or do you mean that your min-expands:
- have no intrinsic definition,
- are only relative to the current state of your database of "expanded forms",
- will be equivalent to my intrinsic definition (expanded form of minimals by Singles), only when you will have finished the computation of all the minimals of all the "expanded forms" (i.e. of all the max-expands)?

I'm asking because I found a potential problem with your min-expands collection: their stats are significantly different from those I get by:
- generating minimals from a sample of 1000 of your max-expands,
- generating all their min-expands,
- filtering them for non-redundancy.
The sample is large enough to make the discrepancies highly unlikely.

[hendrik_monard]

If there's a direct line from Loki to the February 14 batch, it doesn't appear to be through depth 3 puzzles. The closest seed puzzle posted before or on February 27 has a distance of 3 (the other T&E(3) puzzle identified by Denis from that batch), but the closest seed puzzle to these two has a distance of 14 (15 to Loki):

Code: Select all

distance 14
........1.......23.....45.6...45.....478.96..95..678...69.4....4..97...878...5...
...4.........5..23........6..654.....478.96..95..678...69.7....4.598...7.8.......

This puzzle is from hendrick (February 23), which further complicates things of course, since I don't know when these were generated in relation to my own posts (fortunately for mine I was posting new puzzles almost every day) nor what order they were generated in relative to one another.

The large distance from the two puzzles identified by Denis back to the earliest T&E(3) puzzles is not necessarily indicative that there are a lot of steps; while the neighborhood searches can only result in puzzles a distance of at most 4 apart (in the case of -2+2), the singles-expand-and-minimize script could have resulted in much bigger jumps in hamming distance. But it's going to be hard to say much more without running a more thorough backward search (including T&E(2) puzzles with non-degenerate trivalue oddagons), and even then whatever path I find (if any) is going to be "plausible" at best. Which is fine, it was never really realistic to expect to find exactly the path taken between two puzzles distantly related in the database.

Hi mith,
Discovered your post only today.
It appears that the puzzle M503 in my batch of 23 february 2022 was a fifth generation descendant from a puzzle in your list of 11.7s of 23 January.

taken from your post above with reference labels added:
........1.......23.....45.6...45.....478.96..95..678...69.4....4..97...878...5... M503
...4.........5..23........6..654.....478.96..95..678...69.7....4.598...7.8....... P326

9876.....5.....96..4.......3...5.21....2..6.3...1.3.95...31..2.....6935......21.. M503
98.76.5..7.5.498...465......984.6.7...795........8.....6.........4....32.......5. P326

........1......234....25..6..7.8.....52.96...98...7..5.69.785..7..6.2...8..95.6.. ED=11.7/1.2/1.2 #15 in mith__list_23jan 11.7s
9876.....5.....86.4.........6.38..25.5..1263.......1.8...26..8....1..2.3....53.1. maxlex of previous line


'genealogy' from mith's puzzle to M503 with depth information by SHC (all M... puzzles maxlex and included in my batch of 23 february)

9876.....5.....86.4.........6.38..25.5..1263.......1.8...26..8....1..2.3....53.1. 2 L15 in mith_list_23jan_can
987......6..85....4.........6.5.32...3.12..65....861.3...36..58...2....1....1.32. 2 M514
987......6...........85....4..3..2......2..43....1.8.5.4.23.5.1.1.5.4.3.....8142. 2 M790
987......6...........85....4..3..2......2..43....1.8.5.4.23.5.1.1.5.4.2.....8143. 2 M429
987......6..95.....4.......3..21.65....5.3..2....96.31.3.1...2.....6.59.....2.1.3 3 M443
9876.....5.....96..4.......3...5.21....2..6.3...1.3.95...31..2.....6935......21.. 3 M503

details for transition M429 (te2) to M443 (te3) extracted (and completed with labels etc) from the log file:
"
987......6...........85....4..3..2......2..43....1.8.5.4.23.5.1.1.5.4.2.....8143. 11.7/1.2/1.2 M429
987......6.........1.85....4..3..2......2..43....1.8.5.4.23.5.1...5.4.2.....8143. 11.7/1.2/1.2 modif
987......6..95.....4.......3..21.65....5.3..2....96.31.3.1...2.....6.59.....2.1.3 11.7/1.2/1.2 M443 maxlex of previous line
18/02/2022 20:44:30"

Hendrik