About Red Ed's Sudoku symmetry group

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

Postby Red Ed » Wed Feb 11, 2009 3:02 am

eleven wrote:It was a bit surprising for me, that Red Ed had listed <D2S> as generator of the first group with class 43 (D+BS), where i had expected SBD.
D2S is shorter; that's why.

As equation: (x~y, if there is a t with txt'=y, here y=SD2, x=DBS, t=FvS, t'=(FvS)'=S'Fv=SSFv)
FvS(DBS)SSFv = FvSDBFv = FvSDDSDFv = FvSSDFv = FvSSFvFvDFv = SD2
FhD2(SD2)D2Fh = FhD2SFh = DS = DDBD = BD
D(DS)D = SD = DBDD = DB
Nice.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Red Ed » Sat Feb 14, 2009 5:09 am

I wondered what different abstract groups were represented in the set of 122 non-trivial automorphism groups. The results are below. Each subset of aut groups has a heading which is GAP's "StructureDescription" of the aut group. Most of the StructureDescriptions uniquely identify the abstract group, but some of the semidirect products, like (C3 x C3) : C2, do not (since the homomorphism, which is an aspect of the semidirect product, is elided). Nevertheless, I have verified that the aut groups for the entries under each heading are all isomorphic.

It would be illuminating, though I expect beyond my enthusiasm, to rework the aut group generators (the <A,B,C,...> lists) so that they had the same form under each heading and you could say for example "transposition in this aut group is equivalent, in the abstract, to half-turn in that aut group". But I sense even before seeing the reaction to this post that genuine interest in that may be limited.

C2
2 157694823824173695963582174549238716716945238238716549691457382482361957375829461 1 134 <BxCx>
2 319246875246875913578319624752693148691428357483157296827531469135964782964782531 1 79 <H>
2 457826913162953847983471625274685139819237456635194278726548391548319762391762584 1 37 <D>

C3
3 246187539137259486589436217758943621924618753613725948861572394375894162492361875 1 32 <RS>
3 275849163843165279169273845587326914326914587914587326732691458691458732458732691 1 30 <R2R3S>
3 347965821659218347182473965596821473473596182218734596931687254864352719725149638 1 7 <R3C>
3 359782146278146593614593782761254938945318627823679451482967315136425879597831264 1 10 <RC>
3 497863125251497638638125974863512497974386251125974863749638512512749386386251749 1 8 <C>
3 587946231246531987931287546654193728793628154128754693469875312875312469312469875 1 28 <R3S>
3 682439517537681429419572683823794165145863792796125834278946351354218976961357248 1 22 <BS>
3 718564392564239718392718645631852974849376521275491863427683159153947286986125437 1 9 <R2R3C>
3 829153764754869123163724859231547698598631247647298531376482915415976382982315476 1 25 <S>

C4
4 592137468674582193831496725146953287957268341328741659483615972719824536265379814 1 79 86 <Q>

C2 x C2
4 279135486684279351153468279348516927516927843927843615792681534435792168861354792 1 79 134 <H,BxCx>
4 964285371732194685581376249813952467296417538457863912378549126625731894149628753 1 37 79 <H,D>

C6
6 251897463674532918398164752746325189523981647189746325932618574467253891815479236 1 25 134 145 <S,BxCx>
6 276435819819276435435819276342198567567342198198567342653724981981653724724981653 1 32 134 142 <BxCx,RS>
6 471965328965832471328471965714596832596283147832147659147659283659328714283714596 1 8 134 135 <C,RxSx>
6 519736284742581639386249751691357842257814396834692517963175428175428963428963175 1 10 37 40 <DR>
6 563712489189453762742689153356271948298346571471598326635127894824935617917864235 1 22 37 43 <D2S>
6 689523417714689325325417986196274853853196274472358691267931548548762139931845762 1 30 134 143 <R3BxSCx>
6 734568129861927435952413876143295687295786341687341592416872953378659214529134768 1 28 134 144 <BxCx,R2S>

