The New Sudoku Players' Forum

[gfroyle]

It has occurred to me that Sudoku (playing, studying) involves a large number of concepts from combinatorics.

Therefore I thought it might be nice to write up some elementary "essays" on combintorial topics that used Sudoku as a running example.

I have done an example of such an essay based on the concept of SYMMETRY...

http://www.csse.uwa.edu.au/~gordon/sudoku/sudoku-symmetry.pdf

The idea here is to explain the FORMAL mathematics (at a beginner's level) underlying the concepts of a symmetric puzzle. This sort of complements the various informal descriptions (by Tso in particular) of symmetries.

Those familiar with group theory and combinatorics will recognize the basic arguments as common to every beginning text book known to man, but hopefully the Sudoku twist adds some extra interest.

Comments and feedback welcomed..

Gordon

[re'born]

Gordon,

I took a look at your note and really enjoyed it. The pictures are terribly nice (I appreciate that when you rotate the squares, you also rotate the letters), and the exposition is well-paced.

As I study finite group theory, I thought it might be unfair of me to read it critically from a mathematics point of view. I presume your goal was to use this to whet someone's appetite, not as a reference for the foundations of group theory. So, I had my wife read it. She is a Sudoku player, but does not know any group theory (well, other than Burnside's p^a q^b theorem, but that is just to impress people at parties). There were two things that were confusing to her. First, you don't define the order of a group element very precisely. Our conversation went roughly as follows:

rep'nA's wife: Why is the order of a 4 and not 8? 8 times leaves it back in the same position, doesn't it?

rep'nA: Yes, but we take the smallest number of times to be the order.

rep'nA's wife: Oh. Well, why isn't it 0 then. If you don't do anything, the position doesn't change.

rep'nA: Yeah, so we define it to always be positive, so it can't be 0.

rep'nA's wife: Oh. Why didn't he just say that?

The other thing that confused her was at the end when you introduce conjugation. She had a little trouble seeing that a^{-1} = a^3 . Thankfully, that conversation ended with her saying, "oh yeah, doy."

I hope this feedback is useful. Keep us posted on any updates or a part II.

rep'nA

[JPF]

Thanks Gordon.

That's very useful, particularly for old-timers like me, who learnt group theory some(!) decades ago with old friend E. Galois...

One slight comment and one question :

a) I would have put somewhere the word non-commutative (ab # ba), just in case..., and add that every symmetry s of the square can be written in only one way as s=(b^n).(a^p) where 0<=n<=1 ; 0<=p<=3

The different types of symmetries could therefore be described by a set of values of (n ; p)

b) There are 10^81 (valid or not valid) puzzles.
There are 2^81 = 2,4 x 10^24 patterns, before considering any types of symmetries.
How many patterns of each type (i.e. I to VII) ?

Last point, for those bloody cartesian people :
Let be RiCj the coordinates of the cell in the grid.

Using the name of the transformations,

Code: Select all

                                     Row         Column
Identity               e             i            j
90° rotation           a             j          10-i
180° rotation          a^2          10-i        10-j
270° rotation          a^3          10-j          i
R. vertical axis       b             i          10-j
R. anti-diagonal       ba           10-j        10-i
R. horizontal axis     ba^2         10-i          j
R. main diagonal       ba^3          j            i
   

Cheers,

Jean-Pierre

[Red Ed]

Might it be worth saying something about automorphic puzzles, i.e. where the symmetry op fixes the clues and consistently relabels the symbols? Perhaps not, as it's a bit "niche", but just a thought ...

[gfroyle]

So, I had my wife read it. She is a Sudoku player, but does not know any group theory

Thanks for that... I don't think I could convince my wife to read any of my work!

The comments were spot-on and were pretty much things where I had wondered "hmm, wonder if this needs a bit more explanation". Always a battle trying to decide how much to include and how much to leave out, and whether to keep it reasonably informal, or to include formal definitions.

Trouble is that to a mathematician, a formal definition is a way of SIMPLIFYING and clarifying things, while to a non-mathematician a formal definition is often a scary and meaningless bunch of symbols.


Have updated it to Version 0.2 based on those comments..

Cheers

gordon

[gfroyle]

Might it be worth saying something about automorphic puzzles, i.e. where the symmetry op fixes the clues and consistently relabels the symbols? Perhaps not, as it's a bit "niche", but just a thought ...

