One

cannot fight fashion… Following ones own research interest is a

pretty frustrating activity. Not only does it take forever to get a

paper refereed but then you have to motivate why you do these things

and what their relevance is to other subjects. On the other hand,

following fashion seems to be motivation enough for most…

Sadly, the same begins to apply to teaching. In my Geometry 101 course I

have to give an introduction to graphs&groups&geometry. So,

rather than giving a standard intro to graph-theory I thought it would

be more fun to solve all sorts of classical graph-problems (Konigsberger

bridges, Instant

Insanity, Gas-

water-electricity, and so on…) Sure, these first year

students are (still) very polite, but I get the distinct feeling that

they think “Why on earth should we be interested in these old

problems when there are much more exciting subjects such as fractals,

cryptography or string theory?” Besides, already on the first day

they made it pretty clear that the only puzzle they are interested in is

Sudoku.

Next week I’ll have to introduce groups and I was planning to do

this via the Rubik

cube but I’ve learned my lesson. Instead, I’ll introduce

symmetry by considering micro-

sudoku that is the baby 4×4 version of the regular 9×9

Sudoku. The first thing I’ll do is work out the number of

different solutions to micro-Sudoku. Remember that in regular Sudoku

this number is 6,670,903,752,021,072,936,960 (by a computer search

performed by Bertram

Felgenhauer ). For micro-Sudoku there is an interesting

(but ratther confused) thread on the

Sudoku forum and after a lot of guess-work the consensus seems to be

that there are precisely 288 distinct solutions to micro-Sudoku. In

fact, this is easy to see and uses symmetry. The symmetric group $S_4$

acts on the set of all solutions by permuting the four numbers, so one

may assume that a solution is in the form where the upper-left 2×2

block is 12 and 34 and the lower right 2×2 block consists of the

rows ab and cd. One quickly sees that either this leeds to a

unique solution or so does the situation with the roles of b and c

changed. So in all there are $4! \\times \\frac{1}{2} 4!=24 \\times 12 =

288$ distinct solutions. Next, one can ask for the number of

_essentially_ different solutions. That is, consider the action

of the _Sudoku-symmetry group_ (including things such as

permuting rows and columns, reflections and rotations of the grid). In

normal 9×9 Sudoku this number was computed by Ed Russell

and Frazer Jarvis to be 5,472,730,538 (again,heavily using the

computer). For micro-Sudoku the answer is that there are just 2

essentially different solutions and there is a short nice argument,

given by ‘Nick70′ at the end of the above mentioned thread. Looking a bit closer one verifies easily that the

two Sudoku-group orbits have different sizes. One contains 96 solutions,

the other 192 solutions. It will be interesting to find out how these

calculations will be received in class next week…

# micro-sudoku

Published in featured