Search MAA Reviews:
Taking Sudoku Seriously: The Math behind the World's Most Popular Pencil Puzzle
Jason Rosenhouse and Laura Taalman
Publisher: Oxford University Press (2011)
Details: 226 pages, Paperback
Topics: Recreational Mathematics, Mathematics for the General Reader, Combinatorics
MAA Review[Reviewed by Mark Hunacek, on 01/10/2012]
Jason Rosenhouse seems to have gotten hold of an interesting idea, one that he has now successfully exploited in two books. His first, The Monty Hall Problem: The Remarkable Story of Math’s Most Contentious Brain Teaser, used that famous probability problem as the jumping-off point for a wide-ranging inquiry into various related topics. In this book, he and coauthor Laura Taalman, herself a coauthor of three other Sudoku-variation puzzle books as well as an article in the September 2007 issue of Math Horizons also entitled Taking Sudoku Seriously, have, instead of addressing a famous mathematical problem, turned their attention to a hugely popular puzzle, Sudoku. The common theme of both books — the “interesting idea” alluded to earlier — is to use one central problem to discuss a broad spectrum of topics in mathematics (and sometimes other disciplines as well).
In Monty Hall, for example, analysis of that problem (named after the host of a famous game show) and its variations led to discussion of topics in probability and other areas like psychology and philosophy. (Readers who don’t own the book but who would like to get a sense of what it is like should look at the article by Rosenhouse, Lucas and Schepler in the December 2009 issue of Mathematics Magazine.) In this second book, Rosenhouse and Taalman lead a Sudoku-related tour through topics in combinatorics, abstract algebra, graph theory, polynomials, and, perhaps most importantly, the nature of mathematics and mathematical reasoning in general.
Most people are probably are already familiar with the game of Sudoku, but it is easy enough to describe it quickly: one starts with a 9 × 9 square divided into 9 smaller 3 × 3 squares. The object is to place the numbers 1 through 9 in every row and column of the large square, using every number exactly once and also insuring that each of the smaller squares also contains the numbers 1 through 9, each appearing exactly once. The game begins with some of the squares already filled in; the player’s job is to fill in the remaining ones, consistent with these rules. In a “sound” Sudoku puzzle, this can be done in a unique way.
It has been said (by people not familiar with mathematics) that the game of Sudoku involves no mathematics. It is true, as the authors point out, that it involves no arithmetical calculations, but of course anyone with enough mathematical background to read MAA Reviews already knows that mathematics is not coextensive with arithmetic, and can quickly appreciate that Sudoku raises a number of interesting mathematical questions and touches on a variety of mathematical disciplines.
For example, a completed Sudoku grid is a Latin square, but not every 9 × 9 Latin square is a completed Sudoku grid because the “sub-square condition” may not be satisfied. Therefore, after an introductory chapter discussing solution methods for Sudoku and also discussing the nature of mathematical reasoning in general (complete with examples like the Königsberg Bridge problem), there are two chapters with Latin squares as their theme. In them, we learn about construction methods, orthogonal Latin squares, the classical problem of the 36 officers, and orthogonal Sudoku squares, along with a section explaining why people should care about this. These two chapters also discuss variations on classical Sudoku, such as “Latin-doku” (ignore the subsquares and just fill in the blanks so as to create a Latin square) and “Bomb-Sudoku” (ignore the subsquares but add the requirement that no two adjacent squares can contain the same number), and discuss a generalization of a Sudoku square called a Gerechte design (an n × n Latin Square that is divided into n regions of n squares each, with the property that no number appears more than once in any of the regions as well as in any row or column).
The next two chapters address issues connected with counting completed Sudoku grids. Specifically, chapter 4 talks about how to count completed Sudoku squares by first introducing some basic combinatorial ideas, applying them to the (much simpler) task of counting 4 × 4 Sudoku grids (or “Shidoku” grids, as the authors call them; these are used throughout the book to illustrate some of the mathematical ideas in a simpler setting) and then extending these ideas to the general 9 × 9 case, essentially giving an introduction (with many details either sketched or omitted) to work done by Felgenhauer and Jarvis that was published about five years ago. (In case you’re wondering, there are 6,670,903,752,021,072,936,960 possible completed Sudoku puzzles.)
Chapter 5 then extends these ideas by inquiring into the number of “fundamentally different” Sudoku squares, which leads naturally to abstract algebra entering the discussion via symmetry groups, group actions and Burnside’s lemma. This material, of course, like other material discussed in the book, is fairly serious mathematics, usually only taught to math majors at the junior or senior undergraduate level. Yet by proceeding slowly and clearly and omitting details and technical arguments as appropriate, Rosenhouse and Taalman do an excellent job of making the essence of these topics understandable to people with no particular mathematical background beyond that typically learned in high school. (Their discussion of what the phrase “abstract algebra” means, for example, and why one would want to study properties of a binary operation, is so nicely done that I stole some of it for the first day of the abstract algebra course I am teaching this semester.)
These are followed by three other chapters that continue the theme of connecting Sudoku problems with topics in mathematics. For example, in chapter 6, the authors begin with the interesting question of finding a “good” Sudoku puzzle — one that has a unique solution but is not (unlike, for example, a puzzle with all but one square filled in) completely trivial to solve. This, in turn, is quickly placed in the context of the mathematical theory of search algorithms. As might be expected, this chapter makes heavy use of computer calculations, but also takes time to talk about the interesting (and unsolved at the time of writing) question of what is the minimum number of clues that must be filled in in order to insure that there is a unique solution. For puzzles that are rotationally symmetric, the smallest known number is 18; if the symmetry condition is relaxed, the smallest known number is 17. (In a very recent development, Gary McGuire of University College Dublin has announced a computer-based proof that 17 really is the minimum number; author Rosenhouse has been quoted as saying the attitude toward the proof is one of “cautious optimism”. The reviewer thanks the editor of MAA Reviews for pointing this out to him.)
Chapter 7 returns to the subject of graph theory, last seen in the first chapter with the Konigsberg bridge problem, and explains the connection between Sudoku puzzles and graph colorings; the four-color problem is of course mentioned. Chapter 8 explores how polynomials can be used in the study of Sudoku puzzles. Essentially, the idea here is to use a series of polynomial equations to characterize the entries in a Sudoku grid, which in turn leads to the authors to mention the concept of a Gröbner basis. (The authors wisely do not pursue this topic, and are content to just mention it.) In all three of these chapters, the discussion is expository, attempting to explain to the reader that these concepts exist but not doing much in the way of actual proof. (More mathematically sophisticated readers, however, will appreciate the numerous references to papers; there is an interesting 47-item bibliography. Although there has been mathematical work done on Sudoku before, this book is, to my knowledge, the first attempt to address the subject in a full-length book.)
After these three chapters on mathematical theories, the authors shift gears a bit and present a chapter devoted to the subject of extremal problems in Sudoku, most of which are unsolved and involve extensive computer use. The authors return to the question, for example, of what is the minimum number of clues that must be filled in to insure a sound puzzle, and also address other problems that are similar in spirit: e.g., what is the maximum number of clues that a puzzle can have, such that the removal of any one of them renders the puzzle unsound? Or, what is the size of the largest rectangular block that can remain empty and still guarantee a sound puzzle? The authors discuss examples illustrating the state of knowledge of these and other extremal problems.
Finally, the text ends with an epilogue devoted entirely to puzzle-solving: a number of variations of Sudoku puzzles are given for the problem-solving amusement of the reader. No mathematical theories are discussed here, although the authors state that the mathematics involved could fill a “mighty treatise”; that treatise, however, is saved for another day.
This is a delightful book which I thoroughly enjoyed reading. In some sense it is hardly surprising that I would enjoy it, since I enjoy Sudoku, mathematics and good writing, and this book combines all three of these. However, I doubt anyone needs to enjoy all three to enjoy this book; a person with very limited background in mathematics, or a person without much experience solving Sudoku puzzles, could still find something of interest here. While it is not intended as a text for any kind of traditional course in mathematics, I did keep thinking, as I read it, that it would be fun to offer an honor’s seminar based on it. Finally, I should also mention that it is quite reasonably priced: it is (as of this writing, at least) available for sale for just over twenty dollars, with a Kindle edition available for ten. I would, however, enthusiastically recommend this book even if it cost more.
Mark Hunacek (firstname.lastname@example.org) teaches mathematics at Iowa State University. He starts every day with the Des Moines Register’s Sudoku puzzle.