Skip to content →

Tag: puzzle

sudoku mania

Published June 26, 2005 by lievenlb


I never pay
much attention to the crossword-puzzle page of our regular newspaper DeMorgen. I did notice that they
started a new sort of puzzle a few weeks ago but figured it had to be
some bingo-like stupidity. It wasn’t until last friday that I had a
look at the simple set of rules and I was immediately addicted (as I am
mostly when the rules are simple enough!). One is given a 9×9 grid
filled with numbers from 1 to 9. You have to fill in the full grid
making sure that each number appears just once on each _horizontal
line_, on each _vertical line_ and in each
of the indicated 3×3 subgrids!

It is amazing how quickly one learns
the basic tricks to solve such _sudoku_s. At first, one plays by
the horizontal-vertical rule trying to find forbidden positions for
certain numbers but rapidly one fails to make more progress. Then, it
takes a while before you realize that the empty squares on a given line
in a 3×3 subgrid cannot be filled with any of the numbers already
present in the 3×3 subgrid. Easy enough, but it takes your
sudoku-experience to the next level. Anther simple trick I found useful
it to keep track how many times (from 0 to 9) you have already filled
out a given number. If it is 9, you may as well forget about this number
for elimination purposes and if it is 0 it will be hard to use it.
Optimal numbers to use are those that are already 4 to 6 times on the
board. And so on, and so on.

After having traced all back-copies
of the newspaper I ran out of sudokus but fortunately there is a
neverending (sic!) supply of them on the web. For example, try out the
archive of Daily
Sudoku, and there are plenty of similar sites as, no doubt, you’ll
find by Googling.

An intruiging fact I learned from my newspaper
is that there are exactly 6,670,903,752,021,072,936,960 different
filled-out Sudoku grids. You then think : this should be easy enough to
prove using some simple combi- and factorials until you give this number
to Mathematica to factor it and find that it is

$2^{20} \\times
3^{8} \\times 5 \\times 7 \\times 27704267971$

and hence has a
pretty big unexplained prime factor! This fact needed clarification, so
a little bit later I found this Sodoku
players forum page and shortly afterwards an excellent (really
excellent) Wikipedia on
Sudoku. There is enough material on that page to keep you interested
for a while (e.g. the fact that nxn sudoku is NP-complete).

Leave a Comment

snortGO

Published December 17, 2004 by lievenlb

