The New Sudoku Players' Forum

[coloin]

....Meanwhile, what do you mean by "doesn't really add up?"

Thanks for the explanation ... the MC grid is the obvious example of the potential new transformation...
I was just worried that the many orbits of the sudokuP grids in the MCgrid would be connected [ still am ] !
Are all the 73 sudokuP minlex - all different ?

[eleven]

Just to give a sample for the equivalence of Mathimagics' F-transformed puzzle (with the 2's resolved).
On the left side you have a single 8 in r5c4 because the box positions 1 in r147c7 are seen by the 8 in r9c7 in the same column, and r7c147 by the 8 in the same row r7c2.
On the rigtht side there is a single 8 in r5c1, because in column 1 cells r369c1 are seen by the position 7 cell r9c7, and r789c1 by the box cell r7c2.

Code: Select all

1 . 2 | 3 . . | a . .      1 . 2 | . . . | . . .
. . . | 4 . . | 2 . .      3 . . | 4 . . | 2 . .
. . . | 2 . . | 5 . .      a . . | 2 . . | 5 . .
---------------------      ---------------------
2 6 . | X 7 . | b . .      2 6 . | . 7 . | . . .
. 7 . | . . 2 | . . .      X 7 . | . . 2 | . . .
. . . | . . . | . 2 .      b . . | . . . | . 2 .
---------------------      ---------------------
d 8 . | e 2 . | C . .      d 8 . | . 2 . | . . .
. 2 . | . . . | . . .      e 2 . | . . . | . . .
. . . | . . . | 8 . 2      C . . | . . . | 8 . 2

E.g. a transformed row skyscraper would then have the strong links in boxes and the weak link by the positions, and so on.

[blue]

Nice examples, eleven.

------

... the MC grid is the obvious example of the potential new transformation...

Yes. The MC grid has 2592 automorphisms under the full SudokuP group ... 648 are in both groups.

Are all the 73 sudokuP minlex - all different ?

No. SudokuP "minlexing", gives 6 distinct "types".

Code: Select all

123456789456789123789123456231564897564897231897231564312645978645978312978312645 -  1 * (2*6^4) times
123456789456789123789123456231564897564897231897231564312645978978312645645978312 - 18 * (2*6^4) times
123456789456789123789123456231564897564897231897231564645978312978312645312645978 - 12 * (2*6^4) times
123456789456789123789123456231564897897231564564897231645978312312645978978312645 - 36 * (2*6^4) times
123456789456789123789123456564897231897231564231564897978312645312645978645978312 -  4 * (2*6^4) times
123456789564897231978312645645978312789123456231564897897231564312645978456789123 -  2 * (2*6^4) times

BTW: I made a mistake in my earlier post -- fixed now.

[Mathimagics]

Have you seen

estimated ed-SudokuP above?

Very strong evidence to suggest that the true count is under 180,000.

Oh, dear me, it's public humiliation time again ...

That figure is demonstrably rubbish!

I think that we would all agree that, failing any mathematical breakthrough, the only way to count essentially different SudokuP grids is by brute force, by which I mean counting the number of essentially different Sudoku grids that can be transformed into SudokuP's (ie: are isomorphic in the standard Sudoku sense to a SudokuP grid).

This is a simple process and computationally feasible. I have made a start on the smaller (gsf) bands and have so far completed 3% of the 5,472,730,538.

The SudokuP isomorphism count is already at 6,315,106, or 4.1% of the total grids counted. That percentage appears to be trending down as the job progresses, but even if it comes down to 3%, say, then the number of ed-SudokuP grids is somewhere around 165 million. This looks much more like a sensible figure, it's roughly 25% less than the number of "essentially P-different" SudokuP grids using the restricted P-equivalence, ie 214,038,113.

Apologies to all!

[coloin]

Well .... good to see hat we will have the number soon !

Except im confused slightly - and I dont understand how we went wrong !
It might be that gsf bands 1-31 have repeating minirows [r2c3=6] and these do have more sudokuP ....
Interpreting blue's figures that there are only 6 minlex [2592] must mean that some of the 2592-orbits are interconnected ....

so are you counting 6 or 73 for the mc grid ?

[Mathimagics]

so are you counting 6 or 73 for the mc grid ?

