About Red Ed's Sudoku symmetry group

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

Postby udosuk » Thu Jan 22, 2009 11:59 pm

eleven wrote:MR+MD imply HT+RS+CS (and trivially MC):
...

Excellent observation!:)

I just don't have time to look at it in details right now:( , absorbed too much on work and watching tennis.:D

I suppose the next step you will investigate why MR+MD+JR implies QT, DM etc...:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby eleven » Fri Jan 23, 2009 4:45 am

Thanks for a response.

My next step is to verify, if its really true, what i claimed. In the moment i have some doubts - the proof is missing, that if a grid has those symmetries, there always must be an equivalent grid, where they all are in "normalized" form.
Otherwise its either incomplete or wrong, what i wrote.
eleven
 
Posts: 3149
Joined: 10 February 2008

Postby Red Ed » Fri Jan 23, 2009 6:18 pm

I'll try to find time this evening to give you a list that shows, for each of the 122 non-trivial aut groups, the symmetry classes contained within. That will settle once and for all the question of which symmetries imply which others. It's just a question of writing a function to put individual symmetries in canonical form, which isn't hard.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Red Ed » Sat Jan 24, 2009 5:33 am

As promised:
EDIT: introduced new second column counting the number of grids, up to isomorphism, with the given automorphism group.

Code: Select all
  2  23201 574139682621478395839256147742391568198564723356782419267913854485627931913845276 1 37
  2 257606 413526987572189643968743125341978562297615438856432719725861394689354271134297856 1 134
  2 267642 691375428752184693483269157319857246246931875578642319827496531964513782135728964 1 79
  3     57 395782164287146539641593728716254983954318672832679415428967351579831246163425897 1 10
  3    193 587632419326491785914758623275984361843516972169327548732169854691845237458273196 1 30
  3    326 682753491195842763347169285834527619579631824261498357958376142726914538413285976 1 9
  3    658 497836152251479683638152947863521479974368215125947836749683521512794368386215794 1 8
  3    683 682715439537924681419386572796438125823561794145297863961842357278153946354679218 1 22
  3    729 483529671671843592952761438716438925529617384834952167295176843167384259348295716 1 28
  3    841 829153647754869231163724598231547986598631472647298315376482159415976823982315764 1 25
  3    847 361542987792638145458971362924857631583164729617293854839415276246789513175326498 1 7
  3   3002 246395178137864295589172463758216934613489752924537681861943527375621849492758316 1 32
  4    112 318476295692583741754921386469317528237658419185294637526849173873162954941735862 1 37 79
  4    525 137295486582476139496138752268759314953641278741823695615384927379562841824917563 1 79 86
  4   2189 384792516972561843561384927297648135135927468648135279453816792729453681816279354 1 79 134
  6      1 894362715312875496756941832569784321173526984248139657625498173487213569931657248 1 10 37
  6      3 421638759963175284785249631247316895196852473538497162814963527352784916679521348 1 22 37
  6      4 618273954237954681954681237186732495372549168549816723723168549491325876865497312 1 30 134
  6      7 958163742632794518714582936593826471276431895841957263185349627369275184427618359 1 10 79
  6     10 538179246249856731617243985853791624924568173761432598372685419486917352195324867 1 9 134
  6     14 376915428851247963429683175537196284962438751184752639715369842248571396693824517 1 10 37 40
  6     16 619543782453827169872916543728169435345278691961354278196782354287435916534691827 1 8 134
  6     18 356948217918276354274315986829157643635894172147632895791523468563489721482761539 1 22 37 43
  6     18 526189473437256981819347562698473215743521698251968734985734126162895347374612859 1 32 134
  6     19 184673259957812643632945781579128436341756892826439517213564978795281364468397125 1 30 134 143
  6     21 346759812579812436182436759957128364634597128218364597721945683493681275865273941 1 30 79
  6     24 561743298374982561892615473256839147437156829189427356625398714918274635743561982 1 28 134
  6     28 176298435435761892829354167287916354354872619691543278712435986968127543543689721 1 25 134
  6     39 789126453365498127412357698621984735873561249594273816956712384237849561148635972 1 28 134 144
  6     42 395426718284371695716589234872695341453718926169234587947152863638947152521863479 1 9 79
  6     63 892643715346715982175982634928436157634571829751298346289364571517829463463157298 1 28 79
  6     70 198624375425713689763598142542137896637859214819246753254371968376985421981462537 1 22 79
  6     72 965471823471328956328965417714832569832659174596147238147283695283596741659714382 1 8 134 135
  6     76 215978643647325198389641572764253819532819467198467235476532981851794326923186754 1 25 134 145
  6     91 793256841146798352258143697625814973379625418814379526562481739431967285987532164 1 25 79
  6    100 483956271596721483271843596148537629359268147627419358862394715735182964914675832 1 8 79
  6    110 795428163248361795163975824957284631824136957631597482586743219419652378372819546 1 7 79
  6    149 284967351713852469695134278371528946569341827428679135842796513137285694956413782 1 32 134 142
  6    262 162347958859261734437589162985126347743895216621473589598612473374958621216734895 1 32 79
  8     29 723468195815392764649571283372986451964157832581234679237649518158723946496815327 1 37 79 86 134
  9      1 163495287824371695759286341275618934396542718481937562948723156632154879517869423 1 10 25 32
  9      1 293816754547923618186574293618239475932457186754168329861392547475681932329745861 1 8 26
  9      1 394687125867251493521934768786493512439125876152768349248579631613842957975316284 1 7 8 9 10
  9      1 472369518869157423153482967986571234315824679247693185724936851698715342531248796 1 9 30 32
  9      1 698723154542981376713654829869237541371546298254819763986372415425198637137465982 1 10 28 30 32
  9      1 796328415124657389853491672485916723612573894379284156568139247231745968947862531 1 8 32
  9      1 812375469964812573537649218128496357375128946496537182281753694753964821649281735 1 8 29
  9      1 953678421781425693246391578369187245812549736475236189698714352524963817137852964 1 22 25
  9      2 925463718781295634364718529259871463178634295643529871896142357412357986537986142 1 7 28 30
  9      3 256843719917652438348197652562438971483971265179526843791265384834719526625384197 1 8 28 30 32
  9      3 651983274974215638238647951382764519749521386516398742897452163123876495465139827 1 8 25 32
  9      3 691573482357824691482916357925487136748361925136259748813795264264138579579642813 1 22 25 32
  9      3 814956327732148695695327481327569814956481273148273956261835749583794162479612538 1 7 9
  9      6 872391546693754182451268973918546327745132698236879415129683754387415269564927831 1 22 32
  9      7 254761839937584126681392457728436591346915278195827643872643915519278364463159782 1 7 30 32
  9      7 279186534354729861816345297695471328482963715731852649567214983948637152123598476 1 9 28 32
 12      1 568472391392186574417359826186297435724835619935614287853741962641923758279568143 1 10 37 40 79
 12      5 627934185458612793193587426974251368286473519315869274532798641841326957769145832 1 22 37 43 79
 12      6 945827163276513984138694257481769532762351849359482671893246715627135498514978326 1 30 79 134 143
 12     14 936182475281745639574639812369854721712396584845271396157428963693517248428963157 1 28 79 134 144
 12     21 367915482421683579958274613736591248142368957895427361673159824214836795589742136 1 32 79 134 142
 12     22 712635498563498127849127635356849712127356849498271563984712356635984271271563984 1 8 79 134 135
 12     23 346891275527643981891725436752364198918257643463918527189572364634189752275436819 1 25 79 134 145
 18      1 148295736763481259952763418529637841637814925481952673394578162216349587875126394 1 7 9 79
 18      1 254367198168294357397158264643581729982673415571942836726815943419736582835429671 1 8 28 134 135
 18      1 315269478672841395498537612186495723753612984924378156261984537547123869839756241 1 22 25 79
 18      1 378125964192364758465798123736489512514632879829571436643917285251843697987256341 1 10 22 37 40
 18      1 467521839125938467983764251398476125746215398251389746674152983512893674839647512 1 8 31 79
 18      1 648327519529816743713945628851634297362791485974582136435269871287153964196478352 1 8 32 134 135
 18      1 672385194481296375593174286257963841349851762168742953914638527735429618826517439 1 8 27 79
 18      1 932158647851647239746239158518476392293581764674923581329764815467815923185392476 1 8 30 134 135
 18      1 948671253253849176617523894325716948761498532894235761489352617532167489176984325 1 8 9 134 135
 18      2 215876934786934512394125768867512349943687125152493687521349876678251493439768251 1 7 8 9 10 79
 18      2 319675248576248913842913675281397564654821397937564821795486132123759486468132759 1 8 29 79
 18      2 427618593359247168168953274742186359816539427935472816593861742681724935274395681 1 8 26 79
 18      2 439825761671349258285617493716258934943761582528493176394176825852934617167582349 1 8 32 79
 18      2 684312975372569814951478263519624387723185496846793521195836742237941658468257139 1 7 25 28 79
 18      2 687124359395876421412953678243795186168432597579681234724368915951247863836519742 1 10 28 30 32 79
 18      2 738541926659287431412639578241963785973158264865724319597812643386475192124396857 1 22 25 134 145
 18      2 867342195519687324432159678741938562398526417256471983975213846123864759684795231 1 9 30 32 134 142
 18      2 913746825786512439542983167169837254435129678827465391351678942698254713274391586 1 8 22 79
 18      3 176839524893524167542167839725483916961752483438916752387295641614378295259641378 1 8 28 30 32 79
 18      3 264719853918453762357862419725698134831524697496137528149375286672981345583246971 1 8 25 32 79
 18      3 264857913578193246931426587346578129192634758785219364857941632623785491419362875 1 22 32 134 142
 18      3 371964825694852371258317946749526183183749652526183497965238714417695238832471569 1 10 23 79
 18      3 825746193931825674674931258467319825193258467582467319258674931319582746746193582 1 8 28 30 32 134 135 142 143 144
 18      3 872951364159364278463278951518493726394726815627815493941632587785149632236587149 1 10 25 32 79
 18      3 936782415874591623251364987369827541748915362512643798693278154125436879487159236 1 22 25 32 134 142
 18      4 567214839934658721128397465641725983385469172279831546853142697792586314416973258 1 8 24 79
 18      6 695314827473628195821597463956431278734862951218759634167983542542176389389245716 1 9 28 32 79
 18      6 924183675831567924675492831319875246758624319246931758487216593162359487593748162 1 8 25 32 134 135 142 145
 18      6 984653271563127489721498563872549316316782945495361827149836752257914638638275194 1 22 32 79
 18      7 791624538426835791538197426162953847847261359359748162974516283615382974283479615 1 22 25 32 79
 18      8 927436581158729346463518927832965714695174832714382695346851279581297463279643158 1 7 30 32 79
 27      1 246891573819753624735264981167329845392485716458176239624537198981642357573918462 1 7 8 9 10 28 30 32
 27      1 857612439394578261261439857578261943439785126126943578785126394612394785943857612 1 8 22 25 32
 36      1 168742935742395618395168472953274186274681359816539247539427861681953724427816593 1 8 30 79 134 135 143
 36      1 316895724249371685857264931631958472984712563725643198478126359592437816163589247 1 22 25 79 134 145
 36      1 341786925286915734975342861437891652168254379529673148754168293892437516613529487 1 10 22 37 40 43 79
 36      1 542318697968742153173956824726435918381679542459281736834197265215863479697524381 1 22 25 79 86
 36      1 598263741172459386634817925813945672457326198269781534941632857325178469786594213 1 8 25 79 134 135 145
 36      1 763482159149537268258691743315824976926375814874916325597248631681753492432169587 1 8 28 79 134 135 144
 36      2 581273964732946851469158723953617482176824395248395176395761248824539617617482539 1 7 9 79 86
 36      2 718326495569784123243591678695847231432915786187263954871632549324159867956478312 1 22 32 79 134 142
 36      2 793846521165372894428519367937684215651237948284951673842195736516723489379468152 1 8 32 79 134 135 142
 36      3 374162958895437216621589743753894162948621537216375489162943875587216394439758621 1 22 25 32 79 134 142 145
 54      1 361485297972163458845927361729631845458279136613854729297316584136548972584792613 1 8 9 28 30 32 134 135 142 143 144
 54      1 374968512986251473152347896869125347521734689743896251215473968698512734437689125 1 8 24 25 31 32 79
 54      1 428395176953176842761842395219587634634219587587634219145968723896723451372451968 1 8 9 28 30 32 134 135
 54      1 516348792483972561729651438874129356291536847365487219657814923932765184148293675 1 10 22 25 32 79
 54      1 768214935249635781153789264836172459927456813415893672684321597392567148571948326 1 10 22 25 32 37 40 43
 54      1 825194763637258941419376582541639278963827154782415396196783425378542619254961837 1 8 24 25 27 32 79
 54      1 879542316635187294421963758754621983296835147318479562167298435582314679943756821 1 8 22 25 32 134 135 142 145
 54      2 638297451451368792279541638386729514514836927792154386863972145145683279927415863 1 8 22 25 32 79
 54      2 915687243423915786876234195234591678768423519159768324687342951591876432342159867 1 7 8 9 10 25 28 30 32 79
 72      1 782145369394768125516923847927814536651239478843576912165392784238457691479681253 1 22 25 37 43 79 86 134 145
 72      1 841569327659372418732481596327956841596148732418237659273814965965723184184695273 1 8 10 37 40 79 86 134 135
