Su Doku

Su Doku is usually played on a 9 by 9 board, divided into 3 by 3 cells. You can generalize this into playing on an M×M square board broken into non-overlapping rectangular cells, each containing M squares (an obvious question is to how define a puzzle where M is a prime number). The solution of the puzzle is to place M symbols on the board such that each row, column or cell contains each symbol exactly once, without moving the initial clues. Puzzles with M<9 are called Sub Dokus, those for M>9 are called Super Dokus.

Technorati tag: Su Doku

The mathematics of Su Doku

Introduction

The popular game of Su Doku throws up many mathematical challenges. A newbie might ask, "How do I make a start on this?" (warning: if you don't want to turn into an addict, turn the page now and go to the sports news). Every addict probably asks "Is there only one solution to this puzzle?" (answer: if there isn't then change your newspaper) or "Can I do this without pencil and eraser?" (answer: no easy way to establish this). An addict with more time on hand might wonder "How many possible puzzles can there be?" (answer: possibly more than the number of atoms in a glass of beer) or "What is the smallest number of clues possible?" (answer: not known, but suspected to be 17).

What's in these pages?

Tips: how to solve a Su Doku: If you want to make a start on solving these puzzles, there are many wonderful web sites which introduce and explain methods of solution. I point you to some sources, because it is pointless to reproduce them.
Simpler puzzles: There are smaller versions of Su Doku, which I call Sub Dokus. These involve 4×4 grids (the game is called Shi Doku), 6×6 grids (this is called Roku Doku) and even a 5×5 grid (called, obviously, Go Doku). These are "toy models" for working out conjectures about Su Doku, and also, as I discovered to my surprise, good ways of introducing deductive methods to young children.
Harder puzzles: There are Super Dokus, which are similiar puzzles on larger grids. The 15×15 grid became a bit of a thing in Bombay a couple of months ago. The 12×12 is the smallest one where there are two different variants possible: the cells could be either 6×2 or 4×3. This forces a generalization of the counting problems.
Prime puzzles: Su Doku on M×M grids where M is a prime number is quite a different beast. Some properties of these puzzles are explored here.
Related puzzles: Su Doku has cousins. The oldest is over two hundred years old, was invented by the Swiss mathematician Leanhard Euler, and is called Latin Squares. The most recent are substantially younger.
Challenges: A list of unsolved mathematical problems about this class of puzzles. At present this is a list that seems to interest only me, but maybe in that wide web out there others have related thoughts.
Results: Tables of known results. Now very incomplete, but maybe one day...

Suggestions

The last part of the Su Doku tips web page leads into the questions where frontline research begins. If you want to get a flavour of some of the methods used, then you might want to start with the page on Shi Doku. If you just want to see lists of known results (or check that yours has been cited) then move on to the page for experts. If you are tired of Su Doku and want newer puzzles, then explore the site deeper.

Dedication

There seems to be a raging debate (ok, I exaggerate) about whether Su Doku involves mathematics. I say yes, yes and yes; and what I say thrice is true. Talking of which, I'm not the only person who wishes Martin Gardner was still writing for the Scientific American in the age of Su Doku. You will too, if you read through the rest of these pages on recreational mathematics, and compare them to the superb work he did on the Rubik Cube. These web pages are dedicted to that combination which introduced half the world to the joys of recreational maths (ok, I exaggerate, but not by much): Martin Gardner and his monthly column "Mathematical Games".