S3
6 124386795369751248587492613835974126742163859691528437976215384253847961418639572 1 22 37 <D2,BS>
6 136452978452897136897361452245789361613245897978136245524978613789613524361524789 1 8 79 <H,C>
6 147256389829437516356189247714625938982743651635918724298561473561374892473892165 1 28 134 <RxSx,R3S>
6 198426357763895124425317698819642735637958241542731869981264573376589412254173986 1 22 79 <H,BS>
6 256189347347256198189347256521968473473521869968473521612895734734612985895734612 1 32 134 <BxCx,BC>
6 426953187371842956589167342947386521152479638863215794695728413234691875718534269 1 9 79 <H,R1R3C>
6 619345872453728619872619453196287534287534196534196287961453728345872961728961345 1 8 134 <C,BxCx>
6 652789143134652987789134562218475396475396218396218475927561834561843729843927651 1 9 134 <FhR2xCx,R1R3C>
6 732859641148236957659741832273985164814623795965174283396517428481362579527498316 1 25 134 <S,RxSx>
6 759284613284613975136759284568437129491526738327198456842361597613975842975842361 1 7 79 <H,R2C>
6 795821463821463795463795821954638217237914658618257934182346579346579182579182346 1 30 79 <H,R1R3S>
6 876419352549732186312856479954681237681273945237945618495168723168327594723594861 1 30 134 <RxSx,R2R3S>
6 894326715312857496756914832569748321248193657173562984625489173487231569931675248 1 10 37 <D2,RC>
6 973526418416978523528413976265184739184739265739265184897352641341697852652841397 1 25 79 <H,S>
6 976254813253816974814973256138542769542769138769138542681497325397625481425381697 1 28 79 <H,R2S>
6 976841532842536971531972846325719468769428315418365729184253697653197284297684153 1 32 79 <H,RS>
6 985631247623947815741825639158493726396752481472186953814579362539268174267314598 1 10 79 <H,RC>

D8
8 648732951751694832932851647469273185185469273273185469896327514517946328324518796 1 37 79 86 134 <D,BxCx>

C9
9 128375964375964281496128375812496753964537128537281496281649537649753812753812649 1 8 29 <R2R3C1S>
9 618475932932186754754329861861547293475932186329861547293754618547618329186293475 1 8 26 <R3C1S>

C3 x C3
9 187234956625798413349561872432659781978143265516827394263975148894316527751482639 1 10 25 32 <S,RC>
9 259643781178925364643781259925178643781364925364259178896537412412896537537412896 1 7 28 30 <R2S,R3C>
9 265719843971438652384652197526971438197843526438265971652197384719384265843526719 1 8 28 30 32 <C,C3B>
9 358741269926835417417692835692417583741358926835926741174583692583269174269174358 1 7 8 9 10 <C,C3R>
9 549837126126549837837126549481765293293481765765293481314972658972658314658314972 1 9 30 32 <R3RS,R2R3C>
9 643917258985234671127568493364791825598423167712856349436179582859342716271685934 1 22 25 32 <S,BC>
9 675283149914567328832491756769825413341976582258134697183752964527649831496318275 1 10 28 30 32 <RC,R3S>
9 692357814573814926148269735926735481357481269814692573269573148735148692481926357 1 8 25 32 <B,C>
9 695174823482369517731258946567412389948736251123895674279681435354927168816543792 1 9 28 32 <R3S,RSC>
9 718436259925871364643592187364925718871643592259187436436718925592364871187259643 1 8 32 <C,RS>
9 782915643364782591159436782827159364436827915591643827245398176973261458618574239 1 7 30 32 <RS,R3C>
9 814956327732148695695327481327569814956481273148273956261835749583794162479612538 1 7 9 <C3R,R3CC>
9 872456193693812457451793862236145978918237645745968231129574386387629514564381729 1 22 32 <BC,RS>
9 953768214781245936246931785475326891369817452812459367137582649524693178698174523 1 22 25 <B,S>

