## Sudoku Symmetry Group (minimal spec)

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

### Re: Sudoku Symmetry Group (minimal spec)

Hi Mathimagics,

Thanks for the explanation about N=5 and SmallGeneratingSet.
I understand the name now ... i.e. why it isn't called MinimalGeneratingSet.

Ok, but the real upshot is that this demonstrates what I said earlier about rotate being more "powerful" than flip - the rotate permutation still completed the group, without having a complete subgroup of row/band permutations.

This explains why my x and y operations using (N-1) + (N-2) shifts still work, even though the pair {x, y} does not generate the full band/row subgroup! It doesn't actually have to, because of the power of rotate to fill in the gaps (pun intended)!

Yes, I witnessed the "power of rotate", in my earlier scheme.

PS: Yes, my shifts are done left to right (+ means "followed by"). I haven't tested whether this order is critical or not, but will do this.

[EDIT] The order of the shifts is apparently not critical at all, the "+" actually commutes in this particular case!

The order of the operations will make a difference in the actual generators, though, since row operations in band 1, don't commute with band operations involving band 1.
I don't know how detailed your testing was, but unless I have a bug, for N=3, the ordering did matter, as to whether {x,y} generates the "bands & rows" group. It's possible that even though switching the order (apparently) doesn't work for that part, adding "z = rotate" to the set, still works for generating the full group.

You will have gathered that all my verifications simply involve examining the group size when I plug a set of permutations into GAP ... very fast.

Nothing wrong with that. I should really learn GAP

We have done well, I think! We have produced truly elegant, generally applicable minimal generators ... good job all round!

I would be much happier if we could come up with an actual proof (or a clear vision that one exists), for general N, and some particular specification of generators.

I think I could do that for my earlier setup for the full group, but I'ld be much happier if we could do it for a pair of generators for the "bands & rows" subgroup. I'm close to having something, I think. (Edit: ... not as close as I hoped ) If it works, it would involve an "odd/even" difference, again, in the way the generators are specified.
blue

Posts: 894
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

blue wrote:I should really learn GAP

The interface is a little primitive and unforgiving, but installation is painless (on Win64 at least, but that says much for an open-source package). I can give you my scripts for getting the group sizes, (and I have one for extracting individual conjugacy class permutations). That will save you much pain ...

blue wrote:I'd be much happier if we could do it for a pair of generators for the "bands & rows" subgroup.

I agree this seems the more likely route. We need to show that HG1 {x, y} generates this subgroup for any N, and then that adding the flip element generates the full group.

Mathimagics
2017 Supporter

Posts: 1481
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

Mathimagics wrote:
blue wrote:I should really learn GAP

The interface is a little primitive and unforgiving, but installation is painless (on Win64 at least, but that says much for an open-source package). I can give you my scripts for getting the group sizes, (and I have one for extracting individual conjugacy class permutations). That will save you much pain ...

I have it downloaded and installed, and some of it learned, thanks.

Below is some "LogTo" file output, showing some results.

For anyone else who's interested, at the top, are short functions for producing the groups for (N*N)x(N*N) and (N1*N2)x(N2*N1) Sudoku.
(I'm not sure if I have the orderering right, for the N1,N2 case).

Hidden Text: Show
Code: Select all
`gap> sgrp  := function(N)>   local g;>   g := WreathProduct(SymmetricGroup(N),SymmetricGroup(N));>   return WreathProduct(g,SymmetricGroup(2));> end;;gap> gap> sgrp2 := function(N1,N2)>   local g1, g2;>   g1 := WreathProduct(SymmetricGroup(N1),SymmetricGroup(N2));>   g2 := WreathProduct(SymmetricGroup(N2),SymmetricGroup(N1));>   return DirectProduct(g1,g2);> end;;gap> gap> Size(sgrp(3));3359232gap> NrConjugacyClasses(sgrp(3));275gap> gap> Size(sgrp2(3,3));1679616gap> NrConjugacyClasses(sgrp2(3,3));484gap> gap> Size(sgrp(4));126806761930752gap> NrConjugacyClasses(sgrp(4));18335gap> gap> Size(sgrp(5));17832200896512000000000000gap> gap> Size(sgrp2(2,3));3456gap> NrConjugacyClasses(sgrp2(2,3));90gap> quit;`
blue

Posts: 894
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

deleted
Last edited by StrmCkr on Sun Dec 23, 2018 9:10 am, edited 1 time in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1085
Joined: 05 September 2006

### Re: Sudoku Symmetry Group (minimal spec)

deleted
Last edited by blue on Sun Dec 23, 2018 10:29 am, edited 1 time in total.
blue

Posts: 894
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

deleted.
Last edited by StrmCkr on Sun Dec 23, 2018 9:11 am, edited 1 time in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1085
Joined: 05 September 2006

### Re: Sudoku Symmetry Group (minimal spec)

.
Transpose (aka flip) IS a diagonal reflection (main diagonal).

Rotate quarter turn is different.

Mathimagics
2017 Supporter

Posts: 1481
Joined: 27 May 2015
Location: Canberra

### Re: Sudoku Symmetry Group (minimal spec)

deleted
Last edited by blue on Sun Dec 23, 2018 10:30 am, edited 1 time in total.
blue

Posts: 894
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

deleted.
Last edited by StrmCkr on Sun Dec 23, 2018 9:07 am, edited 1 time in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1085
Joined: 05 September 2006

### Re: Sudoku Symmetry Group (minimal spec)

blue wrote:
Code: Select all
`+-------+    +-------+    +-------+    +-------+| a b c |    | e . . |    | e d a |    | . . c || d . . | -> | d . . | -> | . . b | -> | . . b || e . . |    | a b c |    | . . c |    | e d a |+-------+    +-------+    +-------+    +-------+`

1,2,3,4

1 and 4 ( I have)
2 and 3 ( I have)
.
3 - 4 and
1-2 I don't.
(so yes you are using a fixed rotational direction 1/4 turn after transposing...
Last edited by StrmCkr on Fri Dec 21, 2018 1:03 pm, edited 1 time in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1085
Joined: 05 September 2006

### Re: Sudoku Symmetry Group (minimal spec)

deleted
Last edited by blue on Sun Dec 23, 2018 10:30 am, edited 1 time in total.
blue

Posts: 894
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

deleted
Last edited by StrmCkr on Sun Dec 23, 2018 9:09 am, edited 1 time in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1085
Joined: 05 September 2006

### Re: Sudoku Symmetry Group (minimal spec)

deleted
Last edited by blue on Sun Dec 23, 2018 10:31 am, edited 1 time in total.
blue

Posts: 894
Joined: 11 March 2013

### Re: Sudoku Symmetry Group (minimal spec)

deleted
Last edited by StrmCkr on Sun Dec 23, 2018 9:04 am, edited 1 time in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1085
Joined: 05 September 2006

### Re: Sudoku Symmetry Group (minimal spec)

deleted
Last edited by blue on Sun Dec 23, 2018 10:32 am, edited 1 time in total.
blue

Posts: 894
Joined: 11 March 2013

PreviousNext