The New Sudoku Players' Forum

[claudiarabia]

It has occurred to me that Sudoku (playing, studying) involves a large number of concepts from combinatorics.
.....I have done an example of such an essay based on the concept of SYMMETRY.... underlying the concepts of a symmetric puzzle. ...Comments and feedback welcomed.. Gordon

I can add a class of symmetry. It's the diagonal band repetition symmetry:

Code: Select all

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

Claudia

[ronk]

What is the difference between automorphism and isomophism?

There are theoretically 9!*2*(6^8) = 1,218,998,108,160 different puzzles in one equivalency class (set), and so each puzzle is said to be isomorphic to every other puzzle in the set.

But all of those 1.2+ trillion puzzles are not necessarily unique. Is that when the "automorphic" term applies? If so, how small does the set need to be for the automorphic term to be used correctly

TIA, Ron

[edit: replaced 9 with 9! as JPF noted]

[JPF]

There are theoretically 9*2*(6^8) = 30,233,088 different puzzles in one equivalency class (set), and so each puzzle is said to be isomorphic to every other puzzle in the set.

There are a maximum of 9!*2*(6^8) = 1,218,998,108,160 grids in each equivalency class.

In average, the number of grids per equivalency class is :
6,670,903,752,021,072,936,960/ 5,472,730,538=1,218,935,174,261

JPF

[ravel]

There are a maximum of 9!*2*(6^8) = 1,218,998,108,160 grids in each equivalency class.

In average, the number of grids per equivalency class is :
6,670,903,752,021,072,936,960/ 5,472,730,538=1,218,935,174,261

From these numbers, can you also estimate, how high (better low) the probability is, that a random grid has symmetrical properties (only those keep the average number under the maximum, dont they) ?
[Added: over the thumb less than 1 in 10000, but more than 1 in 12000]

[Red Ed]

What is the difference between automorphism and isomophism?

An isomorphism is a structure-preserving map between two objects. An automorphism is an isomorphism whose two objects are the same thing.

Two grids are isomorphic iff you can get from one to the other by the usual set of validity-preserving transformations.

One grid is "automorphic" (probably a mild abuse of terminology) iff there's a nontrivial validity-preserving transformation that leaves it unchanged. Counting automorphic grids is what gives you the 5472730538 number.

It's funny that this thread has come to the top of the pile again because I was just thinking how useful -- and easy -- it would be to build a catalogue of all essentially-different automorphic solution grids, since that would give us a rich source of solution grids that exhibit certain "extreme" properties.

[JPF]

So, can we say that every grid is isomorphic with an automorphic grid ?

i.e. :
For every G , there exist G', t, t' ( t'#e) such that :
t(G) = G'
t'(G') = G'

G, G' are grids ; t, t' are transformations.

JPF

[Red Ed]

So, can we say that every grid is isomorphic with an automorphic grid ?

No! - because then every grid would itself be automorphic.

( Proof: Suppose G is a grid isomorphic to H, so G = fH for some transformation f. Suppose also that H is automorphic, so H = hH for some non-trivial transformation h. Then G = fhf'G (f' is f-inverse) ... which means that G is automorphic. )

[ravel]

Probably this is not the right thread for saying this, because it is about symmetries we can find for the givens of sudokus, not about those in solution grids. But i want to take the opportunity to ask, what the right academic words are for what i mean (looking to wikipedia was more confusing than clarifying).

There are well known transformations for sudokus (including solution grids), that keep all essential properties, some say, their mathematical equivalence, some call such puzzles equivalent, some isomorph.

They also keep all symmetry properties (when there are some) in a mathematical sense, though you might not spot them at the first glance.
E.g. if you have a diagonally symmetrical grid, you can transform it non trivially (where non trivial means, that the transformed puzzle does not have each cell with the same number at the same place again), by mirroring and exchanging the numbers in mirrored cells, to the same grid, where 9 cells (on the diagonal) keep on the same place. The same is true for all equivalent grids. For all of them there exists a transformation (maybe a combination of basic transformations), that maps them to the same grid with exactly 9 cells at the same place and 36 pairs with exchanged numbers.
This is one sample for what i called "the puzzle maps to itself".
I suppose this is an automorphism.

Beside of the diagonally symmetry we know the 180 degree rotational symmetry (where only 1 cell keeps its place), the threefolded symmetry over 3 chunks (samples by Mauricio) or triples of boxes in the way arranged, that we recently saw by gurth (no cell keps on its place), further 90 degree symmetry (again with 1 cell unchanged). Are there more kinds of symmetry ?
All equivalent grids to those keep this property, just the cells are distributed in another way.

Now iff a grid has such symmetry properties, some of the equivalent grids are equal, for diagonal symmetry there are always pairs of them, for threefold puzzles triples and so on. Therefore the size of the equivalence class is only half or third etc. of the maximum size. This is, what my quick calculation for the number of grids with symmetry properties is based on.

So i hope someone with better background will let me know, if it is correct, what i said here, and if there are better terms for that.

[coloin]

Counting automorphic grids is what gives you the 5472730538 number.

This number was the number of essentially different grids.... the existence of automorphic grids reduced the total number of grids ?......

When a cell C is mutable in a puzzle P, the mutation gives a different puzzle P'.
but, it can happen that P and P' are equivalent.
Here is an example seen above from the Nick's list

