# Tag: sudoku

Below an up-till-now hidden post, written november last year, trying to explain the long blog-silence at neverendingbooks during october-november 2007…

A couple of months ago a publisher approached me, out of the blue, to consider writing a book about mathematics for the general audience (in Dutch (?!)). Okay, I brought this on myself hinting at the possibility in this post

Recently, I’ve been playing with the idea of writing a book for the general public. Its title is still unclear to me (though an idea might be “The disposable science”, better suggestions are of course wellcome) but I’ve fixed the subtitle as “Mathematics’ puzzling fall from grace”. The book’s concept is simple : I would consider the mathematical puzzles creating an hype over the last three centuries : the 14-15 puzzle for the 19th century, Rubik’s cube for the 20th century and, of course, Sudoku for the present century.

For each puzzle, I would describe its origin, the mathematics involved and how it can be used to solve the puzzle and, finally, what the differing quality of these puzzles tells us about mathematics’ changing standing in society over the period. Needless to say, the subtitle already gives away my point of view. The final part of the book would then be more optimistic. What kind of puzzles should we promote for mathematical thinking to have a fighting chance to survive in the near future?

While I still like the idea and am considering the proposal, chances are low this book ever materializes : the blog-title says it all…

Then, about a month ago I got some incoming links from a variety of Flemish blogs. From their posts I learned that the leading Science-magazine for the low countries, Natuur, Wetenschap & Techniek (Nature, Science & Technology), featured an article on Flemish science-blogs and that this blog might be among the ones covered. It sure would explain the publisher’s sudden interest. Of course, by that time the relevant volume of NW&T was out of circulation so I had to order a backcopy to find out what was going on. Here’s the relevant section, written by their editor Erick Vermeulen (as well as an attempt to translate it)

Sliding puzzle For those who want more scientific depth (( their interpretation, not mine )), there is the English blog by Antwerp professor algebra & geometry Lieven Le Bruyn, MoonshineMath (( indicates when the article was written… )). Le Bruyn offers a number of mathematical descriptions, most of them relating to group theory and in particular the so called monster-group and monstrous moonshine. He mentions some puzzles in passing such as the well known sliding puzzle with 15 pieces sliding horizontally and vertically in a 4 by 4 matrix. Le Bruyn argues that this ’15-puzzle (( The 15-puzzle groupoid ))’ was the hype of the 19th century as was the Rubik cube for the 20th and is Sudoku for the 21st century.
Interesting is Le Bruyn’s mathematical description of the M(13)-puzzle (( Conway’s M(13)-puzzle )) developed by John Conway. It has 13 points on a circle, twelve of them carrying a numbered counter. Every point is connected via lines to all others (( a slight simplification )). Whenever a counter jumps to the empty spot, two others exchange places. Le Bruyn promises the blog-visitor new variants to come (( did I? )). We are curious.
Of course, the genuine puzzler can leave all this theory for what it is, use the Java-applet (( Egner’s M(13)-applet )) and painfully try to move the counters around the circle according to the rules of the game.

Some people crave for this kind of media-attention. On me it merely has a blocking-effect. Still, as the end of my first-semester courses comes within sight, I might try to shake it off…

Ibrahim Belkadi, one of my first-year group theory students invented the micro-sudokube, that is, a cube having a solution to a micro-sudoku on all its sides such that these solutions share one row along an edge. For example, here are all the solutions for a given central solution. There are 4 of them with ${ a,b } = { 2,3 }$ and ${ c,d } = { 1,4 }$

The problem is : how many micro-sudokubes are there? Ibrahim handed in his paper and claims that there are exactly 32 of them, up to relabeling ${ 1,2,3,4 }$, so in all there are $32 \times 24 = 768$ micro-sudokubes.

