tak1ng sudoku ser1ously

“There is something deeply satisfying in encountering opacity.” (p.9)

I think it was last summer at the Australasian Statistics conference in Adelaide that I saw this book by Jason Rosenhouse and Laura Taalman, Taking Sudoku seriously: The math behind the World’s most popular pencil puzzle. (Or was it in Kyoto at the ISBA meeting?!) In any case, I mentioned my long-term interest in this puzzle (as readers of the ‘Og will undoubtedly have noticed!) and proposed to write a review for Chance. A few weeks later the book arrived at home. Which was a mistake as my wife who is a much deeper Sudoku fanatic than I stole the book with a vague promise to write the review! It is only a few weeks ago that I was able to truly get the book (if not the review) back…

“This is surely the most trivial of pursuits.” (p.4)

In case you never tried to solve a Sudoku puzzle, open your favourite newspaper, news website or phone, and you should immediately find one of those 9×9 squares to fill with integers between 1 and 9, under three sets of constraints: row-wise, column-wise, and block-wise. (The book describes all kinds of variations with no particularly added value.) Depending on the number of integers already present on the grid and on their location, the resolution of the puzzle gets from obvious to close to impossible by hand. This range in the difficulty and the resulting challenges may explain for the popularity of the method, although it remains a mystery to many bystanders. There are many strategies for solving Sudokus, from the (Sherlock Holmes) elimination of obviously impossible values to branching processes carrying guesses until a binary conclusion. The book covers some of those: forced cells, twins, X-wings, and Ariadne’s thread (moving from Star Wars to The Lord of the Ring!). It however does not bring any novel technique to solve Sudokus, at least at the pencil level, so potential readers with this intent in mind should abstain!

“Sudoku is math in the small.” (p.171)

Now many may wonder about the connections between Sudokus and mathematics. Some mathematicians are clearly sceptical. For instance, I remember discussing solving Sudoku grids in the métro with a friend and Mathematics colleague from Paris-Dauphine and she was quite surprised by this fascination, as she did not see any mathematical appeal in the exercise. In my eyes, this is a logical puzzle at the very least (there is one way of setting all the entries and some obligatory paths for filling the grid that have to be exposed), which makes Sudoku vaguely mathematical. I am also attracted by the automated resolution of those puzzles, as shown by my simulated annealing attempt a (long) while ago, even though I am aware that the state-of-the-art codes are beyond my reach. (They are not detailed either in the book.) Reading this book actually made me think of potential alternatives for simulating annealing, from using additional integers during relaxation, to solving a set of algebraic equations under relaxed constraints. (I wonder if Gröbner bases are used by the fastest resolution codes.)

“We are unaware of any result about Sudoku puzzles provable using the techniques of graph-coloring that could not have been arrived at more easily by other means.” (p.133)

Taking Sudoku Seriously does exhibit some of those connections, it may however feel contrived for some readers (and unintelligible to others), as the mathematical objects have an existence of their own and do not appear to directly contribute to the resolution of the puzzle. An exception in the first case is the one of Latin and Greco-Latin squares in Chapters 2 and 4, which are Sudokus of sort, while an exception to the second is the mention of Gröbner bases in Chapter 8 for solving sets of algebraic equations providing the solution to Sudokus in the form of complex roots of unity. Some number theory gets introduced along the way, as well as algebra (permutation and symmetry groups, polynomials) and graph theory. Analysis is rather absent from this volume and so is probability (hence simulated annealing). Except for a rather artificial and unrelated entry about Newton’s cannonball and Archimede’s derivation of the area of a circle in Chapter 7.

“We have a number of different audiences in mind.” (p.xi)

A few days prior to finish reading the book, I received my copy of Significance with a review of Taking Sudoku Seriously by Nicola Tilt. Glancing quickly at it, I read she was wondering about the intended audience for the book, which also is an issue with me. Neophytes and mathematicians alike will learn little about maths from reading the book, since the difficult questions (like counting the number of Sudokus and of non-equivalent Sudokus, or creating Sudokus) are not answered. The most interesting input is, in my opinion, the discussion of computer-based mathematical proofs. From the four-colour theorem to counting the number of Sudokus, to counting the number of fundamentally different Sudoku squares [as 5,472,730,538]. Unfortunately, the book publication date (April 2011) means that it missed the “big news”, namely the resolution of what the authors call “The rock star problem”, which is the determination of “the minimum number of starting clues possible in a Sudoku puzzle with a unique solution” (p.164). On Jan. 1, 2012, Gary McGuire, Bastian Tugemann, and Gilles Civario from University College Dublin used a mix of mathematics and computer power to prove that the minimum is indeed 17, as posited by the authors. (A result to feature prominently in the revised edition, if any!)

“We are curious for a living.” (p.191)

To conclude, and to be fair with the authors, the book reads nicely (on high quality glossy paper), once you limit your expectations to see some links between maths and Sudokus, it offers a lot of Sudokus and related puzzles, with solutions at the back of the book, and, above all, it teaches to some degree mathematical reasoning by running complete arguments on 4×4 Shidokus and extrapolating the results to the 9×9 Sudokus (or not, as in the case of polynomials where the extrapolation does not work, Section 8.2). Worth perusing on your way to work, trying to complete the puzzle at hand before the next stop!