D12
12 127984635356271984498356127712849563563712849849563712271498356635127498984635271 1 8 79 134 135 <H,C,RxSx>
12 358479621429651378671328459783294516294516783516783294867932145942165837135847962 1 25 79 134 145 <H,S,BxCx>
12 518349267642875913379126548836512794427698135951734826795263481164987352283451679 1 22 37 43 79 <D,D2S>
12 716283459529146873483759216295837164837461592164592738648375921952614387371928645 1 28 79 134 144 <H,BxCx,R2S>
12 817692354354817692692354817178265439439178265265439178781546923923781546546923781 1 32 79 134 142 <H,RS,BxCx>
12 856219734219437658734658912921865473568374129473921865192743586347586291685192347 1 30 79 134 143 <SH,R3RxSx>
12 861345927247169385359827164685931742174286539923754816538692471416578293792413658 1 10 37 40 79 <D2,DR>

D18
18 125398467398746251746251398839467512467125983251983746674512839512839674983674125 1 8 31 79 <H,C1RS>
18 137528496825649731469173285974381652318256974652794318596417823741832569283965147 1 10 23 79 <H,R1C1BS>
18 471385269853926471692714853926853714714269538538147692147538926385692147269471385 1 8 29 79 <H,R1R3C1S>
18 519623478784195623623478195195236784478519362236784951951362847847951236362847519 1 8 24 79 <H,C1BS>
18 654231798798546312231798546312987465879654231546312987465123879987465123123879654 1 8 27 79 <H,C1S>
18 681593427274168359935274168816742593742935681359681274427816935593427816168359742 1 8 26 79 <H,R2C1S>

C3 x C6
18 237154698986372154415986237372541986869723541154869372723415869698237415541698723 1 8 25 32 134 135 142 145 <B,C,RxSx>
18 825746931674931582931825746582467193467319258193258674258674319746193825319582467 1 8 28 30 32 134 135 142 143 144 <C,RxSx,C2B>

C3 x S3
18 421657938389421765576893421214389576657214893938765214142938657765142389893576142 1 8 32 134 135 <C,RxSx,RS>
18 642319785785642319319785642463921857857463921921857463236194578578236194194578236 1 22 32 134 142 <BxCx,BC,RS>
18 695321748487956213321748695569132874874569132132874569748213956213695487956487321 1 8 28 134 135 <C,RxSx,R3S>
18 746829513315647928829513746197438265562791834438265197681954372273186459954372681 1 22 25 134 145 <B,S,BxCx>
18 786951243951243786243786951174625839839174625625839174597468312468312597312597468 1 9 30 32 134 142 <BxCx,R1R2SC>
18 815923764476581392923764815647239158239158647158647239764392581392815476581476923 1 8 30 134 135 <C,RxSx,R2R3S>
18 873215946291634785564978132415362897637849521928751463346197258789526314152483679 1 10 22 37 40 <D2C,BS>
18 963287415847195623215463987396728541784519362521346798639872154478951236152634879 1 22 25 32 134 142 <S,RxSx,BC>
18 984253671235176849671894523716532498849761235352948716167325984498617352523489167 1 8 9 134 135 <RxSx,C1C2R>