108      1 569342718284719635371685942942137856635428197718956423856294371423871569197563284 1 10 22 25 32 37 40 43 79
108      1 742369518961258437853147629427936185619825374538714296385471962196582743274693851 1 8 22 25 32 79 134 135 142 145
108      1 983674512674251839251983746398125674467398251125467983839746125512839467746512398 1 8 10 28 30 32 79 134 135 142 143 144
162      1 514382967823697541697145328451238679769514283382769415976451832238976154145823796 1 8 9 22 25 30 32 134 135 142 145
648      1 639821754281745396475369812754936128812574963396182547128457639963218475547693281 1 8 10 22 25 32 37 40 43 79 86 134 135 142 145
Last edited by Red Ed on Mon Jan 26, 2009 2:51 am, edited 1 time in total.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Red Ed » Sat Jan 24, 2009 5:38 am

eleven wrote:And (thanks to StrmCkr) the MC grid has all the 26 symmetries - its just a matter of finding them.
Not true - see last line in previous post.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby udosuk » Sat Jan 24, 2009 5:43 pm

Red Ed wrote:
eleven wrote:And (thanks to StrmCkr) the MC grid has all the 26 symmetries - its just a matter of finding them.
Not true - see last line in previous post.

That was due to a misunderstanding earlier. eleven thought another grid (the MI grid) was equivalent to the MC grid. But basic instinct should tell us that no grid can have all 26 symmetries (e.g. full row and mini column are not compatible).

