How many Sudoku puzzles can be created?
The Sunday Nation
Nairobi,
04 August 2013
The greatest mistake that many make about Sudoku is to assume that solving it
requires mathematical manipulations. Yet the puzzle only requires a
careful analysis of the patterns of the numbers. It could be equally
interesting if the numbers 1-to-9 were replaced with the letters
A-to-I…or even pictures of nine different fruits!
Luke Kiminda understands this and I suspect he enjoys solving Sudoku
because he is wondering how many correct puzzles can be constructed
without repetition. Perhaps he is worried that a day will come when the
newspapers will start repeating thus ending his enjoyment abruptly!
Getting the answer to that question requires some fairly complicated
mathematics. Let me illustrate: how many times can the digits 1-to-9 be
arranged? One pattern is 1, 2, 3, 4, 5, 6, 7, 8, 9; another one is 1, 2,
3, 4, 5, 6, 7, 9, 8; and so on. If you tried listing all of them, you
I’d be at it for a very long time.
So let us devise a mathematical formula. Suppose there were just last
two digits 8, and 9. There are only two possible patterns: 8, 9 and 9,
8. What if there were the last three, 7, 8, and 9? Each one of them can
appear first just once and for each such appearance, there are two
possibilities for the remaining two numbers. That is; if we start with
9, we can have the sequences 9, 7, 8 and 9, 8, 7. The same can be done
when starting with 7 and with 8.
Therefore the total number of patters when there are three digits is 3 x
2 = 6. If there were four, it is easy to see that there would be 4 x 3 x
2 = 24 sequences…and so on. So, the nine numbers from 1-to-9 can be
arranged 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 = 362,880 times.
Thus when composing (not solving!) a Sudoku puzzle, the composer has
362,880 ways of filling up the first 3 x 3 grid, say, the one at the top
left hand corner.
Now, from the rules of Sudoku, it is clear that the entries in the 3 x 3
grids lying diagonally across from top left to bottom right do not
restrict one another. Thus the composer is free to fill these with any
pattern. That is there are 362,880 possibilities for each. Thus the
total for the three comes to 362,880 x 362,880 x 362,880 =
47,784,725,839,872,000 – approximately 48 quadrillion possibilities! In
case you have forgotten, a quadrillion is number with 16 zeroes.
But that’s not all: we’ve only counted three grids out of the nine.
The remaining six
have restrictions that make the calculation even more complicated.
Bertram Felgenhauer and Frazer Jarvis have done the full working and
found that there are 6,670,903,752,021,072,936,960 possible puzzles – or
over 6,670 billion-billions!
However, this number reduces significantly when symmetries are removed.
For example, rotating the whole puzzle through 90 degrees gives a new
puzzle which is, in reality, just a repeat. Same can be said about
mirror reflections, number swaps etc.
After doing this clean up, Felgenhauer and Jarvis arrive at
5,472,730,538 – or about 5.5billion. Now that’s a number that we can
relate to! But it is still very large. Each of all the 7,000 daily
newspapers in the world can publish a different Sudoku every day for the
next 2,140 years!
Therefore, Luke has nothing to worry about: a repeat Sudoku in his
lifetime is more likely to arise from an editorial oversight than an
exhaustion of puzzles.
 |
 |