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).