Thanks for the great program results... Now all the hard data is there, just waiting for some time & effort from us to formulate them nicely. But I'm too engaged to tennis now (e.g. King Roger just pulled off a major escape from 0-2 down moments ago).:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Red Ed » Sat Jan 24, 2009 7:23 pm

King Roger? Pah. Nothing but a jester in the court of King Andy!:D

(Uh, better stay on topic ... isomorphism automorphism blah blah blah ...)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby StrmCkr » Sat Jan 24, 2009 8:18 pm

I think i sorted out the confusion between
how i approach it and you guys as well.

i wasnt concerned about the actuall physical location of each digit

instead i removed that varation, and went with grouped sets.

they way i view the symmetry is by locating a repeating pattern of a specific group of individual digits.

(so that those digits arangement is irrelevant as they can be swaped around anyway)

i noticed patterns of orination via the clues location.
with assinging them as a group: say 1,2,3 is group abc:
then replace all digits of 1 or 2 or 3 with abc:

this gives 27 cell as abc:
Repeated to form 3 groups of 3 digits: (or 3 sets of 27)

abc:
def:
ghj:

which gave me several types of symmetries: (shown in more graphical detail on my page then what i mean here)

-note *3 means per set

3 cells of a set on a row/column in same house *3 -

3 cells of a sets spanning one per box on same row/column *3

