Sudoku Symmetry Group (minimal spec)

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

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Fri Dec 21, 2018 6:40 pm

blue wrote:How come his feet aren't where his head should be, and vica-versa ?


His feet could be in his mouth, like mine usually are :D
User avatar
Mathimagics
2017 Supporter
 
Posts: 1283
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Fri Dec 21, 2018 8:51 pm

deleted.
Last edited by StrmCkr on Sun Dec 23, 2018 9:05 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Proofiness

Postby Mathimagics » Sat Dec 22, 2018 8:10 am

.
Some observations that might be useful in the search for proofiness (not to be confused with "truthiness").

Consider the case of simple Latin Squares of order N (note, not N^2). The order of the symmetry group LG(N) is (N! ^ 2 * 2).

Now that we have one less "dimension" (no bands), it is not surprising that we find these groups can be generated by just 2 permutations {x, y}.

This SG2-style generator seems to do the job (although note that it is sensitive to the parity of N):

  • x = ShiftR(N-1) for odd N
  • x = ShiftR(N-2) for even N
  • y = Rotate 90

Interestingly, I can't seem to find an equivalent SG1-style generator, ie. any {x, y} with y = flip.

Perhaps this group might be easier to analyse? If so, it might lead us to a method for solving the SG proof problem.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1283
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Sat Dec 22, 2018 9:15 am

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.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Sat Dec 22, 2018 4:54 pm

deleted
Last edited by blue on Sun Dec 23, 2018 10:32 am, edited 1 time in total.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Sat Dec 22, 2018 6:30 pm

deleted
Last edited by StrmCkr on Sun Dec 23, 2018 9:05 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Sat Dec 22, 2018 7:57 pm

deleted
Last edited by blue on Sun Dec 23, 2018 10:32 am, edited 1 time in total.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Proofiness

Postby blue » Sat Dec 22, 2018 8:10 pm

Mathimagics wrote:.
Some observations that might be useful in the search for proofiness (not to be confused with "truthiness").

Consider the case of simple Latin Squares of order N (note, not N^2). The order of the symmetry group LG(N) is (N! ^ 2 * 2).

Now that we have one less "dimension" (no bands), it is not surprising that we find these groups can be generated by just 2 permutations {x, y}.

This SG2-style generator seems to do the job (although note that it is sensitive to the parity of N):

  • x = ShiftR(N-1) for odd N
  • x = ShiftR(N-2) for even N
  • y = Rotate 90

Interestingly, I can't seem to find an equivalent SG1-style generator, ie. any {x, y} with y = flip.

That seems to work for all odd N.
For even N, it looks like it only works for N >= 8.
(For N=2, ShiftR(0) doesn't make sense ... ShiftR(1) is the "no nothing" operation).
Checked with GAP, for N=3,4,...,40.

This, seems to work for all N >= 2 ... checked for N=2,...,40:

  • x = ShiftR(N) + ShiftC(N-1)
  • y = Flip
blue
 
Posts: 853
Joined: 11 March 2013

Re: Proofiness

Postby blue » Sat Dec 22, 2018 9:23 pm

For Latin Squares:

blue wrote:This, seems to work for all N >= 2 ... checked for N=2,...,40:

  • x = ShiftR(N) + ShiftC(N-1)
  • y = Flip

Similarly, for Sudoku, this seems to work:

  • x = ShiftR(N) + ShiftC(N-1)
  • y = ShiftB(N) + ShiftS(N-1)
  • z = Flip
Checked for N=2,...,10 with GAP.

Added: It's easy to prove that these work for all N, too.
Last edited by blue on Sat Dec 22, 2018 9:33 pm, edited 1 time in total.
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Sat Dec 22, 2018 9:31 pm

.
Ok, that's nice! We'll add that to the catalog ...

I'll have to revise my formulation, I thought I had checked N=6 but obviously not! 8-)

blue wrote:For N=2, ShiftR(0) doesn't make sense ...

Unless you accept that Shift(0) = Shift(1) = ()
User avatar
Mathimagics
2017 Supporter
 
Posts: 1283
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby blue » Sat Dec 22, 2018 9:53 pm

Mathimagics wrote:Unless you accept that Shift(0) = Shift(1) = ()

True.
It's just my GAP code that breaks down. :(

Code: Select all
gap> cycle := function(N,n) return Concatenation([2..n],[1],[n+1..N]); end;;
gap> cycle(3,1);
[ 1, 2, 3 ]
gap> cycle(3,2);
[ 2, 1, 3 ]
gap> cycle(3,3);
[ 2, 3, 1 ]
gap> cycle(3,0);
[ 1, 1, 2, 3 ]
gap> PermList(cycle(3,1));
()
gap> PermList(cycle(3,2));
(1,2)
gap> PermList(cycle(3,3));
(1,2,3)
gap> PermList(cycle(3,0));
fail
gap>
blue
 
Posts: 853
Joined: 11 March 2013

Re: Sudoku Symmetry Group (minimal spec)

Postby Mathimagics » Sat Dec 22, 2018 10:09 pm

.
Try this:
Code: Select all
cycle := function(N,n) if (n < 2) then n  := 1; fi; return Concatenation([2..n],[1],[n+1..N]); end;;

8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1283
Joined: 27 May 2015
Location: Canberra

Re: Sudoku Symmetry Group (minimal spec)

Postby StrmCkr » Sun Dec 23, 2018 9:25 am

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

Rotate quarter turn is different.


well, apparently i didn't see this correction point earlier i would have dropped everything from the get go....

.......that's what i get for 2 much work and no sleep... thanks for bearing with me....

and
spelled right out in
blues post
None of the individual operations are quarter turns, but ...
"1 -> 2 -> 3" gives a CW quarter turn (overall), and "2 -> 3 -> 4" gives a CCW quarter turn.


i clearly missed the 1/4 turn reference again in blues sub point that diagonal reflection + vertical or horizontal reflection = 90 CCW rotation or 90 Cw rotation.

the good thing is Ive now put (1/4 ) turn back-into my solver since it was missing from the rebuild.
and i learned there is a reference to which is the clearly called the "main diagonal"
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 980
Joined: 05 September 2006

Re: Proofiness

Postby Mathimagics » Mon Dec 24, 2018 1:45 am

blue wrote:Similarly, for Sudoku, this seems to work:

  • x = ShiftR(N) + ShiftC(N-1)
  • y = ShiftB(N) + ShiftS(N-1)
  • z = Flip
Checked for N=2,...,10 with GAP.

Added: It's easy to prove that these work for all N, too.


Anything provable is quite exciting! 8-)

