The New Sudoku Players' Forum

[coloin]

If it is any help i found 33 ED puzzles with this pattern

Code: Select all

+---+---+---+
|8..|...|7..|
|.1.|..3|.4.|
|..6|...|..5|
+---+---+---+
|...|..1|.2.|
|...|.4.|...|
|.6.|7.5|...|
+---+---+---+
|5..|...|..8|
|.2.|6..|.1.|
|..7|...|5..|
+---+---+---+   

It was rather easier to generate the 2452 [edit - Now 2457] ED puzzles with the extra clue
[edit - Generated by up to [-5+5] but possibly there are a few more]

Code: Select all

+---+---+---+
|3..|...|1..|
|.5.|..8|.7.|
|..4|...|..6|
+---+---+---+
|...|1.2|.8.|
|...|.3.|...|
|.9.|4.5|...|
+---+---+---+
|1..|...|..4|
|.7.|5..|.9.|
|..3|...|6..|
+---+---+---+   

This could well be the same pattern that m_b_metcalf submitted as the next pattern.

C

[m_b_metcalf]

This could well be the same pattern that m_b_metcalf submitted as the next pattern.

But, in fact, it isn't.

Regards,

Mike

[dobrichev]

One could argue that clue permutation is included in "essentially different", but that no longer seems precise enough to me.

...I noticed, that i got less puzzles to check, when - while filling in digits - i sorted out sub-puzzles, for which there is a mapping (according to the automorphisms of the complete pattern) to a puzzle with smaller minlex form...

The only thing I'm convinced of is that starting with a sub-pattern of a puzzle's pattern, generating all appropriate non-isomorphic sub-puzzles for that sub-pattern, expanding the generation by upsizing through larger sub-patterns and finally to the original pattern, should produce all non-isomorphic puzzles with that pattern, including the original puzzle (or morphs thereof). [edit: AFAIK, even this has yet to be proven.]

Which transformations are safe to be applied to the intermediate sub-puzzles when targeting morphs eliminations?
There are at least 2 choices: a) those transforming the intermediate sub-pattern into itself, or b) those transforming the complete pattern into itself.
I can't follow the whole experiment but it looks like the root of the evil could be in this detail.

[Mauricio]

Which transformations are safe to be applied to the intermediate sub-puzzles when targeting morphs eliminations?
There are at least 2 choices: a) those transforming the intermediate sub-pattern into itself, or b) those transforming the complete pattern into itself.
I can't follow the whole experiment but it looks like the root of the evil could be in this detail.

b) is the only sane choice, though I don't have the motivation to find and explain an example that shows that a) is wrong, but I am sure it is (I would consider a pattern where the cells fill box 1, r1c4 and r4c1 and the subpattern is box1).

[ronk]

There are at least 2 choices: a) those transforming the intermediate sub-pattern into itself, or b) those transforming the complete pattern into itself.

b) is the only sane choice ...

I don't think anyone has proposed that a) is the correct choice, at least not after having given the choice some thought.

If it is any help i found 33 ED puzzles with this pattern
...
It was rather easier to generate the 2452 ED puzzles with the extra clue

Perhaps. Your results would help validate champagne's process if ...

1. Your process is essentially different from his, and
2. He obtains the same results.

[edit: add response to coloin]

[eleven]

I am sorry, that i bothered others with my own confusion. The mistake i made was, that in the same process i calculated the minlex order to 2 different orders of cells, first to the order of the cells in the sub-pattern, then to the order of the cells in the complete pattern.
It is easy to avoid this problem, when you define an assignment order for all cells in forward and always minlex to this.
Then at any step (e.g. when the last of a group of symmetrical clues is added), you can look, if some morph of the sub-puzzle has a lower minlex-order (in the predefined order), and just eliminate it, if this is the case.

[eleven]

Yes, no, yes, no, yes, no, ...
I guess i changed my mind 10 times, how this question should be answered:

Is it possible to enumerate all non equivalent puzzles from a set of all non equivalent sub-puzzles ?

My answer now is no again.