2 cells of a set in 1 box on same row/box + 1 in another.*3

the rest are combinations of the above:

if you have any questions feel free to ask on my page to keep elevens nice and tidy

... i hope that clarifies things a bit...
strmckr.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1430
Joined: 05 September 2006

Postby Red Ed » Sat Jan 24, 2009 9:03 pm

udosuk wrote:Now all the hard data is there, just waiting for some time & effort from us to formulate them nicely.

We can help each other out here.

Here's what I would need from you:
  • You give me a list of "nice" symmetries. By "nice", I mean simple stuff like rotation, transposition, band/row cycling, flipping the whole grid horizontally or vertically; that sort of thing. The list must be sufficient to generate (by combining) any possible symmetry. It doesn't matter if there are some redundant symmetries in there -- in fact, it should be expected that there'll be quite a bit of redundancy. eleven's list from the first post would be a good starting point:
    B..cyclically move the bands downwards (B123->B231)
    S..cyclically move the stacks rightwards (S123->S231)
    Bx..exchange B1 and B3 (B123->B321)
    Sx..exchange S1 and S3 (S123->S321)
    R1 (R2, R3)..cyclically move the rows in band 1(2,3) downwards (r123->r231)
    C1 (C2, C3)..cyclically move the columns in stack 1 (2.3) rightwards (c123->c231)
    R..cyclically move the rows in all bands downwards (R1R2R3 or r123456789->r231564897)
    C..cyclically move the colums in all stacks rightwards (C1C2C3 or r123456789->r231564897)
    Rx..invert the order (exchange the first and 3rd) of the rows in all bands (r123456789->r321654987)
    Sx..invert the order (exchange the first and 3rd) of the colums in all stacks (c123456789->c321654987)
    D..mirror at the main diagonal from r1c1 to r9c9 (r123456789<->c123456789)
    D2..mirror at the subdiagonal from r1c9 to r9c1 (r123456789<->c987654321)
    • You tell me the cost of each of those "nice" symmetries. The cost is a positive integer. Really nice symmetries have cost 1. Slightly less nice ones have cost up to, oh I don't know, 5?
    • You give me a combination cost. This tells me how bad it is to write a symmetry as a combination of two others.
    In return, I could express each of the 122 aut groups as a list of generator symmetries such that the overall cost of the each list was minimal.

    For example, if we decided that (T)ransposition had cost 2, (Q)uarter turn had cost 1, (B)and cycling had cost 3, and the composition cost was 5, then the set of generators {T,TB,Q} would have cost (2) + (2+5+3) + (1) = 13, whereas the set of generators {T,TBQ} would have cost (2) + (2+5+3+5+1) = 18, which is higher because of the extra composition.

    Interested? Or do you want to go ahead and do this manually yourself?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby eleven » Sun Jan 25, 2009 6:50 am

