The New Sudoku Players' Forum

[Mathimagics]

Hi coloin,

An isotope of grid X is one of 6^8 * 2 = 3359232 valid transformations of X.

If any isotope of grid X has SudokuP property, then it's one of a set of 2592 (6^4 * 2) isotopes which are SudokuP, since there are that many SudokuP-preserving transformations.

So we'd expect the total # of SudokuP-isotopes to be a multiple of 2592, and for the MC grid this is certainly the case, I count 189,216 = 73 * 2592 SudokuP isotopes.

I'll try to categorise those 73 sets (72 + 1 does seem odd, in both senses of the word!).

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

[blue]

.....
the mc grid - or any grid with a band with repeating minirows - maintains sudoku-p with a single row swap
looks like there might be 36 different "orbits" then in the mc ?

Code: Select all

+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
|231|564|897|
|564|897|231|
|897|231|564|
+---+---+---+
|312|645|978|
|645|978|312|
|978|312|645|
+---+---+---+


so how many of the 6 ^ 8 * 2 = 3,359,232 ways to protray the mc grid are sudoku-p,
a single row swop in the above mcgrid maintains it -
if each orbit has 6^4 * 2 "different" grids .... that doesnt really add up or does it ?

Hi Colin,

(6^4 * 2) * 73 of the Sudoku transformations, map the MC grid to a SudokuP grid.
The results cover 6 distinct SudokuP types.
These operations produce one one of each type

• doing nothing
• swap rows 2&3
• swap rows 2&3, swap rows 4&5
• cycle rows 1,2&3
• cycle rows 1,2&3, swap rows 4&5 cycle rows 4,5&6 in the opposite direction
• cycle rows 1,2&3 and columns 1,2&3, cycle rows 4,5&6 and columns 4,5&6 in the opposite direction

[blue]

Something has been missing in this discussion.

Earlier, Mathimagics wrote:

The elements of the SudokuP symmetry group should be a subset of the elements of the Sudoku symmetry group, or all is lost!

In the end, that doesn't turn out to be the case.

The group that has been under discussion, is the intersection the usual Sudoku group, and the (full) SudokuP group.
Like the Sudoku group, the SudokuP group is strictly larger than the intersection.
(There are transformations that map SudokuP grids to SudokuP grids, but usually destroy the integrity of Sudoku grids).

The full group, has 8 * 6^4 elements.

One of the missing transformations ... F, I've been calling it ... transforms each band, like this:

Code: Select all

+-------+-------+-------+      +-------+-------+-------+
| a b c | d e f | g h i |      | a b c | j k l | s t u |
| j k l | m n o | p q r |  ->  | d e f | m n o | v w x |
| s t u | v w x | y z ? |      | g h i | p q r | y z ? |
+-------+-------+-------+      +-------+-------+-------+

It's like a "transpose" for the positions of the (box) mini-rows.
It maps rows to boxes, boxes to rows, columns to box positions, and box positions to columns.

GAP string for F:

Hidden Text: Show

(4,10)(5,11)(6,12)(7,19)(8,20)(9,21)(16,22)(17,23)(18,24)(31,37)(32,38)(33,39)(34,46)(35,47)(36,48)(43,49)(44,50)(45,51)(58,64)(59,65)(60,66)(61,73)(62,74)(63,75)(70,76)(71,77)(72,78)

Adding "F" to the list of generators for the intersection, gives a set of generators for the full SudokuP group.

The set {D,F}, where D is the usual "transpose" operation, generates a group of size 8, that accounts for the factor of 8, in "(8 * 6^4)".
The most interesting elements, are E := F * D * F, and G := D * F * D.

G is like F, but it acts on stacks instead of bands.

E is like D, in that they're conjugates.
E maps rows to rows, and columns to columns ... 123456789 -> 147258369.
In addition, it maps boxes to box positions, and vica-versa.
It's like a "b/p" transpose, as opposed to an "r/c" transpose.

The remaining elements can be written as: D * E, D * F, and D * G.
(D * E), like D, E, F and G, has order 2 -- applying it twice, restores the original grid.
The other two have order 4. (One is the inverse of the other).

Have fun with that !

Cheers,
Blue.

[eleven]

blue is back. great.

[eleven]

Maybe we should clarify the definitions.

