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

[mith]

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

A min-expand is always the expanded form of some minimal (possibly itself), but the expanded form of a minimal is not necessarily a min-expand.

Consider as an example the following puzzles (solution minlex form):

Code: Select all

1.3.56....571.9.3.69.37......1.93..75.96.73.....51.......96..........4..9.5...86.;78  (max-expand, 31c)
1.3.56....571.9.3.69.37......1.93..75.96.73.....51.......96..........4....5...86.;1   (30c)
1.3.56....571.9...69.37......1.93..75.96.73.....51.......96..........4..9.5...86.;162 (30c)
1.3.56....571.9...69.37......1.93..75.96.73.....51.......96..........4....5...86.;3   (min-expand, 29c)

If we take the minimals of the max-expand, we get:

Code: Select all

1.3.5......71.9.3.69..7......1..3..75.96.73.....51.......96..........4....5...86. expands to 1
1.3.5......71.9...69.37......1..3..75.96.73.....51.......96..........4....5...86. expands to 3 (this is Loki)
1.3.56.....71...3.69..7......1.93..75.96.73.....51.......96..........4....5...86. expands to 1
1.3.56.....71.....69.37......1.93..75.96.73.....51.......96..........4....5...86. expands to 3

The max-expand is not the singles expansion of any of these minimals. All four puzzles in the expanded database are expanded forms (no singles can be added), but only two are singles expansions of a minimal (because none of the minimals can place 9r9c1 as a single, while it can be added without affecting depth), and only one is the min-expand (removing a digit or digits does not leave an expanded form) - in this specific case, it is simply a consequence of 3r2c8 making 3r3c4 a single by not the other way around.

We can reproduce the entire database from the min-expands by using the adder script (test all possible placements from the solution, singles expand, check that depth is still 3). We can also reproduce the entire database from the max-expands (by finding all minimals and singles expanding those), but again we have to use the adder script (otherwise we miss puzzles like id 162 in the example; it is only accessed by adding 9r9c1 to the min-expand). In between (and inclusive of) the min-expands and max-expands, we have all possible puzzles which are expanded forms (no singles available) - some of which are not the expanded form of any minimal.

[coloin]

.....by using the adder script (test all possible placements from the solution, singles expand, check that depth is still 3).

I think this expansion is a valid course, provided the rating SE or TEdepth is the same.
It would considerably reduce the database and group togther puzzles of exactly the same solving difficulty and same solution grid.....
By minimizing and min-expanding [for efficiency ] there may well be a new superior puzzle produced [and there shouldnt be an inferior one in any of the minimals]

[denis_berthier]

A min-expand is always the expanded form of some minimal (possibly itself), but the expanded form of a minimal is not necessarily a min-expand..

What I call a min-expand is by definition the expansion of a minimal by Singles.
It is obvious that there can be more expansions of minimals than only those by Singles (such as by adding a digit from the solution and then re-applying Singles if you want to get an "expanded form").

But what you're writing remains highly ambiguous.
One can talk of THE expansion of a minimal by Singles, but one can't talk of "THE expanded form of a minimal" by any other type of expansion. There are many such expansions.

[mith]

To be clear, I am always talking about expansion by singles in this context. The quoted line should have read: "A min-expand is always the (unique) singles expanded form of some minimal (possibly itself)"

The minimal_te3 database contains minimal puzzles which are in T&E(3). Each minimal puzzle has a unique singles expansion.

The expanded_te3 database contains expanded forms which are in T&E(3). A puzzle E is an expanded form if the singles expansion of E is E. We can also talk about the expanded form of a puzzle P (that is, the unique singles expansion of P), and we can talk about the set S of all puzzles P such that the singles expansion of S is E. (S may contain puzzles other than E, and S may contain minimals, but this is not a requirement for appearing in the expanded database.)

While running, the databases are not necessarily closed and min-expand/max-expand may not be determined within the expanded database. However, I only publish updates when the databases are closed under the following script operations:

a1. [minimizer] for each expanded form E in the expanded database, every minimal of E is in the minimal database
a2. [minimizer] for each minimal M in the minimal database, the unique expanded form of M is in the expanded database
b. [adder] for each expanded form E in the expanded database, every expanded form which is in T&E(3) and which contains all the givens present in E is in the expanded database
c. [transformer] for each expanded form E in the expanded database, every puzzle which differs from E only by permutation of some cycle in the given digits is in the expanded database (such a puzzle is necessary an expanded form)