The proof-strategy is as follows. Fix one side and use relabeling to put the solution on that side to be one of 12 canonical forms (see for example this post. Next, work out as above for each of these standard forms in how many ways it can be extended. A nice idea of Ibrahim was to develop a much better notation for micro-sudokubes than the above flattenet-out cube. He uses the fact that a micro-sudokube is entirely determined by the solutions on two opposite sides (check this for yourself). Moreover, fixing one side determines one-half of all the neighboring sides. His notation for the 4 solutions above then becomes

and he can then use these solutions also in other standard form (the extra notation using the names A,B,C 1-4 for the 12 canonical forms).

Via the Arcadian functor I learned of the existence of the Sudokube (picture on the left).

Sudokube is a variation on a Rubik’s Cube in which each face resembles one-ninth of a Sudoku grid: the numbers from one to nine. This makes solving the cube slightly more difficult than a conventional Rubik’s Cube because each number must be in the right place and the centre cubies must also be in the correct orientation.

A much more interesting Sudoku-variation of the cube was invented two weeks ago by one of my freshmen-grouptheory students and was dubbed the mini-sudokube by him. Here’s the story.

At the end of my grouptheory course I let the students write a paper to check whether they have research potential. This year the assignment was to read through the paper mini-sudokus and groups by Carlos Arcos, Gary Brookfield and Mike Krebs, and do something original with it.

Mini-Sudoku is the baby $2 \times 2$ version of Sudoku. Below a trivial problem and its solution

Of course most of them took the safe road and explained in more detail a result of the paper. Two of them were more original. One used the mini-sudoku solutions to find solutions for 4×4 sudokus, but the most original contribution came from Ibrahim Belkadi who wanted to count all mini-sudokubes. A mini-sudokube is a cube with a mini-sudoku solution on all 6 of its sides BUT NUMBERS CARRY OVER CUBE-EDGES. That is, if we have as the mini-sudoku given by the central square below on the top-face of the cube, then on the 4 side-faces we have already one row filled in.

The problem then is to find out how many compatible solutions there are. It is pretty easy to see that top- and bottom-faces determine all squares of the cube, but clearly not all choices are permitted. For example, with the above top-face fixed there are exactly 4 solutions. Let ${ a,b } = { 1,4 }$ and ${ c,d } = { 2,3 }$ then these four solutions are given below

Putting one of these solutions (or any other) on a $4 \times 4$-Rubik cube would make a more interesting puzzle, I think. I’ve excused Ibrahim from having to take examination on condition that he writes down what he can prove on his mini-sudokubes by that time. Looking forward to it!

Recently, I’ve been playing with the idea of writing a book for the general public. Its title is still unclear to me (though an idea might be “The disposable science”, better suggestions are of course wellcome) but I’ve fixed the subtitle as “Mathematics’ puzzling fall from grace”. The book’s concept is simple : I would consider the mathematical puzzles creating an hype over the last three centuries : the 14-15 puzzle for the 19th century, Rubik’s cube for the 20th century and, of course, Sudoku for the present century.

For each puzzle, I would describe its origin, the mathematics involved and how it can be used to solve the puzzle and, finally, what the differing quality of these puzzles tells us about mathematics’ changing standing in society over the period. Needless to say, the subtitle already gives away my point of view. The final part of the book would then be more optimistic. What kind of puzzles should we promote for mathematical thinking to have a fighting chance to survive in the near future?

Here a list of pdf-files of NeverEndingBooks-posts on games, in reverse chronological order.

It has
been a difficult design decision, but I‚Äôm going to replace the LaTeXRender WordPress
Plugin
for mathML as the
default TeX-interface for NeverEndingBooks. I will keep LaTeXRender on
standby as I may have to use exotic packages or commands that iTeX does
not deliver, but for most math-related posts, MathML will do the job
nicely (as the n-category
cafe
shows every day (or even more often)). Not that I stopped being
a dilettante but I’m going to do most of my writings (including
blog-posts) using Scrivener (more on this
another time) and Scrivener supports MultiMarkdown and allows exporting to LaTeX and XHTML (using MathML).

I could never have pulled this off in such a short time without Jacques Distler
more or less on constant stand-by (thanks Jacques!). Looking at the
times his emails were send I have no idea in which time zone he lives
(let alone sleeps…). So, here a walk-through the changes :

As
I’m on WP 2.0.5 I’ll start with Frederick’ post. He tells me I have to install first the itex2MML binary as
explained by
Jacques
but I find that there is more recent
material
and follow the readme. There is a Mac OSX binary but it’s not clear
for what processor (PPC/Intel/Binary) but a quick mail to Jacques learns
me that it’s PPC which is fine by me but on the spot he puts a
the binary, copy it to /usr/local/bin and make sure its chmodded
755.

Back to Frederick’s post, download and install the plugin itexToMML.php in the usual way
(fortunately I spot just in time that I have to change one line saying
where my itex2MML binary is (in Frederick’s file it is NOT the default
location)). You can verify whether the plugin and itex2MML do what they
are supposed to do by typing a LaTeX-command in a post and save it. The
output will not produce the desired formula but have a look at the
source file and see whether there is some mathML code in it. If so,
fine! If not, go back and check everything.

If this works, it is
“merely” a problem of getting your mathML served. Frederick suggests
to unpack wordpress_mathML.zip in the wp-includes directory (but you
better make sure you have made a copy of the original class.php and
functions-formatting.php files. In the end I decided against this
approach (that is, to replace only the functions-formatting.php but NOT
the class.php file). If you have two or more themes you want to
maintain, it is probably better to change the headers (because this is
what we have to do to get mathML served) only in those themes which are
XML-sound. In my case, the Command Line Interface theme most certainly is NOT!!!).

Go to your
theme-files and look for the header.php (or similar) file and replace
this post
within php-tags. If you can go to your blog-page then you
are in good shape and things should work well (apart possibly from
layout considerations, see below). Of course, in my case i was greeted
by ” XML “yellow screen of death” (as Jacques calls
it) and I was convinced I did something wrong, so I tried out several
useless things for a couple of hours before it dawned on me that the
reason might just be that my blog-files were not valid XHTML (and the
new headers are very demanding on serving only well-form XHTML). I had
to modify all changes I made to sidebars etc. as well as rewrite parts
of my first posts (I used to take a rather liberal view on writing
blog-posts, writing a mixture between Markdown and improvised HTML and
in the process was very lax about closing IMG-tags and the likes).
But after some time and numerous corrections to the files I got the
main-page up and running (and even had the mathML served as a readable
formula) apart from the fact that I barely recognized my own site.

I printed out source files of the page with and without changed
headers and couldn‚Äôt find a difference. So, it had to do with the
CSS-style files, but why on earth would the new headers be picky about
CSS? But as a last resort, after narrowing the search down to one
will be remembered for quite some time :

A fascinating
question. The answer is that it *is* following the CSS directive, but
in XHTML, ‘body’ is not what you think it is. ‘body’ is just big enough
to contain its content. It does not fill the viewport. ‘html’ fills the
viewport. The solution (a solution) is described in
http://golem.ph.utexas.edu/~distler/blog/archives/000203.html

Many hours later, I still haven‚Äôt got a clue what
this is all about, but I blindly followed the hint and surely all
problems vanished. In short, another day wasted in front of a
computer-screen.

At the moment I’m back to old headers and
will not be writing mathML for some time as I have the vast job ahead to
validate all my previous posts to XHTML-standards (if not you would see
more yellows screens of death than anything else. So, here‚Äôs the
strategy I’ll be taking in the weeks ahead (I’ll sleep on it tonight
so if any of you think there is a better way, reply quickly)

• rewrite each and every post in proper MultiMarkdown using iTeX for
the most common math and only resorting to LaTeXRender for exotic things
(such as Sudoku, Chess, Dvonn) and run these posts through Markdown
(to get basic HTML and all links in place).
files to the WP-database (so that in the CLI-interface you will be able
command line intended after all).
• in the process change all
so).

Clearly, this is a work that will take a couple of
weeks but it may be fun to reread these old posts and possibly add new
information about the subjects. When I‚Äôm making these changes, I‚Äôll
use the new headers so if you are using a smart browser look out for the
yellow screens. When they happen, either use a dumb browser (such as
Safari) or go into CLI-interface mode where everything should still
work. I plan to start with the oldest posts as this seems more fun to
me.

Here is
a ‘difficult but not unsolvable’ Sudoku from David Eppstein‘s paper Nonrepetitive paths and cycles
in graphs with application to Sudoku
.

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |. | | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. | | |8|3| |9| |2| |. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1| | | | |3|. \end{sudoku-block}y1$

As always I try to solve
Sudokus without having to use backtracking (that
is, making a guess and working from there on to a solution or a
contradiction in which case one uses the other option). Clearly, this is
not well defined. When one starts solving Sudokus one often resorts to
backtracking but after a while one discovers rules which seem to avoid
backtracking (but in a sense are still). For example, if two cells in a
same block (or row or column) can only be filled with two numbers one
can use this fact by forbidding other numbers to occupy those cells.
However, this is a mini-backtracking strategy. Still, I allow all such
rules. More precisely, any formal rule is non-backtracking in my
dictionary. In Eppstein’s paper there is a good summary of the rules
most people apply when starting a Sudoku. He calls them the ‘local
rules’. Here they are

• If a digit x has only one remaining
cell that it can be placed in, within some row, column, or square, then
we place it in that cell. Any potential positions of x incompatible with
that cell (because they lie in the same row, column, or square) are
removed from future consideration.
• If a cell has only one
digit x that can be placed in it, we place x in that cell. Incompatible
positions for x are removed from future consideration.
• If
some three cells, formed by intersecting a row or column with a square,
have three digits whose only remaining positions within that row,
column, or square are among those three cells, we prevent all other
digits from being placed there. We also remove positions for those three
forced digits outside the triple but within the row, column, or square
containing it.
• If the cells of a square that can contain a
digit x all lie in a single row or column, we eliminate positions for x
that are outside the square but inside that row or column. Similarly, if
the cells that can contain x within a row or column all lie in a single
square, we eliminate positions that are inside that square but outside
the row or column.
• If two digits x and y each share the same
two cells as the only locations they may be placed within some row,
column, or square, then all other digits must avoid those two cells.
• If the placement of digit x in cell y can not be extended to a
placement of nine copies of x covering each row and column of the grid
exactly once, we eliminate cell y from consideration as a placement for
x.
• If the placement of a digit x in cell y within a single
row, column, or square can not be extended to a complete solution of
that row, column, or square, then we eliminate that placement from
consideration.

But even if one manages to use all
these rules (and frankly I only use a subset) one might get stuck. I
don’t know how many cells you can fill in the above problem with these
local rules, I’m afraid I only managed $5$… At such
moments, the bivalue Sudoku-graph may come in handy. Eppstein defines
this as follows

In this graph, we create a vertex
for each cell of the Sudoku grid that has not yet been filled in but for
which we have restricted the set of digits that can fill it to exactly
two digits. We connect two such vertices by an edge when the
corresponding two cells both lie in a single row, column, or square, and
can both be filled by the same digit; the label of the edge is the
digit they can both be filled by.

Eppstein then goes
on to define new rules (each of which is a mini-backtracking strategy)
which often help to crack the puzzle. Here are Eppstein’s ‘global
rules’

• If an edge in the bivalue graph belongs to a
nonrepetitive cycle, the digit labeling it must be placed at one of its
two endpoints, and can be ruled out as a potential value for any other
cell in the row, column, or square containing the edge.
• If
the bivalue graph has a cycle in which a single pair of consecutive
edges has a repeated label, that label can not be placed at the cell
shared by the two edges, so that cell must be filled by the other of its
two possible values.
• If the bivalue graph contains two
paths, both starting with the same label from the same cell, both
ending at cells in the same row, column, or square, and such that in the
two ending squares the values not occurring on the incident edge labels
are equal, then the cell at the start of the paths can not be filled by
the start label of the paths, and must be filled by the other of its two
possible values.

For example, in the above problem it
is not hard to verify that the indicated places X,Y and Z form a
nonrepetitive cycle in the bivalue graph so applying the first global
rule we have two choices of filling these places (one leading to a
solution, the other to a contradiction)

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |. | | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. |X|Y|8|3| |9| |2|Z|. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1| | | | |3|. \end{sudoku-block}y2$

In fact, it turns out
that making this choice is enough to solve the puzzle by simple local
rules. So, if I change the original puzzle by filling in the cell X

$\begin{sudoku-block} |5| | | | |1| | |8|. | | | | | | |6| | |. | | | | |6|2|5|7| |. | |9| |2| |5|1| | |. | | |4| |1| |3| | |. |6| |8|3| |9| |2| |. | |7|6|9|8| | | | |. | | |5| | | | | | |. |8| | |1| | | | |3|. \end{sudoku-block}y3$

you will have no problem
solving the puzzle.

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…

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…

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

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…