We have the Sudoku properties with the 9 digits in each row, column, box.
And the property, that all positions in the 9 boxes have all digits.
When i talked about the SudokuP property, i had in mind, that it would have all of them.

So i think, we should use another term for a group with just the additional property.

[Mathimagics]

Hi blue!

Nice to see ya!

Interesting point, still digesting it ... but I do note that your F transformation is not a Sudoku-group element, so by definition grids x and F(x) are "essentially different" wrt the Sudoku group, are they not?

We have the Sudoku properties with the 9 digits in each row, column, box.
And the SudokuP property, that all positions in the 9 boxes have all digits.
When i talked about the SudokuP property, i had in mind, that it would have all of them.

Me, too, otherwise we can all go home!

So i think, we should use another term for a group with just the additional property.

Not sure what you mean here - the SudokuP property applies to grids, but groups are sets of transformations (permutations) applied to gids. What is the "group with just the additional property"?

Cheers!

[blue]

Hi Mathimagics,

... but I do note that your F transformation is not a Sudoku-group element, so by definition grids x and F(x) are "essentially different" wrt the Sudoku group, are they not?

Almost always, the answer is yes ... "essentially different".
There are some SudokuP grids, x, that have automorphisms of the form F * g, where g is in both groups.
For those, we have

Code: Select all

x = (F g) x

F x = F ((F g) x)
    = (F (F g)) x
    = ((F F) g) x
    = g x

Cheers.

[Mathimagics]

In fact F(x) generally might not even be a valid Sudoku grid ...

It only works for SudokuP grids ... fascinating stuff!

[Mathimagics]

I initially thought that F, when restricted to SudokuP grids, and applied to puzzles, might give an "essentially equivalent" puzzle in the accepted sense, ie: matching solver complexity.

The only way I have of comparing SudokuP puzzles is to count the the iterations (= recursions) taken by my DLX-P solver, but this seems a reasonably reliable basis for comparison.

This is an example:

Code: Select all

         P                           F(P)
 1 . 2 | 3 . . | . . .     1 . 2 | . . . | . . .
 . . . | 4 . . | . . .     3 . . | 4 . . | . . .
 . . . | . . . | 5 . .     . . . | . . . | 5 . .
 ---------------------     ---------------------
 . 6 . | . 7 . | . . .     . 6 . | . 7 . | . . .
 . 7 . | . . . | . . .     . 7 . | . . . | . . .
 . . . | . . . | . 2 .     . . . | . . . | . 2 .
 ---------------------     ---------------------
 . 8 . | . . . | . . .     . 8 . | . . . | . . .
 . . . | . . . | . . .     . . . | . . . | . . .
 . . . | . . . | 8 . .     . . . | . . . | 8 . .


You can see that under F only one clue has changed position, but its fairly evident that these are not the same puzzles by any stretch, and this is confirmed by the solver, which takes longer for F(P) (559 iterations), than P (338 iterations).

It might also be the case that F(P) is not well-formed in some instances. That is, there may be unique-solution SudokuP puzzles P, where F(P) doesn't have a unique solution. I haven't actually found such a case yet, but it seems entirely possible.

[eleven]

I am missing a 3 in r2c1. So you cannot know, if the solution grids are equivalent too.
Are they (have no SudokuP solver) ?
[Added:]If there is a SudokuP grid with a SudokuP automorphism using the transformation F, wouldn't that be a sudoku automorphism too ?
Hm, ok, if a transformation preserves the sudoku property for a special puzzle, this is no automorphism.
F just preserves the position property, not the sudoku property (in general).
So i think, that a SudokuP grid transformed with F (alone) is not SudokuP equivalent.

[Mathimagics]

My apologies! I didn't make it clear that Solution[F(P)] = F(Solution[P]):