A nice topic.. but a little more subtle and probably best off in a different essay.. it's on the list though!

Cheers

gordon

[gfroyle]

How many patterns of each type (i.e. I to VII) ?

Thanks for the comments..

We can count the number of patterns of each type if we want to - I'll just do an example for the biggest symmetry type - the whole dihedral group D_8.

If the top-left cell (1,1) is full, then so must all the corners (1,9), (9,1) and (9,9), and conversely if one of them is empty, then so must all the others..

This bunch of cells that are either "all-in" or "all-out" will be called an ORBIT... (in technical terms it is an orbit of the action of D_8 on the 81 cells of the grid).

So the 81 cells can be partitioned into orbits that are either "all-in" or "all-out" and the number of patterns is then just 2^{number of orbits}.

What orbits are there?

There are orbits of size 1 (central cell), 4 (cells on the corners, cells in row and column 5 and cells on the diagonals) and 8 (all other cells).

So there is one orbit of size 1, eight orbits of size 4 and six orbits of size 8 for a total of 15 orbits.

So there are 2^15 patterns that are symmetric with respect to D_8 (including a completely empty grid, and also a completely full grid).


Is there a totally symmetric 17-clue pattern?

Well, we can make a 17-clue pattern from these orbits by either

- the centre cell plus 4 out of 8 orbits of size 4
- the centre cell, 2 out of the 8 orbits of size 4 and 1 out of the 6 of size 8
- the centre cell plus 2 of the 6 orbits of size 8.

So the total number to check is

C(8, 4) + C(8,2)*C(6,1) + C(6,2) = 253

where C(n,m) is the binomial coefficient of course..

So only 253 patterns to consider, even before eliminating impossible ones and equivalences.

Cheers

Gordon

