The New Sudoku Players' Forum

[Mathimagics]

How does this make sense?

There are 3 bands, but only 2 stacks (towers) ...

Reflecting about the diagonal destroys the "all box cells have different values" property

[Mathimagics]

.
The minimum number clues for Sudoku6 is 8 (this was known).

Of the 49 ED grids, 29 have 8C puzzles. The number of 8C puzzles for these grids is in the range [6, 576]. There are 2619 x 8C puzzles in total on the 29 grids.

The grid with 576 x 8C puzzles is:

Code: Select all

123456456231231645564123312564645312

The puzzle list for the only grid with 6 puzzles :

Hidden Text: Show

Code: Select all

.2.4.6.5......4.......1.3.........2.
.2.4............6...5.1..6.....4...3
.2....4.........6..35.......4...1..3
.2.....5.1....4.6.......3...4.....2.
.2.......13.....6......43..5...4....
...4...5....2.4.6.....1..6.........3


[Serg]

Hi, Mathimagics!

.
This is probably nothing new, but the standard Sudoku symmetry group (275 conjugacy classes, 3359232 members) can be generated from just 3 permutations, which is cool!

• rotate 90

• swap rows 1,2

• swap bands 1,2

Congratulations! Your result is elegant.

7 years ago (still at Sudoku Programmers Forum) I discussed a similar problem - can be chosen another "basic" permutaions set (other than classic Gordon Royle's set) for all VPT accounting. It turned out that there are other representation sets (including quarter turn), but those my representation sets included much more transformations.

Serg

[Mathimagics]

.
Thanks, Serg!

Ah, the SPF - those were the days!

[qiuyanzhe]

There are 3 bands, but only 2 stacks (towers) ...

I was talking about the standard 9*9 grid. I am sure that's true, but I wonder how it can be used.

[Mathimagics]

I was talking about the standard 9*9 grid. I am sure that's true, but I wonder how it can be used.

Sorry, when you said "how does this make sense?", I thought you were referring to the 6x6 case.

[Mathimagics]

.
For Sudoku 16x16, assuming I have generated the basic permutations correctly (!), there appear to be a rather daunting 126,806,761,930,752 members in the symmetry group (suggesting that canonicalisation of grids might be a tad sluggish!). These form 18,335 conjugacy classes.

But the REALLY interesting thing is that, once again, the group can be generated by just 3 permutations!

Sadly, not the same 3 simple ones that work for 9x9.

[qiuyanzhe]

Hi, Mathimagics!

But the REALLY interesting thing is that, once again, the group can be generated by just 3 permutations!

I guess one of the simplest expressions is:
a:Swapping rows 12
b:Swapping bands 12
c:Switch bands (1234) to bands (1342), then switch rows (1234) in band 1 to rows (1342), and the same for columns and stacks, then flip along main diagonal.

a^2=b^2=c^6=1,
c^3=flip, c^4=(c without flipping).

For each transformation, firstly flip if needed.
If we need to swap two bands, switch the bands to bands12, then do a 'b', then do the inverse of previous operations.
If we need to swap two rows, switch their band to band1, then switch them to rows12, then do an 'a', then do the inverse of previous operations.
Then flip,
And adjust columns.
Flip once finally.

This can be generalized to grids of (2k)*(2k), but I've not found a straightforward expression for (2k+1)*(2k+1) grids in general.

[Mathimagics]

a:Swapping rows 12
b:Swapping bands 12
c:Switch bands (1234) to bands (1342), then switch rows (1234) in band 1 to rows (1342), and the same for columns and stacks, then flip along main diagonal.

Nice work!

"Switch bands (1234) to bands (1342)" we can simplify (semantically, not algebraically) as "Shift(B2,B3,B4)", ie: Cyclically shift.

Meanwhile, after a good night's sleep, I came up with this:

• x = Swap R1,R2

• y = Swap B1,B2

• z = Shift(R1,R2,R3) + Shift(B1,B2,B3) + Rotate

We can use any 3 indices in the shifts, so long as the same 3 appear in both shifts.

Note that we have used only bands/rows. By using rotate rather than transpose (flip) we automatically get the stack/col ops covered.

I think this will also work for 2k cases generally. The shifts involve the first 2k-1 rows/bands.

Generalising case 2k+1 is problematic, as you said. I am still looking for a 25x25 (k=2) solution ...

[Mathimagics]

.
Ok, I have a 25x25 (k = 2) solution:

• x = Shift(R1,R2,R3,R4)

• y = Shift(B1,B2,B3,B4)

• z = Shift(R1,R2,R3,R4,R5) + Shift(B1,B2,B3,B4,B5) + Rotate

Ok, now if we retro-fit this system to 9x9 (k = 1), we get

• x = Shift(R1,R2), ie. Swap R1,R2

• y = Shift(B1,B2), ie. Swap B1,B2

• z = Shift(R1,R2,R3) + Shift(B1,B2,B3) + Rotate

And this looks very much like what I have got above for 16x16!

But sadly, it does NOT work for 9x9, we have to drop the shifts in z. So is 3x3 just a special magic case, or is it because k is odd?

Need to test k = 1...4 to find out. Can GAP handle the 81x81 case (k=4)? Should be interesting ....

[blue]

Here's another one for 16x16:

Code: Select all

A : swap (band 1) rows 1 & 2
    cycle bands 2,3,4 "down" (2 -> 3 -> 4 -> 2)
       A^4 does only the band cycle
       A^3 does only the row swap
B : cycle (band 1) rows 2,3,4 "down" (2 -> 3 -> 4 -> 2)
    swap bands 2 & 3
       B^4 does only the row cycle
       B^3 does only the band swap
C : quarter turn clockwise

[Mathimagics]

.
Nice one, blue!

More grist for the mill ...

It has the desirable property of keeping the rotation separate. I couldn't find the right combinations for the other two. My best was 50% of the target, and I switched to testing combinations with rotation ...

Cheers!

[EDIT] it seems also to work if you use 1,2,3 only in the cycle ops, and 1,2 only in the swaps. Thus, in my notation:

• x = Swap R1,R2 + Shift(B1,B2,B3)

• y = Shift(R1,R2,R3) + Swap B1,B2

• z = Rotate

[qiuyanzhe]

I am still holding the opinion that "flip" is better than "rotate".
It has period 2, and it is easier to tell what a cell contains after/before flipping than rotating.

[qiuyanzhe]

Congrats to blue!
Why didn't I get the point of combining an odd-period permutation with the swap..
Really elegant, and I believe that would make the example for 25*25 much more straightforward.

Here's what I got lately:

Keeping two swaps, the third one could be
x = Swap(R12)
y = Swap(B12)
z = Shift(R12345) + Shift(B12345) + Flip
and its verification was long..

Also verified
x = Swap(R1234)
y = Swap(B1234)
z = Shift(R12345) + Shift(B12345) + Flip
Define z' = Shift(B12345),
then all we need is that we can swap two bands (consecutive in z') using y and z', and because
12345--z'->51234--y^(-1)->12354,
so this could do exactly the same thing as my previous one.

[Mathimagics]

I am still holding the opinion that "flip" is better than "rotate".
It has period 2, and it is easier to tell what a cell contains after/before flipping than rotating.

I guess it all depends on what better means. I suppose if one is actually combining the permutations and testing whether all basic operations are covered, then yes, flip might be more convenient.

If, on the other hand, one is simply plugging the permutation triplets (z, y, z) into GAP and checking the resulting group size, then this convenience is moot.

For most practical purposes (in this forum), minimal group-generating permutation sets have little, if any, significance. So this is purely an academic exercise.

Hence we are looking for elegance, which I have defined (unilaterally, of course ) as a triplet that uses the least number of elementary operations (swap, rotate, flip) to define a group. So from this perspective, rotation is a winner.

Any triplet system that is both elegant, and clearly generalizable to all square box sizes will be designated truly elegant, and perhaps awesome.

But please feel free to work with whatever works for you ...