Even when the databases are not closed, there is a growing subset of puzzles in the databases which are; of course once a subset of puzzles is closed under the above operations, it remains closed. And of course we track these as "trees"; the subset of puzzles sharing a solution grid is a closed subset under minimizer+adder (and so far it is a minimal closed subset - it's possible there will be some solution grid with multiple unrelated trees, though). Trees related by the transformer operation form closed clusters under all three operations.

The databases are of course not closed under the neighborhood searches on minimal puzzles, but this does not affect min-expands and max-expands. (It's also quite possible they will eventually reach that point at least for -2+1.)

We can determine the T&E(3) min-expands in the expanded database when the min-expand's tree is closed under the above operations: a min-expand in the expanded_te3 database is a puzzle which does not contain as a proper subset (the givens of) a smaller puzzle in the expanded_te3 database. However, we can also define it explicitly and independently from T&E depth (or any other condition/requirement) and from the state of the database as follows:

A min-expand is defined as a puzzle which is the (unique) singles expansion of each of its own minimals.

In the Loki tree example: the 29c min-expand has two minimals, and the singles expansion of each of these two minimals is the 29c min-expand. The other expanded forms do not share this property - they each have a minimal such that the minimal's singles expansion is a different puzzle (a proper subset of the original).

max-expand is defined with respect to the requirements for entry into the database, but can still be defined independently of the state of the database: a T&E(3) max-expand is a T&E(3) puzzle which is not the proper subset of some other T&E(3) puzzle (we don't need to specify that the max-expand is an expanded form; if it weren't, obviously its singles expansion would be in T&E(3) and contain it as a proper subset). We just don't determine the max-expand(s) until the tree is closed.

[denis_berthier]

To be clear, I am always talking about expansion by singles in this context. The quoted line should have read: "A min-expand is always the (unique) singles expanded form of some minimal (possibly itself)"

The main problem is with the other part: "but the expanded form of a minimal is not necessarily a min-expand"

The minimal_te3 database contains minimal puzzles which are in T&E(3).

Where is this database available?

A min-expand is defined as a puzzle which is the (unique) singles expansion of each of its own minimals.

That's a new turn (not equivalent to the definition in the first post), but it's a very bad definition, for many reasons:
1) It's very difficult to check: one would have to generate all the minimals of P - possibly thousands;
2) it's much too restrictive: there can be minimals (probably a vast majority of minimals) that are not minimals of any min-expand in your sense;
3) It's useless in practice (other than as a technical tool in your search process): for the previous reason.

My definition (P is a min-expand iff P is the expansion of a minimal by Singles) is and has always been:
- easy to check: the main data remain the minimals, the min-expands are just there to group them;
- natural: having the same min-expand defines an easy to check equivalence relation compatible with any reasonable measure of complexity (T&E-depth, B, BxB...) - which the SER is not;
- self-contained: no need to refer to the current state of a database;
- easy to use: all the minimal puzzles that have the same min-expand (and all the puzzles in-between) have the same complexity for any reasonable measure ;


As coloin says:

It would considerably reduce the database and group togther puzzles of exactly the same solving difficulty and same solution grid.....

The only way to do this is with my definition of min-expands.
It would require a larger database of min-expands than provided by mith, but it could be used straightforwardly without any ado.

When I recently tried to do some elementary stats on minimals in T&E(3) and their min-expands (in my sense), I found very large discrepancies between what I computed from the delivered "min-expand" database and what I got by re-generating minimals from a random sample of the "max-expands". That's how I was led to restart this whole discussion.

-

[mith]

I posted the minimals here: post338328.html#p338328 First column minimals, second column singles expansion (each morphed to minlex form). When I finally get around to checking hendrick’s and Paquita’s newer puzzles I’ll update this.

The definition in my previous post is logically equivalent to the definition in the first post. It’s not hard to prove (but I’m at work and I’m not going to type it up on my phone).

I’ll respond to some of the rest later, but ultimately what it boils down to is that the database already has the information you would find more useful (singles expansions of minimals); the min-expand list (which has used the definition in the first post consistently) is what Ifind more useful and it’s not much extra work to produce it (especially alongside the max-expand list).

