The New Sudoku Players' Forum

[denis_berthier]

.
.
First, to make things clear: I'm not speaking of the generation process; I'm talking from the point of view of a user of a database.
One problem with the current state of affairs is, puzzles have been stuffed into the ph2010 database without anybody caring to have a look at the contents - except for the highest SERs and for adding exotic patterns to it. That's how the tridagon pattern could escape discovery for 12 years.
AFAIK, I've been the only one to analyse the large databases.
Things have been different with your T&E(3) database, because we talked of what I needed to run such analyses more easily. Unfortunately, there was this misunderstanding about the min-expands.

1) Minimal puzzles have always been the primary concept:
- the definition is self-contained: a puzzle can be checked to be minimal without any reference to any other puzzle, let alone to any database;
- minimal puzzles is what all the puzzle generators generate;
- this is what all the big databases contain;
- this is what (almost) all the published puzzles are;
- this is what allows meaningful statistical analyses.

2) Min-expands in my sense are a derived concept. The associated primary concept is the process of expansion by Singles.
Expansion of a puzzle P (minimal or not) by Singles:
- is uniquely defined;
- requires only trivial computations;
- is intrinsic (doesn't need any reference to any database);
- preserves all the reasonable classifications (but possibly not the SER).

3) Min-expands are the result of this trivial expansion process applied to minimals:
- no one is supposed to ask if a puzzle is a min-expand: min-expands are produced as the expansion of minimals; there's nothing to check about them;
- they are extremely useful for practical classification purposes: they allow to drastically reduce computation times. In order to get an idea of the gain, I started from a sample of 1000 puzzles in your max-expand database, I generated all their minimals, then I computed their min-expands and I finally reduced them by isomorphism: the gain between the minimals and the min-expands is > 7.

When starting from a database of minimals, the first step in studying them is this reduction process of their min-expands by isomorphisms.

-

[mith]

AFAIK, I've been the only one to analyse the large databases.

I have also been analyzing the T&E(3) databases, and since I am the one maintaining them and generating the vast majority of the puzzles, I have geared that specific data set (published alongside the max-expands and the expanded database as a whole) toward my needs. Now that we know the misunderstanding occurred, I can easily add singles-expansions-of-minimals as a superset of the current min-expand list.

1) Minimal puzzles have always been the primary concept:

Expanded forms (more fully the "Expansion of a puzzle P (minimal or not) by Singles") are also self-contained: a puzzle is an expanded form if its singles expansion is itself. This is actually easier to check than whether a puzzle is minimal.

Minimal puzzles are no longer what all puzzle generators generate. (It was also never the case that puzzle generators *only* generated minimals; they were just primarily used that way.) Of my scripts:

• one runs on minimals and generates minimals (though I have considered running it on expanded forms)
• one runs on expanded forms and generates minimals
• and the other two run on expanded forms and generate expanded forms

2) Min-expands in my sense are a derived concept. The associated primary concept is the process of expansion by Singles.

Agreed. The full expanded database is precisely the known set of T&E(3) puzzles after expansion by singles (from minimals or not). The minimal database is the set of minimals of the expanded database. Both singles-expanded-minimals (your min-expands) and minimal-expanded-forms (my min-expands, your absolute min-expands) are dervived from the concepts of singles expansion and of minimal puzzles.

3) Min-expands are the result of this trivial expansion process applied to minimals:
- no one is supposed to ask if a puzzle is a min-expand: min-expands are produced as the expansion of minimals; there's nothing to check about them;
- they are extremely useful for practical classification purposes: they allow to drastically reduce computation times. In order to get an idea of the gain, I started from a sample of 1000 puzzles in your max-expand database, I generated all their minimals, then I computed their min-expands and I finally reduced them by isomorphism: the gain between the minimals and the min-expands is > 7.

I can give you the exact count in the current database:

• 4634322 (minimals)
• 1112250 (expanded forms)
• 667883 (singles expansions of minimals)
• 207652 (approximate min-expands by my definition based on 2022-11 dataset)
• 63067 (approximate max-expands based on 2022-11 dataset)

(I am able to quickly determine the singles expansions of minimals count (~2 seconds) because I am already expanding the minimals and saving that to the database for cross-reference purpose.) No exact numbers for my min-expand definition since I am waiting to process other puzzles before I run the update script. The 2022-11 dataset is about 76% of the current, and min-expands and max-expands are already determined for that set.

[I could be doing this on the fly - the minimizer script already generates all minimals and their singles expansions, there is just an optimization to skip expanded forms generated by this process. Say we minimize a 32c, and one of the minimals expands to a 30c subset, we will have already generated all minimals of that 30c so I don't do it again; but instead I could remove this optimization and then just compare the singles expanded minimals to the original expanded form. The max-expands could likewise be tracked with a tweak to the adder script.]

Anyway, for my purposes, min-expands are a further >3 gain over singles expansions of minimals, and since my interest is primarily trivalue oddagon patterns in their most complex forms that's what I use. Like I said, if the database has a 29c min-expand and a 30c which is the 29c plus one extra given, I don't really care if the 30c is the singles expansion of a minimal or not. The 29c is sufficient for my purposes.

[denis_berthier]

.

I have also been analyzing the T&E(3) databases

Yes, I know, but I meant before that. And we are not doing the same kinds of analyses. This explains why we need different data.

Now that we know the misunderstanding occurred, I can easily add singles-expansions-of-minimals as a superset of the current min-expand list.

Yes, that would spare users the time to recompute them - the longest part being to eliminate the morphs.
BTW, this elimination process is a priori quadratic in time. I guess you don't do it directly on the whole set of expansions of minimals by Singles.

Expanded forms (more fully the "Expansion of a puzzle P (minimal or not) by Singles") are also self-contained: a puzzle is an expanded form if its singles expansion is itself.

Yes.

I can give you the exact count in the current database:

• 4634322 (minimals)
• 667883 (singles expansions of minimals)
• 63067 (approximate max-expands based on 2022-11 dataset)

Good, this confirms my results on a small sample of 1000 max-expands:
(/ 4634322 667883) = 6.9, very close to my 7.01.
(/ 4634322 63067) = 73.48, also very close to my 74.1.
.

[mith]

Correct, eliminating morphs is done primarily on the minimals as they are generated (via neighborhood search using gsf, with the uniq() flag) and to a much smaller degree there may be some elimination in the other scripts for expanded forms from a solution grid with a non-trivial isomorphism (there are only two such solution grids currently represented, and I have no idea if any morphs were actually caught in this way).

The singles expansion is then found for each unique minimal when it is generated (by generator or by minimizer) and saved in gsf-minlex form to the minimal database; if it is a new expanded form (as determined by gsf-minlex) it is also added to the expanded database in both gsf-minlex and solution-minlex forms (as well as the full solution grid for easy grouping by "tree").

[mith]

Discovered a dumb bug in my code while refactoring it. I don't think it is going to have an effect on the results but I will need to rerun one of the scripts to be sure.