There is great satisfaction to be had in completing the puzzles using a combination of logic, observation and ingenuity, writes Patrick Fitzpatrick
Is there mathematics in sudoku? Well, yes and no. The short answer is that in spite of the use of numbers in sudoku, the puzzle doesn't have anything to do with being good with figures. But the long answer is more interesting.
No one who has picked up a newspaper or magazine in the last year can fail to be aware of sudoku. Contrary to popular belief, it wasn't invented in Japan. In fact, it was developed by Howard Garnes, in the US in the late 1970s, and its first public appearance was in the magazine Dell Pencil Puzzles and Word Games. It became hugely popular in Japan where the name sudoku means "numbers occur uniquely".
There is no reason why the grid has to be 9x9, although 4x4 is too easy and 16x16 probably too difficult to make it really popular.
The 9x9 grid seems to have the essential ingredients of "sufficient but not too much" complexity for a daily newspaper puzzle. There are 6,670,903,752,021,072,936,960 distinct grids, and to put that in context, if everyone in the world did one a day it would take us about three billion years to get through them all. There are certainly enough to keep the enthusiasts going for a while.
So let's assume we are given grid 1 to start and since it makes no difference what we use for the entries we can refer to them as symbols (they could be patterns or colours, for example, just as well as numerals).
The individual locations for the symbols are the squares in the grid, and we can see that each square belongs to exactly one row, one column, and one 3x3 box. We number the rows and columns from 1 to 9 and use the notation r1, , r9 and c1, , c9. Then we can refer to each square by its row and column number, so for example, we see a 7 in location r4c5. We also number the boxes from 1 to 9, row by row, from top left to bottom right, as b1, , b9. The aim is to complete the grid by placing the symbols 1-9 in the squares so that each symbol appears precisely once in each row, column and box.
Before we start though . . . we are, of course, relying on the compiler of the grid to have ensured that there is actually a solution for the given initial values. We are also implicitly assuming that there is only one solution; if there were more than one the puzzle would be invalid. No doubt the compiler has used a computer to make up the puzzle. The usual technique is to add initial entries successively and solve the resulting puzzles until the solution is unique.
Another thing that might strike us is why some grids have fewer initial values than others. Most newspaper puzzles start with between 25 and 30 given symbols. We might even ask for the smallest number of initial values that must be specified in order to ensure that the puzzle is valid. There is no definitive answer - the smallest known initial sets with unique solutions have size 17 but no one really knows for sure if every initial set of size 16 or less must lead to multiple solutions.
There are various methods we can employ to start solving a sudoku puzzle. Starting with grid 1 we may notice that the symbols 2, 7 and 8 are missing from r8 and we can conclude that the square r8c9 can only contain the symbol 2, because all the other symbols are ruled out by their presence in r8, c9 and b9. By the same technique we can then successively enter 8 in r8c5, 7 in r8c1, and 2 in r2c5. This gives grid 2.
The next step involves scanning the boxes left to right and top to bottom. For example, consider the pattern of 5s in grid 2 and consider b4. The 5s in r5 and r6 force the 5 in b4 to be in r4, while the 5 in c1 forces the 5 in b4 to be in c3. So we can enter the 5 in r4c3, as in grid 3.
After carrying out this analysis for each symbol 1-9 we arrive at grid 4, where we have also entered a 9 in r5c9. This requires a slightly more subtle form of the scanning argument. The 9s in c7 and c8 force the 9 in b6 to be in c9, and the 9 in r6 leaves two possible locations for it, namely, r4c9 and r5c9. However, the 9 in r6 means that the 9 in b5 must be in r4, either in r4c4 or r4c6. Although we can't be certain which of these is the correct location we can deduce that there cannot be a 9 in r4c9. Thus the 9 in b6 is in r5c9. A similar argument gives a 4 in r9c8.
Successive application of these two elementary steps is often sufficient to solve easy puzzles; for more difficult ones they eventually run out of steam and we then need to consider for each empty square what symbols it might contain - these form the candidates for that square. It's easy to do this, if a bit tedious. In fact, most sudoku experts would actually start with this step.
Grid 5 gives some of the candidate lists. In c6 we notice that squares r4c6 and r9c6 contain the identical lists 39. We deduce that these two squares must contain, between them, the symbols 3 and 9. It follows that we can eliminate 3 and 9 as candidates from the other squares in c6, and this immediately gives us a 2 in r6c6 and then, consequently, a 7 in r7c6. By the same argument for r7c7 and r9c7 we can eliminate 1s and 6s from c7 to get grid 6.
Now we can see that in b3 the symbol 6 appears as a candidate only in r1c8. This means that the 6 must appear in that square, and as a consequence we also get a 2 in r5c8 and arrive at grid 7. Extending the scanning technique a little further, we observe that since the 6 in b5 must appear in either r4 or r6, and the same goes for the 6 in b6, it follows, that the 6 in b4 must be in r5c1. As an alternative, to illustrate an extension of the technique in the previous paragraph we note that, in row 5, the squares r5c2, r5c3 and r5c7 contain, between them, only the candidates 1,3,7. We deduce that these three squares must contain those three symbols and so we can remove the 1 and 3 from r5c1, again giving us a 6 in that square.
The example can be completed using only the techniques illustrated (grid 8 - thanks to Alec Myles for checking my calculations). Although these do not make up an exhaustive toolkit for solving sudoku puzzles, they suffice for all but the most difficult ones. In the hardest examples we get to a stage where no further symbols can be entered and then we have to make a choice among the candidates in a certain square and see what happens. Suppose there is a square with two candidates.
We choose one and then continue with the solution until one of two things occurs: either we end up getting a contradictory solution (for example, with the same symbol in two different squares in a row) or we get stuck again. In the former case we have proved that our first choice was false and can then be certain that the other alternative was the correct one. On the other hand, if we get stuck again, we could make another choice and go on further, but this gets very complicated. At that point it is probably better to go back to where the original choice was made, choose a symbol from the candidate list in a different square and try to derive a contradiction (thereby proving that this choice is false and eliminating that symbol from the candidate list).
However, this process requires us to keep a record of the grid as it stands when the choice is first made, in order to go back to it later, and that makes such puzzles unsuitable for a daily newspaper.
So, is there mathematics in it? Yes, indeed. Finding a solution to a symbolic problem that satisfies certain well-defined constraints is one of the essential techniques of mathematical investigation. Sudoku is founded on Boolean algebra, and related to a wide variety of mathematical topics such as Latin squares, statistical designs, combinatorial optimisation, graph colouring, computational complexity, backtrack search, constraint programming, and error correcting codes.
What's the attraction? Why do so many people do sudoku? As has often been pointed out, it's certainly a good workout for the brain, but that can't be the only reason. We all know that exercise is good for us but how many of us do it regularly?
No, there is clearly something more going on. There is a great sense of achievement in completing the puzzles using a combination of logic, observation and ingenuity and that, in the end, is a peculiarly mathematical pleasure.
Patrick Fitzpatrick is associate professor of mathematics and dean of the College of Science, University College Cork