Can we see the proof, or an outline thereof :?:

[EDIT] LS generators verified to N = 70, SG generators to N = 11 (!). N = 12 crashes Gap on my Win64 system, so that's my absolute limit.
As for my rotation-based SG generator, it's failure on just N=4, N=6 is really intriguing. Clearly something to do with rotate quarter-turn failing to combine with the other x permutation in enough ways. Dihedral group properties? I'm looking into the corresponding Cayley tables to see if there is an explanation.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1283
Joined: 27 May 2015
Location: Canberra

Re: Proofiness

Postby blue » Mon Dec 24, 2018 6:08 am

Starting from:

  • x = ShiftR(N) + ShiftC(N-1)
  • y = ShiftB(N) + ShiftS(N-1)
  • z = Flip
The factors in x commute, and we have:
    x^k = ShiftR(N)^k * ShiftC(N-1)^k
With that we can derive ...

x^(N-1)
    = ShiftR(N)^(N-1) * ShiftC(N-1)^(N-1)
    = ShiftR(N)^(-1) * ShiftR(N)^N * ShiftC(N-1)^(N-1)
    = ShiftR(N)^(-1)
x^N
    = ShiftR(N)^N * ShiftC(N-1)^N
    = ShiftR(N)^N * ShiftC(N-1)^(N-1) * ShiftC(N-1)
    = ShiftC(N-1)
x^(N*(N-1)) = 1

z*x^N*z
    = Flip + ShiftC(N-1) + Flip
    = ShiftR(N-1)
Using 'y' instead of 'x', we get similar results for ShiftB()

Summarizing, we have
Code: Select all
1) Flip = z

2) ShiftR(N)^(-1) = x^(N-1)
3) ShiftR(N-1)    = z*x^N*z

4) ShiftB(N)^(-1) = y^(N-1)
5) ShiftB(N-1)    = z*y^N*z

And if we like:
Code: Select all
6) ShiftR(N) = x^((N-1)*(N-1)) ... from (2) and (x^(N*(N-1)) = 1)
7) ShiftB(N) = y^((N-1)*(N-1)) ... from (3) and (x^(N*(N-1)) = 1)

Next, it's easy to check that (with '+' meaning "followed by"):
Code: Select all
SwapR(1,N) = ShiftR(N-1) + ShiftR(N)^(-1) ... swaps rows 1 & N
SwapB(1,N) = ShiftB(N-1) + ShiftB(N)^(-1) ... swaps bands 1 & N

We could probably stop here, but since the Wikipedia articles involving the group of (all) permutations of a list of n items -- S(n) -- say that the standard set of generators is the set of swaps of adjacent items ...

Using the the N-cycles for band and rows, with the swaps above we can get:
Code: Select all
SwapR(r,r+1) = ShiftR(N)^r + SwapR(1,N) + ShiftR(N)^(-r)
SwapB(b,b+1) = ShiftB(N)^b + SwapB(1,N) + ShiftB(N)^(-b)

SwapC(c,c+1) = Flip + SwapR(c,c+1) + Flip
SwapS(s,s+1) = Flip + SwapB(s,s+1) + Flip

SwapBandRows(1  ,r,r+1) = SwapR(r,r+1)
SwapBandRows(1+b,r,r+1) = ShiftB(N)^b + SwapR(r,r+1) + ShiftR(N)^(-b)

SwapStackColumns(1  ,c,c+1) = Flip + SwapBandRows(1  ,c,c+1) + Flip
SwapStackColumns(1+s,c,c+1) = Flip + SwapBandRows(1+s,c,c+1) + Flip

... with all of the RHS expressed (recursively as necessary) in terms of x,y and z.

Added: I fixed, I hope, all of the errors involcing wrong ordering for '+' terms.
I write B*A for what would be A+B here ... corresponding to "B(A(x)) = (B*A)(x)".
Last edited by blue on Mon Dec 24, 2018 6:35 am, edited 4 times in total.
blue
 
Posts: 853
Joined: 11 March 2013

PreviousNext

Return to General