[mith]

Likely the source of confusion on definitions is stemming from my conflation of two concepts a couple years ago: that of "singles expansion of a minimal" (which Denis called a min-expand), and this:

question: can one find "absolute" min-expands, i.e. min-expands that can contain no smaller min-expand; do they always have to be minimal puzzles (with no other expansion than themselves); perhaps add a y/n/? column for mentioning who is an absolute min-expand (the ? for puzzles that haven't been explored); but I don't know id such search is practicable: calculations may involve complex recursive search;

What I call min-expands are what Denis would call (or would have called) "absolute min-expands". (FWIW, the search is very much practical. )

With that out of the way:

A min-expand is defined as a puzzle which is the (unique) singles expansion of each of its own minimals.

That's a new turn (not equivalent to the definition in the first post), but it's a very bad definition, for many reasons:
1) It's very difficult to check: one would have to generate all the minimals of P - possibly thousands;

My definition (P is a min-expand iff P is the expansion of a minimal by Singles) is and has always been:
- easy to check: the main data remain the minimals, the min-expands are just there to group them;

- self-contained: no need to refer to the current state of a database;

The difference in difficulty you are expressing here is primarily because in one case you are assuming you already have the minimals and in the other you are assuming you have to generate all of them. This is true if you already have the closed set of minimals and their singles expansions, sure. The issue is: that is a state of the database. If you have an expanded form on its own, before generating its minimals and their singles expansions we definitely cannot tell if the expanded form is the singles expansion of a minimal (your definition) nor of all minimals (mine).

Let's consider something more extreme:

• Is every solution grid a min-expand by your definition? Almost certainly yes, but to show it for a specific solution you either need to generate minimals until you find one in T&E(0), already have a minimal in T&E(0) which has that specific solution, or come up with an algorithm to generate a T&E(0) minimal from the solution.
• Is every solution grid a min-expand by my definition? Almost certainly yes, but to show it for a specific solution I either need to generate minimals until I find one in T&E(1+), already have a minimal in T&E(1+) which has that specific solution, or come up with an algorithm to generate a T&E(1+) minimal from the solution.

It's a pretty similar state of affairs until you start with the assumption of having all the minimals you care about and all their singles expansions. In the context of this search specifically, I am already generating all the minimals, their singles expansions... but also all expanded forms related to them (whether they are singles expansions of minimals or not), the solution grids associated with them... so it's really not much difference in effort whether I am listing the min-expands by my definition or the singles expansions of minimals; one involves grouping things in the expanded database, the other involves grouping things in the minimal database.

2) it's much too restrictive: there can be minimals (probably a vast majority of minimals) that are not minimals of any min-expand in your sense;

This only matters if you are trying to generate all the minimals from the min-expand list directly (and care about having all the related minimals in the first place). Which is unnecessary now that I've provided the full list of minimals.

3) It's useless in practice (other than as a technical tool in your search process): for the previous reason.

- natural: having the same min-expand defines an easy to check equivalence relation compatible with any reasonable measure of complexity (T&E-depth, B, BxB...) - which the SER is not;

- easy to use: all the minimal puzzles that have the same min-expand (and all the puzzles in-between) have the same complexity for any reasonable measure ;

The use, for me, is that the min-expands and max-expands define boundaries for the complexity within a given solution tree. For a given (closed) tree, the set of puzzles with the highest complexity (for any reasonable measure) will include at least one of the min-expands. When I'm searching for trivalue oddagons, if I have studied a 29c min-expand I don't particularly care if I'm skipping a 30c that contains it as a subset. Either the 30c has the same complexity, or the extra given lowers the complexity. It doesn't matter to me whether the 30c is the singles expansion of a minimal or not.

The minimals also don't matter much to me at this point, other than that they are used for generating puzzles. Every minimal in the database has an equivalent complexity to a puzzle in the (full) expanded database (its singles expansion). The expanded database has replaced minimals as the main data, in my view.

The min-expands by my definition are the minimal expanded forms, rather than the singles expansions of minimals. Just as the max-expands are the maximal expanded forms, rather than the singles expansions of maximals (whatever that would mean).

I agree that if you are treating the minimals as the main data, having an equivalence relation between them is useful. And I may well expand what I am publishing to make that information easier to pull out (though again, it's not hard to generate this from the list of minimals I have provided).