Many thanks for the list, Red Ed.

So my doubts were justified, and you saved me the time trying to prove something, which is not true. I had a look at the grid with classe 7+8+9+10 symmetries, which disproved, what i claimed here.
With a few transformations it looks like this.
Code: Select all
 MR: 149 253 687               MD 165 297 348
 +-------+-------+-------+     +-------+-------+-------+
 | 1 4 9 | 2 5 3 | 6 8 7 |     | 1 4 9 | 2 5 3 | 6 7 8 |
 | 7 6 8 | 4 9 1 | 3 2 5 |     | 7 6 8 | 4 9 1 | 3 5 2 |
 | 3 2 5 | 6 8 7 | 9 1 4 |     | 3 2 5 | 6 8 7 | 9 4 1 |
 +-------+-------+-------+     +-------+-------+-------+
 | 9 1 4 | 5 3 2 | 8 7 6 |     | 9 1 4 | 5 3 2 | 8 6 7 |
 | 8 7 6 | 9 1 4 | 2 5 3 |     | 8 7 6 | 9 1 4 | 2 3 5 |
 | 5 3 2 | 8 7 6 | 1 4 9 |     | 5 3 2 | 8 7 6 | 1 9 4 |
 +-------+-------+-------+     +-------+-------+-------+
 | 4 9 1 | 7 6 8 | 5 3 2 |     | 4 9 1 | 7 6 8 | 5 2 3 |
 | 6 8 7 | 3 2 5 | 4 9 1 |     | 6 8 7 | 3 2 5 | 4 1 9 |
 | 2 5 3 | 1 4 9 | 7 6 8 |     | 2 5 3 | 1 4 9 | 7 8 6 |
 +-------+-------+-------+     +-------+-------+-------+

