Sudoku Symmetry - Formalized

Everything about Sudoku that doesn't fit in one of the other sections

Re: Sudoku Symmetry - Formalized

Postby claudiarabia » Sun Aug 27, 2006 9:49 am

gfroyle wrote: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
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby ronk » Tue Jan 16, 2007 12:43 pm

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]
Last edited by ronk on Tue Jan 16, 2007 11:02 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby JPF » Tue Jan 16, 2007 2:52 pm

ronk wrote: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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby ravel » Tue Jan 16, 2007 3:22 pm

JPF wrote: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]
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Red Ed » Tue Jan 16, 2007 5:38 pm

ronk wrote: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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Tue Jan 16, 2007 6:51 pm

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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Tue Jan 16, 2007 7:53 pm

JPF wrote: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. )
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby ravel » Tue Jan 16, 2007 9:12 pm

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.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby coloin » Tue Jan 16, 2007 10:38 pm

Red Ed wrote: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 ?......

JPF wrote: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
Last edited by coloin on Tue Jan 16, 2007 7:00 pm, edited 1 time in total.
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby Red Ed » Tue Jan 16, 2007 10:57 pm

coloin wrote:
Red Ed wrote: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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby ravel » Tue Jan 16, 2007 11:46 pm

For the samples by Mauricio see here and here, for gurth's one here.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby JPF » Wed Jan 17, 2007 1:32 am

Red Ed wrote:
JPF wrote: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 :
Red Ed wrote: 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.

coloin wrote:
JPF wrote: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

ravel wrote: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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby Red Ed » Wed Jan 17, 2007 8:39 am

JPF wrote:
Red Ed wrote:
JPF wrote: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).

JPF wrote: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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby JPF » Wed Jan 17, 2007 1:52 pm

Red Ed wrote:... 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.

Red Ed wrote: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
what you wrote: ...isn't an automorphic grid, it's an isomorphic pair

Now,
How many essentially-different grids are automorphic ?

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby ravel » Wed Jan 17, 2007 6:55 pm

JPF wrote: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).
ravel
 
Posts: 998
Joined: 21 February 2006

PreviousNext

Return to General