My last thought had been, that if you canonicalize sub-puzzles and complete puzzles to the same order of cells, i.e. find the minimal minlex form for a predefined order (where all sub-puzzle cells come before the rest), then for each complete puzzle there is a morph, for which you can find a numbering of the sub-puzzle cells, which is minimal for the sub-puzzle (just minlex these cells first and then renumber the rest accordingly).
But this is not true, when sub-puzzle cells are in the same unit as complementary cells.

Example:
I defined the cell order as
32,40,48,50,2,6,74,78,18,26,54,62,14,34,46,66,10,16,64,70

For this order this 16-clue sub-puzzle has that minimal minlex form:

Code: Select all

..2...1.......2...4.......6.....1.3.....2.....2.3.4...7.......8...2.......3...5..
..2...1.......2...4.......6.....1.2.....2.....2.3.4...7.......8...1.......3...5..

But this puzzle

Code: Select all

..2...1...1...2.4.4.......6.....1.3.....2.....2.3.4...7.......8.4.2...1...3...5..

has as minimal minlex of its sub-puzzle the first one. Its sub-puzzle never can be morphed/renumbered to a minimal one. So if you throw away this first sub-puzzle, you have no chance to find the complete puzzle or an equivalent by adding numbers to any non equivalent sub-puzzles.

Code: Select all

+-------+-------+-------+  +-------+-------+-------+     +-------+-------+-------+
| . . 5 | . . . | 6 . . |  | . . 2 | . . . | 1 . . |    | . . 2 | . . . | 1 . . |
| .17 . | . .13 | .18 . |  | . 1 . | . . 2 | . 4 . |    | . . . | . . 2 | . . . |
| 9 . . | . . . | . .10 |  | 4 . . | . . . | . . 6 |    | 4 . . | . . . | . . 6 |
+-------+-------+-------+  +-------+-------+-------+    +-------+-------+-------+
| . . . | . . 1 | .14 . |  | . . . | . . 1 | .*3 . |    | . . . | . . 1 | .*2 . |
| . . . | . 2 . | . . . |  | . . . | . 2 . | . . . |    | . . . | . 2 . | . . . |
| .16 . | 3 . 4 | . . . |  | . 2 . | 3 . 4 | . . . |    | . 2 . | 3 . 4 | . . . |
+-------+-------+-------+  +-------+-------+-------+    +-------+-------+-------+
|11 . . | . . . | . .12 |  | 7 . . | . . . | . . 8 |    | 7 . . | . . . | . . 8 |
| .19 . |15 . . | .20 . |  | . 4 . |*2 . . | . 1 . |    | . . . |*1 . . | . . . |
| . . 7 | . . . | 8 . . |  | . . 3 | . . . | 5 . . |    | . . 3 | . . . | 5 . . |
+-------+-------+-------+  +-------+-------+-------+    +-------+-------+-------+
     cell order           puzzle with min. sub-puzzle      normalized sub-puzzle

[ronk]

Example:
I defined the cell order as
32,40,48,50,2,6,74,78,18,26,54,62,14,34,46,66,10,16,64,70

So you are using "defined-cell-order minimum lexical order" instead of "row minlex?" If you used row minlex, it would make it much easier for us to follow (and perhaps verify your result.)

[eleven]

So you are using "defined-cell-order minimum lexical order" instead of "row minlex?" If you used row minlex, it would make it much easier for us to follow (and perhaps verify your result.)

With row minlex you have 2 different ways of minlexing the sub-puzzle and the complete puzzle. This makes things much more complicated.

[Mauricio]

What am I misunderstanding?

Code: Select all

. . 2|. . .|1 . .
. 3 .|. . 2|. 4 .
4 . .|. . .|. . 6
-----+-----+-----
. . .|. . 1|. 2 .
. . .|. 2 .|. . .
. 2 .|3 . 4|. . .
-----+-----+-----
7 . .|. . .|. . 8
. 4 .|1 . .|. 3 .
. . 3|. . .|5 . .

has minimal minlex with the predefined order than the puzzle posted.

But this puzzle

Code: Select all

..2...1...1...2.4.4.......6.....1.3.....2.....2.3.4...7.......8.4.2...1...3...5..

[eleven]