Code: Select all

      Soln[P]                    Soln[F(P)]
 1 2 3 | 9 7 5 | 4 8 6      1 2 3 | 4 5 6 | 7 8 9
 4 5 6 | 1 8 3 | 9 2 7      9 7 5 | 1 8 3 | 4 2 6
 7 8 9 | 4 2 6 | 1 5 3      4 8 6 | 9 2 7 | 1 5 3
 ---------------------      ---------------------
 8 1 4 | 5 3 7 | 6 9 2      8 1 4 | 6 9 5 | 2 3 7
 6 9 5 | 8 1 2 | 7 3 4      5 3 7 | 8 1 2 | 6 9 4
 2 3 7 | 6 9 4 | 8 1 5      6 9 2 | 7 3 4 | 8 1 5
 ---------------------      ---------------------
 3 6 1 | 7 5 9 | 2 4 8      3 6 1 | 5 7 8 | 9 4 2
 5 7 8 | 2 4 1 | 3 6 9      7 5 9 | 2 4 1 | 3 6 8
 9 4 2 | 3 6 8 | 5 7 1      2 4 8 | 3 6 9 | 5 7 1


I am missing a 3 in r2c1.

Not sure what you mean here ...

So you cannot know, if the solution grids are equivalent too. Are they (have no SudokuP solver)?

Not equivalent, see above.

BTW, it is a trivial matter to modify a DLX solver that solves Sudoku's to make it a SudokuP solver. We just add the constraints for "every position different" to the standard constraints for the rows, columns and blocks.

If there is a SudokuP grid with a SudokuP automorphism using the transformation F, wouldn't that be a sudoku automorphism too?
Hm, ok, if a transformation preserves the sudoku property for a special puzzle, this is no automorphism.
F just preserves the position property, not the sudoku property (in general).

This example should demonstrate that, while SudokuP's can have automorphism under F (although they seem to be rare), this does not imply an automorphism under the Sudoku Symmetry Group:

Code: Select all

           x                        F(x)
 1 2 3 | 7 5 9 | 4 8 6      1 2 3 | 4 5 6 | 7 8 9
 4 5 6 | 1 8 3 | 7 9 2      7 5 9 | 1 8 3 | 4 6 2
 7 8 9 | 4 6 2 | 1 5 3      4 8 6 | 7 9 2 | 1 5 3
 ---------------------      ---------------------
 3 1 2 | 5 9 4 | 8 6 7      3 1 2 | 5 6 7 | 8 9 4
 5 6 7 | 2 1 8 | 9 3 4      5 9 4 | 2 1 8 | 6 3 7
 8 9 4 | 6 3 7 | 5 2 1      8 6 7 | 9 3 4 | 5 2 1
 ---------------------      ---------------------
 2 3 8 | 9 7 1 | 6 4 5      2 3 8 | 6 4 1 | 9 7 5
 6 4 1 | 8 2 5 | 3 7 9      9 7 1 | 8 2 5 | 3 4 6
 9 7 5 | 3 4 6 | 2 1 8      6 4 5 | 3 7 9 | 2 1 8


Invariance via label mapping corresponding to row 1.

And by my reckoning, grid x above has automorphism group 1, ie no non-trivial automorphism ...

So i think, that a SudokuP grid transformed with F (alone) is not SudokuP equivalent.

Right. Even the F-automorphic cases show non-equivalence (to my solver) for certain clue-sets.

[blue]