[re'born]

Gordon,

I read the new version and I liked the changes. I sent it to my wife and you will be happy to know that she approves as well. She says she won't read my papers until I do like you and write about something useful.

Always a battle trying to decide how much to include and how much to leave out, and whether to keep it reasonably informal, or to include formal definitions.

I know what you mean. I think, though, that you do an excellent job here of motivating the definition of a group. It is very sly the way you get the reader to think that they're looking at a puzzle, but at the same time they learn about the structure of the dihedral group. Maybe you could highlight your use of Lagrange's Theorem a little more, but your decision to use it without being too formal is probably for the best.


Best regards,
Adam

[JPF]

Thanks again Gordon.
I appreciate the time you spent to give such a comprehensive and personalized answer.

I will try to post a thread on the fully symmetric puzzles.
I don't think it's worth spoiling your thread by my absurd new questions.

This bunch of cells that are either "all-in" or "all-out" will be called an ORBIT... (in technical terms it is an orbit of the action of D_8 on the 81 cells of the grid).

After that, I feel like an astronaut .

I took a look at your note again, but more carefully.

Now, it is easy to see that if...

At this point, it's a bit difficult to understand, why you consider those 2 elements (ba^2 and b) and show that there are conjugate.
Why those two, particularly ?

Are there any other equivalent symmetries( i.e. conjugate elements) ?

At the end of your paper, it's not clear to me if there are 7 conjugacy classes or less.
But I am a very bad student.

Jean-Pierre

[gfroyle]

At this point, it's a bit difficult to understand, why you consider those 2 elements (ba^2 and b) and show that there are conjugate.
Why those two, particularly ?

Are there any other equivalent symmetries( i.e. conjugate elements) ?

At the end of your paper, it's not clear to me if there are 7 conjugacy classes or less.
But I am a very bad student.

I wavered about including or excluding the concept of conjugacy... but decided in the end that it would be a cop-out if I excluded it.

The issue is that it is intuitively clear to everyone that horizontal reflection is "essentially the same" as vertical reflection, and it is really this concept that conjugacy captures.

Basically if two elements are conjugate then you can think of them as two "views" of the same thing...

The example that I gave was simply an example showing how you would actually demonstrate that two elements are conjugate. There are two more non-trivial conjugacies in the dihedral group ... namely the 90 degree rotation a is conjugate to the 270 degree rotation a^3, and the diagonal reflection is conjugate to the anti-diagonal reflection.

What this means in practice is that if I give you a puzzle with a horizontal reflection symmetry, then you can immediately turn it into one with a vertical reflection symmetry (just rotate it). But if I give you one with a horizontal reflection symmetry then you CANNOT immediately turn it into one with a 180 degree rotation symmetry. So these types of symmetry are FUNDAMENTALLY different, whereas the horizontal/vertical reflections are just "cosmetically" different.

We can extend the concept of conjugacy from individual elements to entire subgroups, and again we usually view conjugate subgroups as "essentially the same". The list of 7 symmetry types of Sudoku puzzles contains one representative of each conjugacy class of subgroups (other than the 1-element subgroup) and so it lists all the "fundamentally different" types of symmetry...

Cheers

Gordon

[PaulIQ164]

Good stuff. And as a recent inroductee to making TeX documents for my uni project (finite group theory too as it happens) I appreciate how nicely it's all laid out.

[Ocean]

Very good explanation of the mathematics behind symmetry, Gordon!

I have one comment, or question.

The list of 7 symmetry types of Sudoku puzzles contains one representative of each conjugacy class of subgroups (other than the 1-element subgroup) and so it lists all the "fundamentally different" types of symmetry...

There might also be other kinds of symmetry than those listed - or is this called something else:

Code: Select all

M24: Band repetition

 3 . . | . . 8 | . . .
 6 7 . | . . . | . . 5
 . . . | 5 . . | . 4 2
-------+-------+-------
 8 . . | . . 2 | . . .
 9 6 . | . . . | . . 1
 . . . | 3 . . | . 5 4
-------+-------+-------
 5 . . | . . 1 | . . .
 2 3 . | . . . | . . 6
 . . . | 9 . . | . 3 7

Code: Select all

M24: Band rotation

 7 . . | . 5 . | . . .
 4 9 . | . . . | . 2 3
 . . . | . 8 . | . . 6
-------+-------+-------
 . 1 . | 6 . . | . 3 .
 . . . | 5 . 8 | . . .
 . 6 . | . . 2 | . 7 .
-------+-------+-------
 . . . | . 2 . | 6 . .
 . 7 1 | . . . | 5 4 .
 . . 4 | . 1 . | . . .

The latter pattern has a symmetry of order 8(?), here is one of the transforms:

Code: Select all

Transformed puzzle:

 4 . . | . 1 . | . . .
 1 7 . | . . . | . 4 5
 . . . | . 2 . | . . 6
-------+-------+-------
 . 6 . | 2 . . | . 7 .
 . . . | 8 . 5 | . . .
 . 1 . | . . 6 | . 3 .
-------+-------+-------
 . . . | . 8 . | 6 . .
 . 9 4 | . . . | 3 2 .
 . . 7 | . 5 . | . . .

[Red Ed]

There might also be other kinds of symmetry than those listed

I think he's just looking at isometries -- that is, the different forms you can get by rotating and turning-over a puzzle drawn on a piece of tracing paper. Other validity-preserving symmetries such as band-cycling are, I suppose, not so pleasing to the human eye.

On another subject ... I think that the bit about conjugacy classes could be clearer. Gordon says that if you mangle a puzzle with group ops then, whilst you'll probably get a different symmetry, you really still get the same "type" of symmetry (let's take this as our definition of "type" of symmetry now). Then he gives a specific example which I personally found unenlightening, as I was too lazy to look back to see what his ops a and b were. Perhaps it would be better to say: let s,t be group ops; then s is a symmetry of clue positions P (so sP = P) iff tst' is a symmetry of tP (since tst' tP = tsP = tP). That is:

Code: Select all

Clue Positions  P ----transform---> tP
   Symmetry     s ----conjugate---> tst'

... and so conjugating by any op t leaves the symmetry "type" unchanged.

Ed.

[gsf]

Gordon,
are the transform labels I II III IV ... standard or just for the paper?

[claudiarabia]

Hi,

I developed this easy sudoku with a kind of spiral-symmetry. I have never found a kind like this in the forums or magazines before. Did somebody?

Code: Select all

 
 . . . . . 3 . . 5
 3 5 . . 9 . . . 7
 . . 6 . 2 . . . 8
 . . . . 6 . . 2 .
 . . 8 . 4 . . . .
 . . . 3 8 7 5 1 .
 . 3 . . 5 . . . 9
 2 . . . 7 . 3 . . 
 7 . . 6 . . . 8 2

Claudia