Now i don't understand.
As i see it this puzzle would be found from the non equivalent sub-puzzle "normalized sub-puzzle" (by adding digits to the other cells), different to the "But this" puzzle.

[ronk]

But this puzzle

Code: Select all

..2...1...1...2.4.4.......6.....1.3.....2.....2.3.4...7.......8.4.2...1...3...5..

has as minimal minlex of its sub-puzzle the first one.

This "puzzle" has multiple solutions. Was that your intent or did something go astray?

For this order this 16-clue sub-puzzle has that minimal minlex form:

Code: Select all

..2...1.......2...4.......6.....1.3.....2.....2.3.4...7.......8...2.......3...5..
..2...1.......2...4.......6.....1.2.....2.....2.3.4...7.......8...1.......3...5..

So these two sub-minimals are equivalent. Conjectures: Therefore, evaluating all possible combinations of clues for the same additional cells, r28c28 in this instance, should produce the same canonicalized results. Moreover, this would be independent of the chosen canonicalization method.

[ronk]

I verified champagne's exhaustive finding of 112 puzzles for the pattern of game 0169 with more conventional techniques, i.e., without using his reductions based on symmetry. More precisely, I checked that my 112 puzzles were equivalent to those dobrichev listed here, and assumed that champagne's list of 112 is also equivalent.

My process applied this command to the following template ...

gsfsudoku -gtm.0 -e"uniq(%#mc)" g0169partial.pattern | sed -e"s/ #.*//" > g0169partial.dat

Code: Select all

 .     .   1      | .   .   .   | 2       .   .     
 .     .   .      | .   .   X   | .       .   .     
 23    .   .      | .   .   .   | .       .   134   
------------------+-------------+--------------------
 .     .   .      | .   .   .   | .       X   .     
 .     .   .      | .   .   .   | .       .   .     
 .     X   .      | .   .   X   | .       .   .     
------------------+-------------+--------------------
 12345 .   .      | .   .   .   | .       .   123456
 .     .   .      | X   .   .   | .       .   .     
 .     .   234567 | .   .   .   | 1345678 .   .     

The cells were chosen such that the g0169partial.pattern had the same four automoprhisms as the full pattern.

A home brew program then relabeled clues in order 1,2,3 ... 9 in row order starting at r1c1. It also placed 'X's at the locations still requiring clues, i.e. r28c28, r4c6, r5c5, and r6c4. Explicitly, the command ...

myProgram g0169partial.dat > g0169full.pattern

... produced a file of 782919 templates, the first and last being ...

Code: Select all

..1...2...x...1.x.2.......1.....x.1.....x.....1.x.2...1.......2.x.1...x...2...1..
..1...2...x...1.x.2.......1.....x.2.....x.....1.x.2...1.......2.x.1...x...2...1..
..1...2...x...1.x.2.......1.....x.2.....x.....1.x.2...1.......2.x.2...x...2...1..
...
...
..1...2...x...3.x.4.......5.....x.6.....x.....3.x.7...8.......7.x.6...x...9...6..
..1...2...x...3.x.4.......5.....x.3.....x.....3.x.6...7.......6.x.8...x...9...8..
..1...2...x...3.x.4.......5.....x.3.....x.....3.x.6...7.......6.x.3...x...8...9..

Lastly, the command ...

gsfsudoku -gt -e"valid&&uniq(%#.c)" g0169full.pattern | tee g0169.dat

... produced said 112 puzzles. All are minimal and at least one can be solved with singles only. In actuality, the last step was assigned to six hyper-threads. Despite this, the entire process still took 8 days.

[eleven]

Congrats on that, Ron,
since i changed my mind now for the 11th time (there was a flaw, indeed there is a minimal minlex of the 20 clue with a minimal minlex sub-pattern), no objections are left to champagne's or your result.

The only doubt i still have is that it could be faster to calculate all 21's (with the help of 2 more symmetries).

[champagne]

I don't know so far what to do of it, but, compared to games with (slightly) smaller number of clues, I generated a relatively low number of puzzles with the pattern of the game 170

9 millions compared to several tens millions for recent patterns.

Have we passed the peak number or is it something linked to that pattern ???

champagne