micro-sudoku

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…