(C3 x C3) : C2
18 158349726934672815267581493782195364519436278643827951326758149875914632491263587 1 10 25 32 79 <H,S,RC>
18 259184367418736592736925184587349621162857943394261875673592418925418736841673259 1 7 9 79 <H,C2R,CHR2>
18 315692478498375612672418395186954723753126984924783156839567241261849537547231869 1 22 25 79 <H,S,B>
18 354716298167982543298354716639875421875421639421639875543167982716298354982543167 1 7 25 28 79 <H,S,R2C>
18 536712498271894356984635172613278549827459631495163287368527914752941863149386725 1 22 32 79 <H,BC,RS>
18 547183926329645781861279435754318692932564178186927543475831269293456817618792354 1 22 25 32 79 <H,S,BC>
18 615293874293748561487561329156932487932874615748615293561329748329487156874156932 1 8 25 32 79 <H,C,B>
18 643297518972518364851643972596382741417965823238174659185436297364729185729851436 1 7 30 32 79 <H,RS,R2C>
18 749236158158749623623581497974362815815497362362815749497623581581974236236158974 1 8 28 30 32 79 <C,H,C2B>
18 768124395539876412241953687472368951683519724195247836324795168816432579957681243 1 10 28 30 32 79 <H,RC,R2S>
18 876349512934125687125687493251934876768512934349768125687493251493251768512876349 1 7 8 9 10 79 <H,C,C2R>
18 934761582582934617176582934761493258258617493493258176825349761617825349349176825 1 8 32 79 <H,C,RS>
18 956341827734682195218579463671938542425167389893254716569413278347826951182795634 1 9 28 32 79 <H,R2S,RSC>
18 975362184184597623362184975759623841418759362623841759597236418841975236236418597 1 8 22 79 <H,C,BS>

C3 x C3 x C3
27 695287134287413695413695728341956287569872341728134956872341569134569872956728413 1 7 8 9 10 28 30 32 <C,C2B,C3R>
27 857612943394578126261439785578261394439785612126943857785126439943857261612394578 1 8 22 25 32 <B,C,RS>

S3 x S3
36 178459623659132487423687195817945362965213748342768519781594236596321874234876951 1 22 32 79 134 142 <H,RxSx,BC,RS>
36 279145683638297154145683279927514368863729415514368927792451836386972541451836792 1 22 25 32 79 134 142 145 <H,S,BxCx,BC>
36 294371865361895274875264391752643918613958742948712653487126539136589427529437186 1 22 25 79 134 145 <H,S,B,RxSx>
36 516482973824739165973516482651248397248397651397651248165824739482973516739165824 1 8 25 79 134 135 145 <H,C,S,RxSx>
36 629471835835629471471835629962358714714962358358714962296147583583296147147583296 1 8 32 79 134 135 142 <H,C,RxSx,RS>
36 712398564645127983398564712456839271839271456271456839127983645564712398983645127 1 8 28 79 134 135 144 <H,C,BxCx,R2S>
36 952786413743915862816342759625891374397254681184673295239168547478529136561437928 1 10 22 37 40 43 79 <D2S,DR>
36 953274816274681539816539427168742395395168742742395168427816953681953274539427681 1 8 30 79 134 135 143 <C,SH,R3RxSx>

(C3 x C3) : C4
36 698427135452183679713569842549812763831796524276354981384971256967245318125638497 1 22 25 79 86 <Q',S>
36 716284593428593716593671428372469851649158372851327649167842935284935167935716284 1 7 9 79 86 <Q,C2R>

C3 x C3 x S3
54 159372468684159237723846159915723684846915372237468915591237846468591723372684591 1 8 22 25 32 134 135 142 145 <B,C,RxSx,RS>
54 297361845458972613361845297729613584845729361136458729972136458584297136613584972 1 8 9 28 30 32 134 135 142 143 144 <C,RxSx,C3BR>
54 768395412249871536153624987415762398836549271927183654392418765571236849684957123 1 10 22 25 32 37 40 43 <B,DR>

(C3 x C9) : C2
54 512347689473968512896125473251734968347896251689512347125473896734689125968251734 1 8 24 25 31 32 79 <H,B,C1RS>
54 864579123231486957579123648486957312123648795957312864648795231312864579795231486 1 8 24 25 27 32 79 <H,B,C1S>

(C3 x C3 x C3) : C2
54 165348729834972516297651483748129365912536874653487291329765148576814932481293657 1 10 22 25 32 79 <H,S,B,RC>
54 297415836368729154541683972729541683836972415154368297972154368683297541415836729 1 8 22 25 32 79 <H,C,B,RS>
54 951678432432951867867243951786432195195786243243519786324195678678324519519867324 1 7 8 9 10 25 28 30 32 79 <C,H,B,C2R>