This is (meant to be) a sort of "grand response" to the previous two posts.
[ Correction: By now, it's the two "previous, but for one" posts ]

I initially thought that F, when restricted to SudokuP grids, and applied to puzzles, might give an "essentially equivalent" puzzle in the accepted sense, ie: matching solver complexity.

The only way I have of comparing SudokuP puzzles is to count the the iterations (= recursions) taken by my DLX-P solver, but this seems a reasonably reliable basis for comparison.

This is an example:

Code: Select all

         P                           F(P)
 1 . 2 | 3 . . | . . .     1 . 2 | . . . | . . .
 . . . | 4 . . | . . .     3 . . | 4 . . | . . .
 . . . | . . . | 5 . .     . . . | . . . | 5 . .
 ---------------------     ---------------------
 . 6 . | . 7 . | . . .     . 6 . | . 7 . | . . .
 . 7 . | . . . | . . .     . 7 . | . . . | . . .
 . . . | . . . | . 2 .     . . . | . . . | . 2 .
 ---------------------     ---------------------
 . 8 . | . . . | . . .     . 8 . | . . . | . . .
 . . . | . . . | . . .     . . . | . . . | . . .
 . . . | . . . | 8 . .     . . . | . . . | 8 . .


You can see that under F only one clue has changed position, but its fairly evident that these are not the same puzzles by any stretch, and this is confirmed by the solver, which takes longer for F(P) (559 iterations), than P (338 iterations)

I'm fairly confident that you would see a similar things happening with the itteration counts, if you transformed the puzzle in one of the "more acceptable" ways ... e.g.:

• swap bands 1&3
• reflect the puzzle across one of the diagonals
• ...

------

It might also be the case that F(P) is not well-formed in some instances. That is, there may be unique-solution SudokuP puzzles P, where F(P) doesn't have a unique solution. I haven't actually found such a case yet, but it seems entirely possible.

To cut this short, that situation is impossible.
In the end, it turns out that P has (SudokuP) solutions S1,S2,...Sn ... all distinct
... if and only if F(P) has (SudokuP) solutions F(S1),F(S2),...,F(Sn) ... all distinct.

------

[Added:]If there is a SudokuP grid with a SudokuP automorphism using the transformation F, wouldn't that be a sudoku automorphism too ?

Short answer: No, since calling it a sudoku automorphism, would imply that it is one of the transformations that maps all (valid) sudoku grids, to (valid) sudoku grids. (For F, that isn't the case).

------

F just preserves the position property, not the sudoku property (in general).

That isn't quite right ... and there's more to the story than that.

Earlier, I wrote, of F, that:

It maps rows to boxes, boxes to rows, columns to box positions, and box positions to columns.

From that, we have that:

• F maps grids satisfying the "row property", to grids satisfying the "box property"
• F maps grids satisfying the "columns property", to grids satisfying the "position property"
• F maps grids satisfying the "box property", to grids satisfying the "row property"
• F maps grids satisfying the "position property", to grids satisfying the "column property"

It follows that F maps grids satisfying all 4 properties -- SudokuP grids -- to grids satisfying all 4 properties.
For Sudoku grids, though ... that are only required to satisfy the "row, column and box" properties ... it maps them to grids satisfying "row, position, and box" properties ... with no guarantee that the "column" property is satisfied, and so no guarantee that the result is also a Sudoku grid.

------

So i think, that a SudokuP grid transformed with F (alone) is not SudokuP equivalent.

I'm confused about that statement:

We say that two Sudoku grids are "Sudoku equivalent", if one can be transformed into the other, using a transformation that maps every Sudoku grid, to a Sudoku grid.
Since F maps every SudokuP grid, to a SudokuP grid, it seems to follow that we should say that x and F(x) are "SudokuP equivalent", whenever 'x' is a bonifide SudokuP grid.
(I hope I'm "beating a dead horse", at this point).

------

Back to tbe beginning:

I initially thought that F, when restricted to SudokuP grids, and applied to puzzles, might give an "essentially equivalent" puzzle in the accepted sense, ie: matching solver complexity.

It's true, in the end ... provided the solver is "sufficiently sophisticated".

• For a puzzle, P, that is solvable using "singles", F(P) is still solvable using "singles", as long as the solver is accounting for "box position"/"pset" singles.
• Techniques like "Claiming"/"Pointing" Sets, need to be extended to cover situations such as the one where candidates for a digit in a row are confined to a "pset", and (as a result) candidates for 'd', that are in the pset, but not in the row ... can be eliminated.
• More generally: the "houses" concept, needs to be extended to include "psets", and the idea that "one candidate can 'see' another candidate", needs to be extnded to allow "seeing" through a "pset".

Best Regards to All,
Blue.

[Mathimagics]

Thanks blue for that concise summary!

Regarding apparent-solver complexity comparisons, that's a very good point.

The DLX algorithm iterations are not immutable - the key operation is "select the column with the least number of 1's" and search that sub-tree.

When there are several candidates (which is probably most of the time), then if the usual "take the first" column option is used, this will result in slightly different search-trees for otherwise equivalent puzzles.

Cheers to you too!

[eleven]

Sorry blue, for posting things without having time to read carefully.
Thanks for your patience.

[Mathimagics]

While I think of it, I noticed this oddity wrt SudokuP's:

In a file of 49,148 x 17-clue Sudoku puzzles, not one of the solution grids has SudokuP property.

No real surpise there, but as far as I can tell, very few of them are even isomorphic with a SudokuP. Interesting?

[EDIT] Have checked 1300 so far, and found just 9 cases with 1 or 2 SudokuP isomorphisms, no more ...