The left one has MR (class 8), the right one MD (class 10) symmetry. Since you get from one to the other by swapping columns 89, there cannot be an equivalent grid, which has both symmetries in "normalized" form (as described by the prototypes C and CR). But my "proof" had premised that.

I have to hurry now, so i cant answer your last post in the moment.
eleven
 
Posts: 3149
Joined: 10 February 2008

Postby JPF » Sun Jan 25, 2009 9:13 am

Thanks Red Ed
Red Ed wrote:My calculations go a step further and actually find the symmetry group in each case. So, for example, where gsf - and kjellfp before him - shows a count of 548449 e-d grids that each have exactly two (one non-trivial + the identity) automorphisms, I have shown that the corresponding 548449 symmetry groups boil down to "essentially" just three types. (Actually that is obvious from the table of conjugacy classes; but other parts of the table are not obvious.)

For people interested in all the e-d automorphic grids , here is a link kindly given by gsf via PM
gsf wrote:
JPF wrote:Would it possible to get your list of grids with #aut>1 ?
download the file
http://www.research.att.com/~gsf/sudoku/data/grid-a2.dat.gz
its a 55Mi file of 560151 grids gzip compressed to 9.6Mi
it took ~5 hours to scan through the list of all grids to generate the data
the data is
Code: Select all
grid # automorphisms band index
where index is the minlex index in the list of all grids counting from 1
if you have success downloading and decompressing then feel
free to post the above and your notes on the player's forum

Red Ed wrote:But it's a good prod: I ought to write out the number of e-d grids for each symmetry group. That's just a case of running the program again (fairly quick) and maintaining a counter for each symmetry group.

I have one more question :
How many automorphisms are there in each of the 26 conjugacy classes ?

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

Postby Red Ed » Sun Jan 25, 2009 4:20 pm

JPF wrote:How many automorphisms are there in each of the 26 conjugacy classes ?

I think you mean isomorphisms, not automorphisms. Anyway, does column 2 of this table answer your question?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby eleven » Mon Jan 26, 2009 12:01 am

Another old question i had, is answered by the new list:
eleven wrote:DBS is equivalent to a combination of D and BS (equivalence in the sense, that if a puzzle has DBS symmetry, it also has both D and BS symmetry and vice versa). I dont have a proof for the "vice versa" part.

There cant be a proof for the other direction, because there is a group, which has D (or DM, class 37) and BS (class 22, now called JD) symmetry, but not DBS (class 43, which we called DM+JD). So the naming DM+JD is all but perfect.

The reason is the same i mentioned above. If a grid has the 2 symmetries and there is an equivalent grid, where both are in normalized form, it also has the symmetry with a number 6-cycle. If there is no equivalent grid, where both are in normalized form, there is no other symmetry forced.

Here are examples for the combinations of Sticks and Jumping-Row symmetries:

Both in normalized form:
Code: Select all
 +-------+-------+-------+
 | 1 9 6 | 2 7 4 | 3 8 5 |
 | 2 7 5 | 3 8 6 | 1 9 4 |
 | 3 8 4 | 1 9 5 | 2 7 6 |
 +-------+-------+-------+
 | 5 1 8 | 6 2 9 | 4 3 7 |
 | 6 3 9 | 4 1 7 | 5 2 8 |
 | 4 2 7 | 5 3 8 | 6 1 9 |
 +-------+-------+-------+
 | 9 6 1 | 7 4 2 | 8 5 3 |
 | 8 4 2 | 9 5 3 | 7 6 1 |
 | 7 5 3 | 8 6 1 | 9 4 2 |
 +-------+-------+-------+
Sticks (1)(2)(3)(47)(58)(69)
JR (123)(456)(789)
Sticks-JR (132)(495768)