((C3 x C3) : C3) : C2
54 318562749974831256562749318183625497749318562625497183497256831256183974831974625 1 8 9 28 30 32 134 135 <RxSx,R3S,C2C3C3R>

(S3 x S3) : C2
72 814237695695148723723956814569372481372481569481569372148723956956814237237695148 1 8 10 37 40 79 86 134 135 <D2,C,BxCx>
72 827541963165329748943867521438675219516932874279418635794186352651293487382754196 1 22 25 37 43 79 86 134 145 <D2,S,RxSx>

S3 x ((C3 x C3) : C2)
108 659178243824365917731492586178243659365917824492586731243659178917824365586731492 1 10 22 25 32 37 40 43 79 <B,D2,CH>
108 674983251251674983983251674125398467398467125467125398746839512512746839839512746 1 8 10 28 30 32 79 134 135 142 143 144 <R,C,H,BxCx,R2S>
108 312564897897312564564897312123456789789123456456789123231645978978231645645978231 1 8 22 25 32 79 134 135 142 145 <H,C,B,RxSx,RS>

C3 x (((C3 x C3) : C3) : C2)
162 514238697823769451697514238451823769382976145769451823145382976238697514976145382 1 8 9 22 25 30 32 134 135 142 145 <B,S,RxSx,C1C3C3R>

(((C3 x C3) : C2) x ((C3 x C3) : C2)) : C2
648 639281475281475639475639281396812754812754396754396812963128547128547963547963128 1 8 10 22 25 32 37 40 43 79 86 134 135 142 145 <D2,C,S,BxCx>
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby eleven » Sun Feb 15, 2009 5:17 pm

Red Ed wrote:But I sense even before seeing the reaction to this post that genuine interest in that may be limited.
This thread was started out of the interest in the very concrete question, what symmetries exist, that can lead to puzzles, where we can use the symmetry for solving. It turned out then, that its also very interesting (at least for udosuk and me) to look at the symmetries alone, which grids can have, and play around with them.
Here we found ourselves in group theory, which i think, is a rather dry subject, when you start with some abstract definition of a group (isnt that, what is done in university lectures ?). So i am happy to have learned something about it this way.
In the moment i want to make a pause (and it seems udosuk either).
With your help we could go a long way, so thanks again.
eleven
 
Posts: 1535
Joined: 10 February 2008

Re: About Red Ed's Sudoku symmetry group

Postby eleven » Sun May 23, 2010 8:55 pm

This (minimal 38 clue) puzzle popped up in my high clue search and was discussed in the lost "High clue tamagotchis" thread. RW had noticed an "almost" digit symmetry. It turned out, that nevertheless you may apply the solution techniques for an automorph 180° symmetric puzzle.
btw the wikipedia definition i read for an automorph puzzle is incomplete, it only says that an automorph puzzle has an automorph solution. Fact is, that additionally for every given the symmetrical cell(s) also must be given.

Code: Select all
 +-------+-------+-------+
 | . . 5 | . . . | 6 . 1 |
 | 3 1 . | . . . | . 7 5 |
 | 7 9 6 | 1 . 5 | . 4 3 |
 +-------+-------+-------+
 | . . . | . . 3 | 4 6 . |
 | 6 . . | 2 . 9 | . . 7 |
 | . 7 3 | 4 . . | . . . |
 +-------+-------+-------+
 | 4 3 . | 5 . 1 | 7 2 6 |
 | 1 6 . | . . . | . 5 4 |
 | 5 . 7 | . . . | 1 . . |
 +-------+-------+-------+ SER 7.7


