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…

Previous in series

Next in series