Code: Select all

 1 . . | . 5 . | . . .
 . . . | 3 . . | . 6 .
 . . 8 | . . . | 2 . .
-------+-------+-------
 . 3 . | . . 2 | . . .
 9 . . | . 1 . | . . 5
 . . . | 6 . . | . 7 .
-------+-------+-------
 . . 5 | . . . | 1 . .
 . 6 . | . . 7 | . . .
 . . . | . 9 . | . . 8      puzzle P :


has one mutable cell r5c5 = 1->8

The resulting puzzle P' :

 1 . . | . 5 . | . . .
 . . . | 3 . . | . 6 .
 . . 8 | . . . | 2 . .
-------+-------+-------
 . 3 . | . . 2 | . . .
 9 . . | . 8 . | . . 5
 . . . | 6 . . | . 7 .
-------+-------+-------
 . . 5 | . . . | 1 . .
 . 6 . | . . 7 | . . .
 . . . | . 9 . | . . 8    is equivalent to P

ravel wrote

Code: Select all

Both are normalized to
....5.6..4....9....8......12....4......8...9...5.1.3...6......5...2...4...1.3....
by gsf's program.

ronk wrote:

Code: Select all

Swap digits 1 and 8
Swap digits 3 and 7
Reflect diagonally

This is an automorphic grid then ?

How many are there [roughly]?

C

[Red Ed]

Counting automorphic grids is what gives you the 5472730538 number.

This number was the number of essentially different grids.... the existence of automorphic grids meant that there were slightly less essentially different grids, I think is what you mean....

Yes, that's the number of essentially-different grids, a.k.a. the number of isomorphism classes. It's calculated using Burnside's lemma, which for each group operation g (or, to save effort, conjugacy class [g]) counts the number of grids fixed by that operation, i.e. the number of grids that are automorphic with respect to g. That's what I meant.

The example you gave isn't an automorphic grid, it's an isomorphic pair.

This is a nice automorphic grid:

Code: Select all

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

If you rotate it by 180 degrees and map digit d -> 10-d then you get back where you started.

[ravel]

For the samples by Mauricio see here and here, for gurth's one here.

[JPF]

So, can we say that every grid is isomorphic with an automorphic grid ?

No! - because then every grid would itself be automorphic.

( Proof: Suppose G is a grid isomorphic to H, so G = fH for some transformation f. Suppose also that H is automorphic, so H = hH for some non-trivial transformation h. Then G = fhf'G (f' is f-inverse) ... which means that G is automorphic. )

... except if fhf'=e or fh=f

I was a bit confused by :

One grid is "automorphic" (probably a mild abuse of terminology) iff there's a nontrivial validity-preserving transformation that leaves it unchanged. Counting automorphic grids is what gives you the 5472730538 number.

It gave me the impression that each of the 5472730538 equivalency classes had (at least) one automorphic grid.

When a cell C is mutable in a puzzle P, the mutation gives a different puzzle P'.
but, it can happen that P and P' are equivalent.

This is an automorphic grid then ?

The puzzles P and P' are such that P'=tP ; but P'#P
In addition, P and P' are puzzles (subgrids), not grids.
P has one solution G.
Then P' has one solution G' such that G'=tG ; G'#G

Probably this is not the right thread for saying this, because it is about symmetries we can find for the givens of sudokus, not about those in solution grids. But i want to take the opportunity to ask, what the right academic words are for what i mean (looking to wikipedia was more confusing than clarifying).

I fully agree with that.

JPF

[Red Ed]

So, can we say that every grid is isomorphic with an automorphic grid ?

No! - because then every grid would itself be automorphic.

( Proof: Suppose G is a grid isomorphic to H, so G = fH for some transformation f. Suppose also that H is automorphic, so H = hH for some non-trivial transformation h. Then G = fhf'G (f' is f-inverse) ... which means that G is automorphic. )

... except if fhf'=e or fh=f

... which can't happen, because then h would be the identity (which I ruled out, above).

The puzzles P and P' are such that P'=tP ; but P'#P
In addition, P and P' are puzzles (subgrids), not grids.
P has one solution G.
Then P' has one solution G' such that G'=tG ; G'#G

I honestly don't mean to be rude, but ... so what? This is just recapping what has already been said about iso- (not auto-) morphisms.

[JPF]

... which can't happen, because then h would be the identity (which I ruled out, above).

right ; fhf'#e was the missing part of your proof.

so what? This is just recapping what has already been said about iso- (not auto-) morphisms.

right.
I apologize if I was the only one to not fully understand

...isn't an automorphic grid, it's an isomorphic pair

Now,
How many essentially-different grids are automorphic ?

JPF

[ravel]

Now,
How many essentially-different grids are automorphic ?

The difference between all (different) grids and the number of nonequivalent grids multiplied with the maximum number of isomorphic grids (i.e. grids in an equivalence class) is 3.4^17. So these must have been fallen away due to automorphisms.

For a 2-fold (e.g. rotational or diagonal symmetrical) grid we only have half of the (max. number of) grids in the class, i.e. 6^11 fall away.

So if all automorphic grids would be twofold, we had 565087 of them. This is an upper bound, because when a grid is n-fold, then 1.2^12*(n-1)/n fall away and we have less of them (if all in average would be 3-fold, it gives a number of 423815).