Take the solution. Then do a 180° rotation and digit changes 15,29,34,67. That gives a valid solution grid with this sub-puzzle, which is the original puzzle despite of the marked cells, a so called U4 (unavoidable set of size 4)
Code: Select all
 +-------+-------+-------+
 | . . 5 | . . . | 6 . 1 |
 | 3 1 . | . . . | . 7 5 |
 | 7 9 6 |*5 .*1 | . 4 3 |
 +-------+-------+-------+
 | . . . | . . 3 | 4 6 . |
 | 6 . . | 2 . 9 | . . 7 |
 | . 7 3 | 4 . . | . . . |
 +-------+-------+-------+
 | 4 3 . |*1 .*5 | 7 2 6 |
 | 1 6 . | . . . | . 5 4 |
 | 5 . 7 | . . . | 1 . . |
 +-------+-------+-------+

Now swap the 1's and 5's in this U4. This must lead to a valid solution grid either (thats the unique rectangle trick, the swap still leaves 1 and 5 in all rows/colums/boxes according to the sudoku rules).

And it must be a solution either to the original puzzle (simply because it contains it).

So you have 2 solutions now for the original puzzle. If they are not identical, the puzzle is not unique. They are identical exactly, when all unsolved cells have digit symmetry.
That allows you to use this property. Since the center cell must be digit symmetrical to itself, it only can be 8 - and the puzzle is solved.


A U4, where all numbers are given, does not change anything to the rest of the puzzle, when the digits are swapped. For a solver its exactly the same puzzle with 2 different solutions (each row/column/box with the U4 cells has both numbers as givens).
Thus RW proposed to denote such a puzzle as
Code: Select all
 +-------+---------+-------+
 | . . 5 | .  .  . | 6 . 1 |
 | 3 1 . | .  .  . | . 7 5 |
 | 7 9 6 |15  . 51 | . 4 3 |
 +-------+---------+-------+
 | . . . | .  .  3 | 4 6 . |
 | 6 . . | 2  .  9 | . . 7 |
 | . 7 3 | 4  .  . | . . . |
 +-------+---------+-------+
 | 4 3 . |51  . 15 | 7 2 6 |
 | 1 6 . | .  .  . | . 5 4 |
 | 5 . 7 | .  .  . | 1 . . |
 +-------+--------+-------+

meaning that it does not matter, if the givens are 1551 or 5115.

Mauricio has generated some nice digit symmetric puzzles containing such U4's. Hopefully he has a backup and will repost them here.
eleven
 
Posts: 1535
Joined: 10 February 2008

Re: About Red Ed's Sudoku symmetry group

Postby Mauricio » Mon Jun 21, 2010 12:33 am

eleven wrote:Mauricio has generated some nice digit symmetric puzzles containing such U4's. Hopefully he has a backup and will repost them here.

Not exactly a backup...
Code: Select all
+-------+-------+-------+
| . . 1 | . . 2 | . . 3 |
| . 4 . | . . 3 | . . 2 |
| 2 . . | 5 6 . | 7 1 . |
+-------+-------+-------+
| . . 5 | 8 . . | 9 . . |
| . . 7 | . 4 . | . . . |
| 9 1 . | . . 5 | . . . |
+-------+-------+-------+
| . . 6 | 3 . . | 4 . . |
| . . 2 | . . . | . 8 . |
| 1 9 . | . . . | . . 5 |
+-------+-------+-------+

Code: Select all
+-------+-------+-------+
| . . . | . . . | . . 1 |
| . . 2 | . . 3 | . 4 . |
| . 5 . | 4 6 . | . . . |
+-------+-------+-------+
| . . 1 | 3 . . | 7 . . |
| . . 7 | . 8 . | 1 . . |
| . 3 . | . . . | . 2 5 |
+-------+-------+-------+
| . . . | 6 4 . | 3 . . |
| . 7 . | . . 5 | . 9 . |
| 6 . . | . . 2 | . . 8 |
+-------+-------+-------+