Neither! We just test each ed-Sudoku grid, and count 1 if ANY SudokoP isomorphism found, otherwise 0. No matter how many isomorphisms, all are equivalent for all intents and purposes.

Well .... good to see that we will have the number soon!

At the current rate, the final tally is 3 weeks (!!) away. But this can be reduced dramatically if Serg (or anybody) can tell me how to reduce the set of isotope-transformations that need to be checked.

In a post above, on page 3 of this thread, he says there is a reduced set of 1296 transformations, whereas the best I have is 46656, so potentially a reduction by factor of 36 is possible.

It's all to do with finding a complement of the SudokuP symmetry group. I'm battling to try and identify this reduced set, hopefully Serg will respond soon!

[Mathimagics]

Hey, I figured it out! It's rather magical, but yes, as Serg said, there are just 1296 isomorphisms we need to check in order to determine if a non-SudokuP grid X has a SudokuP-isomorph.

Using this reduced set tells us that {MC} has 73 such isomorphisms, each of which corresponds to a full set of 2592 isomorphisms in the full set of 3,359,232 isomorphisms.

I'm restarting the jobs, and expect results within a day or two ...

[dobrichev]

A valid SudokuP grid is a union of 9 mutually disjoint "valid" single-digit templates.

Code: Select all

........1 invalid template: r1c9 collides with r7c3
...1.....
.1.......
.....1...
.......1.
1........
..1......
......1..
....1....

...1..... valid template (from the opening post)
1........
......1..
.....1...
.1.......
........1
....1....
..1......
.......1.


All templates count to 46656 and "valid" templates are a subset of them.

If we start from a grid in canonical form and want to test it for P-property, then we must expand it in 36x36 ways, namely
- swap r4,r5,r6 = 6 ways
- swap r7,r8,r9 = 6 ways
- swap c4,c5,c6 = 6 ways
- swap c7,c8,c9 = 6 ways
The rest transformations are preserving the P-property. (unless I am wrong, am I?)

Hi Mathimagics,
I see you finally choose the second approach from this post (from the first page of this thread).

Let talk about the first approach - by generating sudokuP from scratch using templates (or whatever you named them).
You should operate only with the p-templates (some counted them earlier in this forum, they are far less than 46K).
You may choose a suitable canonical form. Say, if you order all possible templates, then the grid representation could be a ordered set of the 9 template indexes. The canonical form may be chosen to have minimal such set.
You should write the respective sudokuP-to-sudokuP canonicalization procedure, which can terminate once it founds that the given (sub)grid has ANY better (lesser, closer to the canonical) P-morph.
Then you can generate all sudokuP grids in this way, by joining each p-compatible template (respectively p-subgrid) with those that are later in the chosen order.
Choosing a good templates order and canonical form (not necessarily the one above, it is just an example that first came in my mind) could benefit from the order of joining the templates and respectively minimize the canonicalization work.
You may think for applying the canonicalization before all 9 p-templates are joined, even pre-build a table with all p-template morphs, and apply logic for non-canonical morphs elimination as earlier as possible in the generation process.

This might, or might not outperform the loop over all essentially different ordinary sudoku grids. But with some luck it might outperform it by orders of magnitude.

Cheers,
MD

[Mathimagics]

Hi Mladen,

You are absolutely right, and I should have paid more attention to your post in the first place. It took me a long time to realise the truth of the "1296 (6^4) rule". Serg had also pointed this out, by the way.

I will pay much closer attention to your suggestions for an alternative approach. That might also serve the useful purpose of providing independent verification of whatever result I get from my isomorphism checker.

Speaking of which, it is progressing nicely, having completed 6% of the 5,472,730,538 Sudoku catalog in 1 hour. We'll have a result probably in 15 hours time.

Cheers
Jim

[Serg]

Hi, Mathimagics!

Hey, I figured it out! It's rather magical, but yes, as Serg said, there are just 1296 isomorphisms we need to check in order to determine if a non-SudokuP grid X has a SudokuP-isomorph.

I should explain - what I meant when I was saying about checking 1296 transformations instead of checking 3359232 transformations from VPT Group.

Definition
SudokuP Validity Preserving Group or PVP Group is group of transformations preserving validity of any valid SudokuP puzzle or solution grid. This group is generated by following set of transformations and is subgroup of VPT Group.

1. Transposing.
2. Permutations of 3 bands.
3. Permutations of 3 stacks.
4. The same permutations of rows in every band.
5. The same permutations of columns in every stack.

