Sudding Sudoku! How long can it go on? (answer: a few billion years more)
Flipping heck, now The Times is offering mobile sudoku - 10 games sent by text to your mobile for “only”£4.50. Excuse me? When the paper costs what, 60p? All that journalistic effort for naught, well, 15p?
The Guardian meanwhile on Friday had an ironic G2 with a puzzle on every page. How long can this madness go on? Let’s work it out.
How many games of 9×9 sudoku (9 3×3 boxes) are there? That’s easy. Each line must be unique - can’t repeat a number in the same position as a line above. So for the first row you have 9×8x7×6x5×4x2×1 = 9! (9 factorial) possibilities = 362,880 possible first rows. Second row you have 8! possibilities - you can mix the numbers up but there are nine possiblities already taken by the row above.
(If you find this too hard, imagine a 2×2 grid: only two ways to lay that out in the top row. Then the bottom row is decided. Then imagine a 3×3 grid: six ways to lay out the top row - 123, 132, 213, 231, 312, 321. Choose any of those - say, 123, For the next row, you can’t do 123, but you can do 213, 231, 321, 312. For the final row there’s only one way to do it. OK? That’s the basic principle.)
Back to the 9×9. Third row, 7! possibilities. And so on. Total number of sudoku 9×9 games: (9!)! = 9!.8!.7!.6!.5!.4!.3!.2! = 1,834,933,472,251,090,000,000** (1,834 billion billion or so) which I’m afraid means we might have to wait until some time near the heat death of the universe before daily papers run out of grids. And that’s assuming they don’t repeat themselves between the nasty computer-generated ones and the environmentally-friendly hand-picked ones; is anyone checking this? I mean, come on! They might be nicking each others’ ideas here, which would never do.
More interesting question: how few numbers do you need to solve a grid? For example the “Easy” grid in Friday’s Independent has 30; intermediate, 27; advanced, 28. So it’s somewhere less than half the 81 of the grid, but I suspect that each number has to appear at least once. (Though you could imagine a situation where a number doesn’t appear but the grid is uniquely solvable… eg a grid with all the 9s left out. )
The game itself is a good time-waster, but I prefer getting into the mathematical underbelly of things like this. What’s its closest mathematical relation? Topology? Field theory? I’m sure at least one reader out there could tell us.
* on second thoughts, it must be less than that, because you’re constrained in what you can put in the first three numbers of the second row by the first three numbers of the top row. And so on. Which probably takes the odd billion-fold possibilities out. Even so, you’re still looking at the Earth being engulfed by the sun before they run out of grids. And that’s without the Indie’s Saturday hexadecimal version.
- These posts might be related (the database thinks..):
- Sudoku trivia.. what's the least numbers for a solvable grid without guesses? (17 May 2007; score: 70.05%)
- One good thing I'll say about thelondonpaper: its sudoku ranks (20 November 2006; score: 51.57%)
- Meet the naked triplet and fishy cycles: sadly, they're for solving sudokus (12 December 2007; score: 48.87%)
![[Valid RSS]](wp-includes/images/valid-rss.png "Validate my RSS feed"){kind=small}
May 14th, 2005 at 9:46 am
I don’t know the maths behind it, but there is definitely a minimum number of numbers required if you want it to be solvable without any guessing. The Telegraph’s one yesterday (someone sent it to me) seems to require two guesses to solve it, at least if you make the obvious first guess - it may only require one if you pick the right square. There are of course all kinds of rotational and refletive symmetries in the grid and you can of course swop any pair of numbers, i.e. replace all the 8s with 2s and vice versa.
Writing a program to solve them was quite fun though! Though the CSS to make the grid look pretty was probably harder :-) I wonder if someone will be silly enough to start offering cash prizes…..
May 15th, 2005 at 10:53 pm
Hadn’t heard of this. Then, in a week, both yourself and my second-favourite web comic mention it.
http://www.frozenreality.co.uk/comic/bunny/index.php?id=255
June 11th, 2005 at 8:05 pm
This is nonsence. Your way of working out Sudoku variations doesnt take into account the 3X3 grid system nor the fact that you can only have 9 of each digit. You have worked out the number of ways of inserting ANY number of the digits 1-9 into the 81 square grid - example - your answer inclues 81 9s!!! Clearly not right. The maths required to work this out is actually very complicated indeed! (and No, I dont know it!)
June 11th, 2005 at 10:02 pm
Yes, you’re right - I overestimated it by quite a lot. I did work out the correct number on the back of an envelope, but then lost the envelope.
OK, try again.
9! for the first row.
For the second row: choice of 6 numbers for first position (because can’t use any of the three in the triple above it), 5 for the next, then 4.. = 6!
For the third row, choice of 3 numbers for the first position (none of the six used already in the 2×3 square above), 2 for the next, then only one = 3!
Third row, fourth position: same again (ie 6 ways to arrange the three numbers in the second “box”); third row seventh position, three numbers to choose from which can be ordered any of 3! ways. So 3!.3!.3! = 6.6.6.
For the fourth row, in the first position, there’s the choice of 6 numbers (ie none of the three used in the column above). For the second position, 9 - 3 -1 = 5 choices. Fourth row third position - 4 choices. And so on. So the fourth row has 5! choices.
Fifth row. Can only choose from 9 - 4 - 2 = 3 numbers in the first position.
.. oh something like this. Sorry, can’t take it any further just now. But does this help?
April 7th, 2006 at 1:39 pm
I am addicted to Sudoku! I made an inventory of methods for solving even the most difficult Sudoku. Start with looking for duo’s, it’s an eye opener!
Check http://www.sudokuhints.nl/en/ for details.
Good luck!
March 26th, 2007 at 10:55 am
if you are into Sudoku you shall check out Kakuro which is a new puzzle game that’s getting popular lately :-)