Code: Select all
+-------+-------+-------+
| . . . | . 1 . | . . 2 |
| . . 3 | . . 4 | 5 . . |
| 6 . . | 5 . . | . 4 . |
+-------+-------+-------+
| . 5 . | . . 7 | . 8 . |
| 4 . . | . . . | . . 9 |
| . 8 . | 6 . . | . 5 . |
+-------+-------+-------+
| . 9 . | . . 8 | . . 7 |
| . . 8 | 9 . . | 3 . . |
| 1 . . | . 2 . | . . . |
+-------+-------+-------+
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Re: About Red Ed's Sudoku symmetry group

Postby dukuso » Mon Jun 21, 2010 8:22 am

I've been converting the sudoku to a graph of order 117 with the same automorphism-group
(su2gra.exe)
and then using Nauty to print generators of the group.
Anyone been doing this too ?

The disadvantage was that I need ~10K to store such a graph, presumably this could
be improved.

do we have a list with the ~500000 sudokus with nontrivial automorphism group and their group-type,generators ?
put it on gsf's memory-card
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: About Red Ed's Sudoku symmetry group

Postby gsf » Mon Jun 21, 2010 1:22 pm

dukuso wrote:I've been converting the sudoku to a graph of order 117 with the same automorphism-group
(su2gra.exe)
and then using Nauty to print generators of the group.
Anyone been doing this too ?

The disadvantage was that I need ~10K to store such a graph, presumably this could
be improved.

do we have a list with the ~500000 sudokus with nontrivial automorphism group and their group-type,generators ?
put it on gsf's memory-card

memory card REAMDE wrote:the catalog of essentially different sudoku grids

This 8Gib mini-SD disk contains the catalog of essentially different
9x9 sudoku grids. The grids take just over 5Gib and are in the sudz
directory, labeled by 3 digit band number. The bands are the 416
essentially different bands (3 9-cell rows.) The numbering is the
ordinal based on minlex (row-order minimal lexicographic) ascending
sort, starting from 001. The file data/band.info contains the number
of grids per band. Because of minlex ordering, some of the later bands
have no member grids.

The data was generated by the gsf sudoku solver. A windows and linux
x86 executable are in the bin directory. Use the --man option for more
information, and ask questions on the Sudoku Players' Forum.

sudz data is compressed, and requires just over 8 bits per grid. The
gsf solver writes and reads sudz data. The data self-identifies, so
just present it to the solver as if it were a regular text file. The
data for each grid contains the number of automorphisms for that grid.
The file data/a2.sudz contains all of the grids with a non-trivial
automorphism.

The file data/band.md5 contains the md5 sum of each band for integrity
checking.

The data is being distributed by mini-SD because for most of us in 2010
its a pain to (a) find a provider that gives good, easy, fast and free
access to that much data (b) find the patience to babysit a long
download on a home machine.

The distribution is "pay it forward". You have recieved the data
because the previous recipent has paid the postage to send it to you.
By receiving it you agree do the same for the next recipient.

2010-06-16 gsf NJ USA

so data/a2.sudz is a compressed minlex order list of all grids with non-trivial automorphism (1909399 bytes)
this command line (g == gsf solver command name) lists and counts the number of grids with
#automorphisms > 100, the final format -Ff... lists the count totals and elapsed time
Code: Select all
g -f%v%,#%,%#An -e '(%#An)>100' -Ff%#an/%#in data/a2.sudz

since its so small you can also download a2.sudz

can you list the nauty automorphism generators for a few grids?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: About Red Ed's Sudoku symmetry group

Postby dukuso » Tue Jun 22, 2010 5:15 am

I forgot a link to Nauty :
http://cs.anu.edu.au/~bdm/nauty/
user guide in pdf here : cs.anu.edu.au/~bdm/nauty/nug.pdf

e.g. "most canonical" has automorphism-group of size 648,
given as subgroup of the permutation group of 117 numbers
with the 4 generators:


(1 18)(2 9)(3 54)(4 72)(5 63)(6 27)(7 45)(8 36)(10 20)(12 56)(13 74)(14 65)
(15 29)(16 47)(17 38)(21 55)(22 73)(23 64)(24 28)(25 46)(26 37)(30 60)
(31 78)(32 69)(34 51)(35 42)(39 62)(40 80)(41 71)(43 53)(48 61)(49 79)
(50 70)(58 75)(59 66)(67 77)(82 87)(83 84)(85 89)(90 99)(91 101)(92 100)
(93 105)(94 107)(95 106)(96 102)(97 104)(98 103)(109 114)(110 111)
(112 116)
(3 6)(4 7)(5 8)(9 18)(10 19)(11 20)(12 24)(13 25)(14 26)(15 21)(16 22)(17 23)
(30 33)(31 34)(32 35)(36 45)(37 46)(38 47)(39 51)(40 52)(41 53)(42 48)
(43 49)(44 50)(57 60)(58 61)(59 62)(63 72)(64 73)(65 74)(66 78)(67 79)
(68 80)(69 75)(70 76)(71 77)(82 83)(85 86)(88 89)(91 92)(94 95)(97 98)
(102 105)(103 106)(104 107)(109 110)(112 113)(115 116)
(0 1 2)(3 4 5)(6 7 8)(9 10 11)(12 13 14)(15 16 17)(18 19 20)(21 22 23)(24 25
26)(27 28 29)(30 31 32)(33 34 35)(36 37 38)(39 40 41)(42 43 44)(45 46 47)
(48 49 50)(51 52 53)(54 55 56)(57 58 59)(60 61 62)(63 64 65)(66 67 68)
(69 70 71)(72 73 74)(75 76 77)(78 79 80)(81 84 87)(82 85 88)(83 86 89)
(99 100 101)(102 103 104)(105 106 107)
(0 3 6)(1 4 7)(2 5 8)(9 12 15)(10 13 16)(11 14 17)(18 21 24)(19 22 25)(20 23
26)(27 30 33)(28 31 34)(29 32 35)(36 39 42)(37 40 43)(38 41 44)(45 48 51)
(46 49 52)(47 50 53)(54 57 60)(55 58 61)(56 59 62)(63 66 69)(64 67 70)
(65 68 71)(72 75 78)(73 76 79)(74 77 80)(81 82 83)(84 85 86)(87 88 89)
(99 102 105)(100 103 106)(101 104 107)(108 109 110)(111 112 113)(114 115
116)


you can post other grids and I post the generators or I can upload my programs
su2gra.exe and gauto.exe (which uses Nauty-code)
---------done---------
http://magictour.free.fr/su2gra.exe
http://magictour.free.fr/gauto.exe

I should merge these two programs, so it reads sudokus without
storing the 117-graph to a file but rather processes it directly
maybe even reads sudokus in sudz format or such
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: About Red Ed's Sudoku symmetry group

Postby Mauricio » Mon Nov 07, 2011 6:02 pm

eleven wrote:...

Surely at least eleven and RW would find this puzzles very pleasant.
Code: Select all
...........12.34.5.46..721...71.893...........296.47...139..84.5.43.21...........
...........12.34.5.46..721...74.893...........296.17...139..84.5.43.21...........
...........12.34.5.46..721...81.973...........276.48...138..94.5.43.21...........
...........12.34.5.46..721...84.973...........276.18...138..94.5.43.21...........

Minimals, very similar yet different puzzles, ED=8.4/8.4/2.6. Solvable using singles if you assume a unique solution.

One more, solvable using singles and assuming unique solution
Code: Select all
...........1..23.43..5..2612...718.9.........9.738...2169..4..35.39..1...........


I don't know if the puzzles require their own thread, so I post them here, the original discussion was lost in the great crash.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Re: About Red Ed's Sudoku symmetry group

Postby eleven » Tue Nov 08, 2011 9:50 pm

Thanks for those puzzles Mauricio, very nice with both 4 and 8 cell unavoidables.
eleven
 
Posts: 1535
Joined: 10 February 2008

Previous

Return to General