Alex's Adventures in Numberland - Alex Bellos [93]
Completing any puzzle is immensely gratifying to the ego, but part of the extra allure of completing a Sudoku is the inner beauty and balance of the perfect Latin square that gives it its form. Sudoku’s success is testament to an age-old, cross-cultural fetish for number squares. And unlike many other puzzles, its success is also a remarkable victory for mathematics. The puzzle is maths by stealth. Although Sudoku contains no arithmetic, it does require abstract thought, pattern recognition, logical deduction and the generation of algorithms. The puzzle also encourages an aggressive attitude towards problem-solving, and fosters an appreciation of mathematical elegance.
For instance, as soon as you understand the rules of Sudoku, the concept of a unique solution is remarkably clear. For every pattern of numbers in the grid at the start, there is only one possible final arrangement for the numbers in the empty spaces. However, it is not the case that every partially filled grid has a unique solution. It is perfectly possible that a 9 × 9 square with some numbers filled in has no solutions, just as it is perfectly possible that it has many solutions. When Sky TV launched a Sudoku show, they drew what they claimed was the world’s largest Sudoku by cutting a 275 × 275ft grid out of a chalk hillside in the English countryside. However, the given numbers were placed in such a way that there were 1905 valid ways to complete the square. The roclaimed largest Sudoku did not have a unique solution, and therefore was not a Sudoku at all.
The branch of mathematics that involves the counting of combinations, such as all the 1905 solutions to Sky TV’s faux Sudoku, is called combinatorics. It is the study of permutations and combinations of things, such as grids of numbers, but also, famously, the schedules of travelling salesmen. Let’s say, for instance, that I’m a travelling salesman and I have 20 shops to visit. In what order should I visit them so that my total distance is the shortest? The solution requires me to consider all the permutations of paths between all the shops, and is a classic (and extremely difficult) combinatorial problem. Similar problems arise throughout business and industry, for example in scheduling flight departure times at airports or having an efficient postal sorting system.
Combinatorics is the branch of maths that most consistently deals with extremely high numbers. As we saw with magic squares, a small set of numbers can be rearranged in an astonishingly large number of ways. Though they both share square grids, there are fewer Latin squares than magic squares for the same size of grid, though the number of Latin squares is still colossal. The number, for example, of 9 × 9 Latin squares is 28 digits long.
How many possible Sudokus are there? If a 9 × 9 Latin square is to qualify as a finished Sudoku grid, the 9 subsquares must also include every digit, and this reduces the total of Sudoku-ready 9 × 9 squares to 6,670,903,752,021,072,963,960. Many of these grids, however, are different versions of the same square when reflected or rotated (as I showed with the 3 × 3 magic square on chapter 6). Eliminating squares that are rotations and reflections, the number of distinct possible finished Sudoku grids is about 5.5 billion.
Still, this is not the total number of possible Sudokus, which is much larger since each finished grid will be the solution to many Sudokus. For example, a Sudoku in a newspaper has one unique solution. Once you fill in one of the squares, however, you are creating a new grid with a new set of givens, in other words a new Sudoku with the same unique solution, and so on for each square you fill in. So if a Sudoku has, say, 30 given numbers, then we will be able to create another 50 Sudokus with the same unique solution until we complete the grid. (That’s one new Sudoku for each extra number, until there are 80 givens in the 81-square grid.) Finding the total number of Sudokus is