As a postultimate remark, a paper by Hiroshi Watanabe from the University of Tokyo was arXived a few days ago: it contains further links about the mathematical properties of Sudokus, incl. one with a nine-state Potts model, but mostly a simulated annealing algorithm to find a “difficult” Sudoku. Contrary to my early attempt, this algorithm explores the space of all Sudoku puzzles, thus moves from one Sudoku to another at each iteration (“with the Metropolis criterion with the Boltzmann weight”, I wonder why Boltzmann?!).The hardest sudoku found by this method is represented below: it has a depth of 10 and would require 50,000 backtracking attempts to solve! Just “impossible to solve by hand”. (It took the equivalent of 11 cpu-core-years to create it.) As pointed out to me by Anthony Leverrier, from INRIA, the author added in the second version of his arXiv preprint that the puzzle can be easily solved by hand… So you may give it a try.

The hardest Sudoku ever, by H. Watanabe

10 Responses to “tak1ng sudoku ser1ously”

  1. I have now checked Fisher’s published correspondence and in fact there is an exchange of several letter in the period 3 July 1924 to 24 January 1926 between Fisher and MacMahon on the subject of Latin squares. It seems that Fisher had reached the solution some 10 years before his paper with Yates,

    See Bennett, J. H. (1990). Statistical Inference and Analysis Selected Correspondence of R.A. Fisher. Oxford, Oxford University Press. (pp273-276).

    • Thank you Stephen. This is indeed a clear mistake in my review: the book itself only mentions Euler about Latin and Greco-Latin squares. And then attempts by mathematicians [not statisticians!] in the 1930s and 1940s. Although it contains a paragraph on the usefulness of those “in the statistical design of experiments going back at least to the 1930s” (p.52). But the only reference is Bogart (Kenneth, not Humphrey). I will sure mention this omission and Fisher’s derivation in my CHANCE review.

      • Christian, that’s great. I think the Latin Square story is an interesting one. One of the problems Fisher faced in getting his work accepted was that mathematicians tended to underestimate the depth and strength of his solutions because they were not dressed up in the mathematical formalism they were used to. The MacMahon story is a great example of Fisher coming in to a field and using insight rather than the established mathematics to outdo the expert. Savage admitted in

        Savage, L. J. (1976). “On rereading R A Fisher.” The Annals of Statistics 4(3): 441-500.

        that it was shock to him to realise what a very good mathematician RAF really was.

  2. Christian, I am surprised that you didn’t mention RA Fisher. I assume that typical 9×9 Sudokos form a subset of the set of 9×9 Latin Squares. Fisher famously solved the problem of the complete enumeration of 6×6 Latin Squares In a paper with Yates . They pointed out that direct enumeration was quicker than applying McMahon’s method (McMahon was the acknowledged expert) and speculated that by trying to apply McMahon’s method, solutions had been overlooked.

    See R. A. Fisher and F. Yates (1934). The 6 × 6 Latin squares. Mathematical Proceedings of the Cambridge Philosophical Society, 30, pp 492-507. doi:10.1017/S0305004100012731.

    A picture of a stained glass window in the form of a 7×7 Latin square honouring Fisher can be found here: http://www.senns.demon.co.uk/FisherWeb.html and you will also find a link to the Fisher archive at Adelaide where you can obtain the paper.
    Stephen

  3. I don’t understand the fascination with Sudoku given how trivial it is to write a program to solve them. After trying to solve my first Sudoku by hand while staying with my in-laws, I excused myself and wrote a short Java program to solve Sudokus using an 8-queens style backtracking algorithm.

    http://www.colloquial.com/games/sudoku/java_sudoku.html

    How do people study the complexity of Sudoku? Is there a class of Sudoku-like puzzles that grow in size? Do you just grow from 3 x 3 to 4 x 4 puzzles with numbers 1:16? Does that then require an overall 4 x 4 grid?

    • Dear Bob, I am not sure I understand what you do not understand about the fascination of Sudoku: that there exist a trivial computer program to solve them does not detract from their attraction as a source for mathematical questions (the point of the book), computer challenges (like my pedestrian attempt at writing a simulated annealing R code, the meta-simulated annealing approach of Watanabe which obviously failed in its definition of complexity), and the few minutes of mental abstraction in the daily métro ride when solving the newspaper puzzle…

      As for the complexity, Watanabe considers depth (minimal number of forward steps necessary to reach a solution or a deadend) and width (number of parallel scenarios one had to pick from). I cannot tell what went wrong with his derivation, producing a puzzle I was able to
      solve in half-an-hour…

      • It’s the doing of Sudokus I don’t understand. I can understand studying anything! I think I’m too literal and can’t really think of them any way other than in terms of the algorithm I’d apply to solve them. So I don’t find them any more relaxing than filling in tax forms. I (personally) don’t like crossword puzzles, either.

        But I do like some video games, so it’s not the mindlessness or lack of productive engagements. But then given your comment, maybe it’s exactly that “mental abstraction” that’s attractive about Sudoku.

        Thanks for the explanation of complexity — I was expecting something asymptotic (something about complexity in general as problem size grows in terms of number of cells).

  4. I took me 35mn and a seat in the métro to solve it, hardly impossible indeed!

  5. Concerning the preprint by Watanabe, the author added the following comment to the abstract:
    ” (Added on Mar. 11, the created puzzle can be solved easily by hand. Our definition of the difficulty is inappropriate.) “

    • Uh-oh, I overlooked the major sentence of the paper, as it happens! I thus wonder why the author bothered to post this paper… Thanks in any case for pointing out this fact!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 717 other followers