All entries for Friday 13 May 2005
May 13, 2005
Many people think the maths is a pretty closed field – that there aren't really many open questions that can be appreciated by people with little training in the field.
If you've been reading newspapers (instead of, er, revising…) recently, you will have found what we can loosely term Sudoku Wars. In a recent, short period of time, more or less all the major newspapers, from the Guardian to the Telegraph to the Sun, have taken on this rather obscure Japanese puzzle. Today, the Guardian had one puzzle to every page of their G2 supplement.
Quite possibly this mania will blow off in a week or so.
If you don't know what sudoku is…
Basically, you have a 9×9 grid that is further divided into 9 3×3 smaller squares. The trick is to, given a number of initial hints, fill up the grid with digits 1–9 so that:
- Every subgrid contains all 9 digits.
- Every row contains all 9 digits.
- Every column contains all 9 digits.
Fun, eh? Ok, it's more interesting that it sounds. It's reasonably easy to think of an algorithm to solve it – simple trial and error can work. But it has been proven that the puzzle is NP-Complete – that there is unlikely that there is an efficient (i.e. scaling according to some polynomial law) way to do it. In short, it's a fair bet that a Sudoku puzzle will take you a long, long time…
(Part of the neatness of NP-Complete problems is that one fast solution can be used to solve other problems quickly as well. So if you do find a really fast solution, make sure YOU COME STRAIGHT TO ME, AND TELL NO ONE ELSE. )
Erm… In any case… A lot of other questions of Sudoku are interesting, and unanswered. For example, a newspaper cannot just randomly toss together a lot of numbers, and hope that it makes a decent sudoku puzzle. Some patterns of initial conditions give NO solution. Others allow several solutions. For example, if we want to fit the corners of a rectangle with two different numbers, unless we get a hint about one of them, the two possible combinations can be substituted for each other.
So, what's the minimum number of hints we need to give to get a single unique solution? We don't know. The best that has been found is 18. But we really don't know. (Or at least, I don't know.)
In fact, we don't even know how many solutions there are for a blank grid – how many ways can we fill a standard 9×9 grid whilst not breaking the rules of Sudoku?
Maths. Scratch the surface, and we know almost nothing.