Before I'm bogged down by the changes let me
return to the snortGO
puzzle. Recall that in snortGO black and white take
turns in placing a Go-stone on the board respecting the rule that no
stones of opposite colour may be adjacent. Javier is right that snortGo
with an empty starting board having an odd number of rows and columns is
a first player's win (place your first stone on the central spot and
respond to your opponent's moves by reflecting them along the
center).
Still, one can compose realistic end-game problems (as
in the previous snortGo post where the problem was : prove that the position is a first
player's win and indicate a winning move for both black and white).
To start the analysis let us remove all spots which are unavailable for
both players (as depicted in the top picture). Some of the remaining
spots are available to just one player (the central free spots and the
two in the top left corner). One counts that black has 5 such central
spots and white 4 (including the top left corner). So, all the genuine
action is happening in the three remaining corner regions for which one
can calculate the exact value following the rules of combinatorial game
theory where bLack is playing Left and white Right (so the free
spots for black add up to +5 whereas those for white add up to -4). It
is pretty easy to work out the exact values of the corner subgames

To find the value of the total game we have to sum up these
values which can either be done by hand (use this and this to get
started and use the inductive rule $G+H = \\{ G^L+H,G+H^L \\vert
G^R+H,G+H^R \\}$) or using combinatorial game suite to
verify that this sum is equal to $\\{ \\{ 3 \\vert 2 \\} \\vert -1 \\}$
which is a fuzzy game (that is, confused with zero or a first
player's win). To find the actual winning moves just try out the
Left (bLack) and Right (white) options in the corner games to find out
that there is a unique winning move for white and there are just 2
winning moves for bLack, all indicated in the pictures below.

Leave a Comment

quintominal dodecahedra

Published December 15, 2004 by lievenlb


A _quintomino_ is a regular pentagon having all its sides
colored by five different colours. Two quintominoes are the same if they
can be transformed into each other by a symmetry of the pentagon (that
is, a cyclic rotation or a flip of the two faces). It is easy to see
that there are exactly 12 different quintominoes. On the other hand,
there are also exactly 12 pentagonal faces of a dodecahedron
whence the puzzling question whether the 12 quintominoes can be joined
together (colours mathching) into a dodecahedron.
According to
the Dictionnaire de
mathematiques recreatives this can be done and John Conway found 3
basic solutions in 1959. These 3 solutions can be found from the
diagrams below, taken from page 921 of the reprinted Winning Ways for your Mathematical
Plays (volume 4) where they are called _the_ three
quintominal dodecahedra giving the impression that there are just 3
solutions to the puzzle (up to symmetries of the dodecahedron). Here are
the 3 Conway solutions

One projects the dodecahedron down from the top face which is
supposed to be the quintomino where the five colours red (1), blue (2),
yellow (3), green (4) and black(5) are ordered to form the quintomino of
type A=12345. Using the other quintomino-codes it is then easy to work
out how the quintominoes fit together to form a coloured dodecahedron.

In preparing to explain this puzzle for my geometry-101 course I
spend a couple of hours working out a possible method to prove that
these are indeed the only three solutions. The method is simple : take
one or two of the bottom pentagons and fill then with mathching
quintominoes, then these more or less fix all the other sides and
usually one quickly runs into a contradiction.
However, along the
way I found one case (see top picture) which seems to be a _new_
quintominal dodecahedron. It can't be one of the three Conway-types
as the central quintomino is of type F. Possibly I did something wrong
(but what?) or there are just more solutions and Conway stopped after
finding the first three of them…
Update (with help from
Michel Van den Bergh) Here is an elegant way to construct
'new' solutions from existing ones, take a permutation $\\sigma
\\in S_5$ permuting the five colours and look on the resulting colored
dodecahedron (which again is a solution) for the (new) face of type A
and project from it to get a new diagram. Probably the correct statement
of the quintominal-dodecahedron-problem is : find all solutions up to
symmetries of the dodecahedron _and_ permutations of the colours.
Likely, the 3 Conway solutions represent the different orbits under this
larger group action. Remains the problem : to which orbit belongs the
top picture??

Leave a Comment

Elkies’ puzzles

Published November 24, 2004 by lievenlb

Noam D. Elkies is a
Harvard mathematician whose main research interests have to do with
lattices and elliptic curves. He is also a very talented composer of
chess problems. The problem to teh left is a proof game
in 14 moves. That is, find the UNIQUE legal chess game leading to the
given situation after the 14th move by black. Elkies has also written a
beautiful paper On Numbers
and Endgames applying combinatorial game theory (a la Winning
Ways!) to chess-endgames (mutual Zugzwang positions correspond to zero
positions) and a follow-up article Higher Nimbers in pawn
endgames on large chessboards. Together with Richard Stanley he wrote a
paper for the Mathematical Intelligencer called The Mathematical
Knight which is stuffed with chess problems! But perhaps most
surprising is that he managed to run his own course on Chess and
Mathematics!

Leave a Comment

25 years monstrous moonshine

Published April 21, 2004 by lievenlb

Writing a survey paper is a highly underestimated task. I once
tried it out with \’Centers of generic division algebras : the
rationality problem 1965-1990\’ and it took me a lot of time and that
was on a topic with only 10 to 15 key papers to consider… The task of
writing a survey paper on a topic with any breadth must be much more
difficult. Last week, Terry Gannon posted a survey paper on the arXiv :
Monstrous Moonshine : The first twenty-five years
which gives a very readable introduction to this exciting topic. It has
a marvelous opening line :

It has been approximately
twenty-five years since John McKay remarked that

196 884 = 196 883 +
 1

Anyone who is puzzled by this line (“So what?”)
should definitely have a go at this paper! Still not convinced? Here is
the second sentence :

That time has seen the discovery of
important structures, the establishment of another deep connection
between number theory and algebra, and a reinforcement of a new era of
cooperation between pure mathematics and mathematical
physics.

For the remaining sentences (quite a few, the paper
is 33 pages long) I happily refer you to the paper.

Leave a Comment