Cant be both in normalized form:
Code: Select all
                                  after DM, c56           
 +-------+-------+-------+    +-------+-------+-------+
 | 6 2 8 | 1 9 4 | 5 7 3 |    | 6 1 3 | 9 4 7 | 8 2 5 |
 | 1 9 4 | 3 7 5 | 6 2 8 |    | 2 9 7 | 1 8 5 | 4 6 3 |
 | 3 7 5 | 6 2 8 | 1 9 4 |    | 8 4 5 | 6 2 3 | 9 1 7 |
 +-------+-------+-------+    +-------+-------+-------+
 | 9 1 6 | 4 8 2 | 3 5 7 |    | 1 3 6 | 4 7 9 | 2 5 8 |
 | 7 5 3 | 9 1 6 | 4 8 2 |    | 9 7 2 | 8 5 1 | 6 3 4 |
 | 4 8 2 | 7 5 3 | 9 1 6 |    | 4 5 8 | 2 3 6 | 1 7 9 |
 +-------+-------+-------+    +-------+-------+-------+
 | 8 4 9 | 2 6 1 | 7 3 5 |    | 5 6 1 | 3 9 4 | 7 8 2 |
 | 2 6 1 | 5 3 7 | 8 4 9 |    | 7 2 9 | 5 1 8 | 3 4 6 |
 | 5 3 7 | 8 4 9 | 2 6 1 |    | 3 8 4 | 7 6 2 | 5 9 1 |
 +-------+-------+-------+    +-------+-------+-------+
Sticks (1)(24)(37)(5)(69)(8)      JR (142)(375)(698)       



Red Ed, please could you explain, what the class size and the "number of grids fixed up to relabelling" mean (how are they calculated). Is there any relation between those numbers and the number of non-equivalent (e-d/essentially different) grids, that have this symmetry ? I still would be interested in this number for each symmetry.

If i understood you right with giving nicer symmetry descriptions - the class numbers are ok for me as they are (clearer than our names). What i would like to have is, what udosuk did for the 26 classes: Give an example grid, where the symmetry is in "normalized" form, i.e. easy to spot. As we saw (first for the MC grid), for some symmetries this would need more than one grid.
eleven
 
Posts: 3149
Joined: 10 February 2008

Postby JPF » Mon Jan 26, 2009 2:46 am

Just trying to understand, like others, what you are doing so easily:)

My question was irrelevant as : in a conjugacy class, if it exists one isomorphism h which fixs a grid x, then all the isomorphisms of this class fix at least one grid.
k and h conjugate => k=fhf' => kf=fh
and hx=x => k(fx)=fx

I understand now that out of 2x 6^8=3359232 isomorphisms, there are only 311 408 automorphisms.
Now you consider the 560151 automorphic grids and the set H={h1,h2,...} of their associated group of automorphisms.
In this set H, you have defined an equivalence relation.
h1~h2 if they are the automorphism groups of 2 isomorphic grids.

There are 122 classes.
Does it mean that there are 1134 groups of automorphisms ?

Not clear to me how you go from there to the nice symmetries...

eleven, I hope i'm not creating the mess in your own questions.

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

Postby Red Ed » Mon Jan 26, 2009 4:24 am

eleven wrote:Red Ed, please could you explain, what the class size ...
The set of group elements h'gh, for g fixed and h ranging over the whole group (of 3359232 elements), is called the conjugacy class of g. The class size is the number of different values that h'gh can take. For example, if g is the identity, e, then h'gh = e always and so the class size is 1. Two symmetries are in the same class iff they are "essentially" the same, in the sense explained by JPF above. For example, cycling the rows in band 1 is "essentially" the same as cycling the columns in stack 2 (say).

... and the "number of grids fixed up to relabelling" mean (how are they calculated).
That's the number of solution grids, with top row = 123456789, that are either totally unchanged by application of the given symmetry, or are effectively just relabelled by application of that symmetry. I counted them like this.

Is there any relation between those numbers and the number of non-equivalent (e-d/essentially different) grids, that have this symmetry ? I still would be interested in this number for each symmetry.
OK, I'll try to get round to it tonight.
EDIT: done; see edited post above.
Last edited by Red Ed on Mon Jan 26, 2009 2:53 am, edited 1 time in total.
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General