Totally we have 2 x 6^4 = 2592 isomorphic transformations.

Suppose one wants to check - what images (i.e. results of grid's transformation) of given valid SudokuP solution grid are valid under the action of VPT Group (3359232 transformations)? It's no sense to check results of PVP Group, because images of those 2592 transformations will be definitely valid SudokuP solution grids. It's not so obvious, but can be easily proven, that applying PVP Group to invalid SudokuP solution grid will give invalid SudokuP solution grids only (2592 grids at most).

Now let's consider VPT Group partition by left cosets (Group Theory terminology) of PVP Group. VPT Group is divided by 1296 cosets, each coset containing 2592 transformations. Each coset has its own representative t (transformation from VPT Group), that produces all coset's transformations by applying t to each PVP Group transformation (coset contains elements: t p1, t p2, ... t p2592). So, we have 1296 representatives (including "Do nothing" transformation) for VPT Group partition by left cosets of PVP Group. If we want to check what images of given valid SudokuP solution grid are valid under the action of VPT Group, we need to check images of applying 1296 representatives only to given valid SudokuP solution grid.

Those 1296 representatives can form group if PVP Group is normal (hello, GAP!).

Serg

[Mathimagics]

Thanks Serg,

Actually I found that GAP was no help with this, since the PVP group (SudokuP symmetry group) is NOT a normal subgroup of VPT, the Sudoku symmetry group.

I was looking to use GAP to take the complement of PVP group wrt VPT group. But GAP won't do this unless the subgroup is normal. I was in the process of doing something much like you described above when I realised that a simple combinatorial approach must be possible, which I worked out, blissfully unaware that dobrichev had actually given the answer earlier.

If we just use permutations of Bands 1 and 3, plus permutations of stacks 1 and 3, then we don't change the center block B5, but we still hit every possible orbit connection, and do so exactly once.

In fact this could be applied to any block we choose (dobrichev used B1, which is good for canonical form operations).

This leads to a very efficient algorithm for counting the orbit connections - we can do it with 1296 x SWAP operations, where each SWAP only exchanges one pair of rows or columns.

BTW: my job to enumerate the grids with SudokuP isomorph is faithfully recording each one AND the isomorphism counts. This involves little overhead since 97% of Sudoku grids appear to have no SudokuP isomorph, but it does mean we have an "audit trail" and can cross-check any individual case.

[blue]

Definition
SudokuP Validity Preserving Group or PVP Group is group of transformations preserving validity of any valid SudokuP puzzle or solution grid. This group is generated by following set of transformations and is subgroup of VPT Group.

1. Transposing.
2. Permutations of 3 bands.
3. Permutations of 3 stacks.
4. The same permutations of rows in every band.
5. The same permutations of columns in every stack.

Totally we have 2 x 6^4 = 2592 isomorphic transformations.

I argued earlier that this isn't the full "PVP" group.
I won't labor the point, but it's the intersection of the "full group" with the Sudoku VPT group.
I'ld rather see it called the "restricted PVP" group, (r)PVP, or something similar ... if using "intersection" is too cumbersome.
Don't mind me, though.

Now let's consider VPT Group partition by left cosets (Group Theory terminology) of PVP Group. VPT Group is divided by 1296 cosets, each coset containing 2592 transformations. Each coset has its own representative t (transformation from VPT Group), that produces all coset's transformations by applying t to each PVP Group transformation (coset contains elements: t p1, t p2, ... t p2592). So, we have 1296 representatives (including "Do nothing" transformation) for VPT Group partition by left cosets of PVP Group. If we want to check what images of given valid SudokuP solution grid are valid under the action of VPT Group, we need to check images of applying 1296 representatives only to given valid SudokuP solution grid.

Those 1296 representatives can form group if PVP Group is normal (hello, GAP!).

For what Mathimagics is doing, it's right cosets, rather than left cosets, that are relevant ... with t's acting on Sudoku grids, instead of SudokuP grids. dobrichev's transformations can be used as t's. [ Since they form a group, they can be used for both right and left cosets. ]

BTW: The (restricted) PVP group is not a normal subgroup of the Sudoku VPT group. dobrichev's transformations also form a subgroup of the Sudoku group, that isn't a normal subgroup. I see Mathemagics just covered the 1st part.

BTW: my job to enumerate the grids with SudokuP isomorph is faithfully recording each one AND the isomorphism counts.

Good !
Do you plan to use that to get the total number of Sudoku grids having a (Sudoku) transformations to (at least one) SudokuP grid ?

I think that we would all agree that, failing any mathematical breakthrough, the only way to count essentially different SudokuP grids is by brute force, by which I mean counting the number of essentially different Sudoku grids that can be transformed into SudokuP's (ie: are isomorphic in the standard Sudoku sense to a SudokuP grid).

I understand what you're doing, but I don't think you should the term "essentially different SudokuP grids".

[Mathimagics]

Hi blue,

Do you plan to use that to get the total number of Sudoku grids having a (Sudoku) transformations to (at least one) SudokuP grid ?

Yes, that's just what I'm doing.

I don't think you should the term "essentially different SudokuP grids".

I think we have agreed, have we not, that essentially different is taken to mean not Sudoku-equivalent, ie we assume the basis of comparison is the full Sudoku symmetry group.

So the term "essentially different Sudoku-V" grids has common sense of meaning for any Sudoku variant Sudoku-V.

If we are discussing equivalence under other definitions, eg P-equivalence, then we will qualify this, eg: essentially P-different, not P-equivalent, etc. The qualifier will generally be assumed to be a reference to a group that only includes P-preserving transformations.

Does that seem reasonable?

[blue]

Hi Mathimagics,

I understand what you're doing, but I don't think you should the term "essentially different SudokuP grids".

I think we have agreed, have we not, that ...

Well ... I sure didn't, and wouldn't want to agree to that.
If that was the decision earlier in the thread, then I guess I need to apologize.

My main objection, is that SudokuP grids that wouldn't qualify as "essentially different"/"essentially distinct" under that definition, aren't as "(essentially) equivalent" as you might like them to be.
It's true that one can be mapped to the other using a Sudoku transformation.
It isn't true that a valid puzzle for one, maps to a valid puzzle for the other, using the same transformation.
For an example, the first two grids in this post (about the MC grid), are related by the transformation that swaps rows 8&9. But here are two puzzles related by the same transformation:

Code: Select all

+-------+-------+-------+    +-------+-------+-------+
| 1 2 3 | 4 5 6 | 7 8 9 |    | 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |    | 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |    | 7 8 9 | 1 2 3 | 4 5 6 |
+-------+-------+-------+    +-------+-------+-------+
| 2 3 1 | 5 6 4 | 8 9 7 |    | 2 3 1 | 5 6 4 | 8 9 7 |
| 5 6 4 | 8 9 7 | 2 3 1 |    | 5 6 4 | 8 9 7 | 2 3 1 |
| 8 9 7 | . . . | 5 6 4 |    | 8 9 7 | . . . | 5 6 4 |
+-------+-------+-------+    +-------+-------+-------+
| 3 1 2 | 6 4 5 | 9 7 8 |    | 3 1 2 | 6 4 5 | 9 7 8 |
| 6 4 5 | 9 7 8 | 3 1 2 |    | 9 7 8 | . . . | 6 4 5 |
| 9 7 8 | . . . | 6 4 5 |    | 6 4 5 | 9 7 8 | 3 1 2 |
+-------+-------+-------+    +-------+-------+-------+
      (2 solutions)    #1          (1 solution)     #2

As Sudoku puzzles, they both have two solutions.
As SudokuP puzzles, the first still has two solutions, but the 2nd one doesn't.

[Mathimagics]

blue's point is quite valid ..

Yes, we did agree much earlier in the thread, that the definition of "essentially different" should be consistent, after Serg pointed out that P-equivalence and S-equivalence were by no means the same.

We have adopted the "essentially different" definition using the Sudoku group, I guess mainly because we can give it a strict and generally applicable mathematical interpretation. It can be used for any variant whose solutions sets are a subset of Sudoku grids, and such a definition is needed in any case.

Semantic problems will always be possible when we use "plain English" terms for mathematical properties. What I've tried to do is to marry the reluctant couple here!

Your examples are not P-equivalent, and perhaps that's the context in which puzzles (partially completed grids) need to be compared.

I am open to suggestion for alternate terminology, if we need to change so be it, but let's do it soon so we can get it out of the way and can still edit our posts!