Skip to content →

Tag: puzzle

hints for micro-sudoku

As a
quick reply to last posts comment :

Another
interesting question: How many clues (numbers allready in the grid) do
we need a Sudoku puzzle to have in the beginning in order to obtain a
unique solution? Comment by A.R.Ray

At
least one student proved that in micro-Sudoku (on a 4×4 grid)
one needs just 4 hints to get any unique solution (and that 4 is
minimal). It is an application of the fact that the micro-Sudoku group
acts on the set of all solutions with just two orbits so one needs to
check just these two solutions…

Leave a Comment

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…

One Comment

sudoku mania (bis)

Situation : my first class this year, about 20
fresh(wo)men, their second class this year.

Me : Okay, who
did some mathematics this vacation?

(No response
obviously, even if they did, it’s not a cool thing to
admit…)

Me : Sure, let me rephrase the question :
who thought about solving a puzzle or played a strategic game this
vacation?

(No response, or… is there?….. a
timid question :

‘Does Sudoku
count????’

Me : Well, not really but okay
let’s rephrase the question : Who solved at least 1 Sudoku this
vacation?

IMMEDIATE RESPONSE : about three quarters of all
students waving their arms!

Me :
Oof…….Oh…….Yes??? (to an even more timid
student raising his arm)

‘Does doing half a Sudoku
also counts?’

It’s going to be a tough
semester…

Leave a Comment