It must be something in the milk. For expository writers who specialize in mathematical subject matter, there’s a strange attractor in Northfield, Minnesota. That’s where Lynn Arthur Steen and his colleagues produced “telegraphic reviews” of mathematical writing for many years. Math Horizons, the student math magazine published by the MAA, was edited there for a while by Steve Kennedy and Deanna Haunsperger. Barry Cipra lives there. And I used to live there too.

I’ll be making a pilgrimage back to my old hometown next week. Thanks to the generosity of Paul Zorn and the hospitality of Barry Cipra, I’ll be giving a talk at St. Olaf College Tuesday afternoon. Details here. And Rosalind Reid and I will be meeting with Mary Steen’s class of potential future math scribes.

Four colors suffice for any planar map: We’ve known that since 1977. If a map is divided into countries or provinces or other regions, and you want to color the map so that no two adjacent regions have the same color, you’ll never need more than four crayons. But there are a couple of definitions that have to be accepted if this theorem is to hold. First, “adjacent” means that two regions share a boundary segment, not merely a point or a discontinuous set of points. Second, a “region” has to be a connected area, so that you can reach any point in the interior from any other such point without crossing a boundary.

A few days ago the strange and wonderful Strange Maps blog called attention to this map of the Principality of Liechtenstein:

(The map comes from the Wikimedia Commons Atlas of Liechtenstein, which has a larger image.)

It seems that Liechtenstein is divided into 11 communes, which emphatically do not satisfy the connectivity requirement of the four color map theorem. Just four of the communes consist of a single connected area (Ruggell, Schellenberg and Mauren in the north, and Triesen in the south). All the rest of the communes have enclaves and/or exclaves. (I confess that I didn’t know the distinction between these words until yesterday. They make a nice pair.) The most fragmented commune is Vaduz, which includes the principality’s capital. Vaduz consists of six isolated pieces; the smallest is a sliver about a kilometer northeast of the town of Planken.

In the map above, each commune is assigned its own color, and so we have an 11-coloring. It’s easy to see we could make do with fewer colors, but how many fewer? I have found a five-clique within the map; that is, there are five communes that all share a segment of border with one another. It follows that a four-coloring is impossible. Is there a five-coloring? What is the chromatic number of Liechtenstein?

“Between The Folds” uncovers the stories of ten fine artists and intrepid theoretical scientists who abandoned careers and scoffed at hard-earned graduate degrees—all to forge unconventional lives as modern-day paperfolders.

Perhaps such a film should be kept from impressionable youth, lest more degree-scoffers be lost to a life in the creases. Nevertheless, the one-hour documentary, written and directed by Vanessa Gould, is showing online this weekend, today through Sunday only, in connection with the Hamptons International Film Festival. Several of the featured folders come from the world of science and math: Robert Lang, Tom Hull, Erik Demaine, and Erik’s father Martin Demaine.

If you’d like still more cinematic experience of Erik Demaine, his recent talk at the opening symposium for the Microsoft New England research center is now online, where he performs magic tricks as well as showing off origami. (But the video is in a Windows-only format—what’s with that?)

At right Erik makes a hand-waving argument while blindfolded.

Thanks to Barry and Ros for tips on these items.

The mail has brought me an early copy of The Princeton Companion to Mathematics, a 1,034-page compendium edited by Timothy Gowers (as well as June Barrow-Green and Imre Leader, associate editors), with contributions from more than 130 other authors. I’ve only just begun to browse through its pages, but already I’m completely charmed. This is one of those books that makes you wish you had a desert island to be marooned on.

In the preface, Gowers is at pains to establish that his book is a companion, not an encyclopedia. What that means, in part, is that authors are allowed to exhibit attitude and personality. Gowers wastes no time in doing so himself. The preface begins by citing a definition of “pure mathematics” written by Bertrand Russell in 1903:

Pure Mathematics is the class of all propositions of the form “p implies q,” where p and q are propositions containing one or more variables, the same in the two propositions, and neither p nor q contains any constants except logical constants….

Russell is allowed to go on in this vein for another eight lines, and then Gowers remarks: “The Princeton Companion to Mathematics could be said to be about everything that Russell’s definition leaves out.”

Since I haven’t yet read more than 5 percent of the book, I’m in no position to review it here, but I think I can say a little more about the nature of what’s in it. Two big sections are essentially reference material: 99 short articles on mathematical concepts (arranged alphabetically) and 96 biographies of mathematicians (arranged chronologically, excluding living persons; the median birthdate is 1822). A third section gives brief accounts of 35 “theorems and problems,” many of them either open or recently solved (the Riemann hypothesis, the Mordell conjecture, Fermat’s Last Theorem) but also including a few classics (the three-body problem, the insolubility of the quintic).

Lots of good stuff in all of those sections, but not a lot of surprises. What I’m really warming up to are the parts of the book where authors are given freer rein to follow their own particular instincts or obsessions and where they express more distinctively personal views.

Gowers himself wrote a 76-page introduction that undertakes to explain what mathematics is all about, not only as a body of knowledge but also as a cultural phenomenon and as a way of thinking about the world. (The last section of the chapter is titled “What do you find in a mathematical paper?” At one point, Gowers begins to sound a little like Russell: “The object of a typical paper is to establish mathematical statements.”)

Seven more essays take another stab at introducing mathematics, this time working from a historical perspective. For the most part the sequence of topics follows an uncontroversial trajectory through the past two millennia: numbers, geometry, algebra, analysis, proof. But the editors have also decided to put algorithms on an equal footing with these subjects, a choice that would have been unlikely 50 years ago. On the other hand, the historical progression culminates in “The Crisis in the Foundation of Mathematics.” The crisis in question is that of the intuitionist rebellion and Gödel’s incompleteness results, events of the 1920s and 30s. It’s rather like a political history of the world that ends with the conflict between communism and fascism. But I suppose that the rest of the book could be taken as an effort to fill in the record of what’s happened since then.

The best bits of all come at the end of this weighty volume. Although the Companion claims to focus on “pure” mathematics, 14 chapters on “The Influence of Mathematics” show a definite leaning toward applications. We get views of mathematics in chemistry, biology, economics, statistics, music and art. And there are a few more narrowly focused essays, on topics such as wavelets, traffic and cryptography.

The book’s last section, titled “Final Perspectives,” is where I would recommend beginning. Here are the contents:

• The Art of Problem Solving, by A. Gardiner.
• “Why Mathematics?” You Might Ask, by Michael Harris.
• The Ubiquity of Mathematics, by T. W. Körner.
• Numeracy, by Eleanor Robson.
• Mathematics: An Experimental Science, by Herbert S. Wilf.
• Advice to a Young Mathematician, with contributions from Sir Michael Atiyah, Béla Bollobás, Alain Connes, Dusa McDuff and Peter Sarnak.
• A Chronology of Mathematical Events, by Adrian Rice.

Details: Princeton University Press. ISBN: 978-0-691-11880-2. Price: $99. The book’s web page has PDFs of a few chapters, as well as an interview with Gowers. Gowers also has a blog with a few entries pertaining to the book.

Catching up on new submissions to the arXiv, I came across a paper by Robert Baillie, “Summing the Curious Series of Kempner and Irwin,” which is item 0806.4410 in the mathematics listings. Here’s the abstract, exactly as it appears at http://lanl.arxiv.org/abs/0806.4410v1:

In 1914, Kempner proved that the series 1/1 + 1/2 + … + 1/8 + 1/10 + 1/11 +… + 1/18 + 1/20 + 1/21 + …, where the denominators are the positive integers that do not contain the digit 9, converges to a sum less than 90. (The actual sum is about 22.92068.) In 1916, Irwin proved that the sum of 1/n where n has at most a finite number of 9’s is also a convergent series. We show how to compute sums of Irwins’ series to high precision. For example, the sum of the series 1/9 + 1/19 + 1/29 + 1/39+ 1/49 + … where the denominators have exactly one 9, is about 23.04428708074784831968. Note that this is larger than the sum of Kempner’s “no 9″ series. We also show how to construct nontrivial subseries of the harmonic series that have arbitrarily large, but computable, sums. For example, the sum of 1/n where n has at most 434 occurrences of the digit 0 is about 10016.32364577640186109739.

Baillie’s article is full of really interesting mathematics and algorithmics, which ought to be reason enough to mention the paper here. But it was something stranger that caught my attention. Look closely at the large number in the last line of the abstract. The HTML source of the arXiv page looks like this:

  1<a href="abs/0016.3236">0016.3236</a>4577640186109739.

It seems the sequence 0016.3236, embedded in a larger string of digits, has been interpreted as an arXiv identifier. I can only guess that some program at arXiv.org is scanning abstracts looking for strings of the form nnnn.nnnn, where n is any decimal digit. It’s a little like those rogue search-and-replace scripts that do amusing things like turning every “gay” into a “homosexual.”

As it happens, there is no arXiv paper with the identifier 0016.3236. There can’t be because the identifier format is actually yymm.nnnn, encoding the year and month of submission in the first four digits. Obviously there is no month 16, and the identifier scheme had not yet been introduced in the year 00. Thus, as far as I know, the competition is still open for the first perfectly self-referential arXiv preprint—one that finds a legitimate reason to embed its own identifier in its abstract. (Part of the challenge is that you can’t know in advance—at least not with high precision—what number will be assigned to a paper when it is submitted.)

[More on the Kempner series: Baillie and Thomas Schmelzer also have an article on related work in the latest American Mathematical Monthly. The article is available (pdf) from Schmelzer's web site.]

Update 2008-09-07: Because this post makes fun of programs that automatically scan and “fix” text, it inevitably suffers that very fate. Although the long quotation above was pasted into my editor window exactly as it appeared in the original arXiv abstract, that’s not how the quotation will arrive on your screen. If you try to follow the link embedded in that long number, you’ll find that the address is not “abs/0016.3236″ but “bit-player.org/2008/abs/0016.3236″. Somewhere in the WordPress software is a routine that “corrects” any URL lacking a top-level domain. I have resisted the urge to correct the correction. I note that arXiv is following the same policy: The latest version of the Baillie abstract (posted 17 August) still includes the curious embedded link.

I have a longstanding friendly feud with my Editor-in-Chief over the use of logarithmic scales in graphs. I tend to go for a log plot if there’s the slightest hint of an exponential trend in the data; she argues that the human sense of numbers is inherently linear, and thus a nonlinear scale should be used only in exceptional circumstances. Linear is natural, she says; logs are for geeks.

Vindication is always sweet, so I was delighted to see a report in the latest issue of Science (subscription needed for full-text access) suggesting that members of an Amazonian indigenous group seem to order numbers on a logarithmic scale. Stanislas Dehaene, Véronique Izard, Elizabeth Spelke and Pierre Pica worked with 33 adults and children of the Mundurucu group in Brazil’s Para province. The subjects were shown a line segment with labeled end points (illustration above) and asked to place various other numbers within this interval. The numbers were presented as patterns of dots, as sequences of tones or as spoken number words in the Mundurucu language or in Portuguese. The results of the experiment show, according to Dehaene et al.:

The Mundurucu seem to hold intuitions of numbers as a log scale where the middle of the interval 1 through 10 is 3 or 4, not 5 or 6.

In contrast, 16 American control subjects from the Boston area placed numbers on the scale pretty much in proportion to their magnitude.

For the sake of my ongoing quibble with the E-in-C, it’s in my interest to support and endorse this finding. I wish could do so.

Exactly what does it mean to “hold intuitions of numbers as a log scale”? Simply taking base-10 logarithms of numbers isn’t quite what’s wanted. The logarithm function maps the integers 1 through 10 onto a range from 0 to 1. To map numbers in the domain [1, 10] onto the same co-domain “logarithmically,” we need a transformation along the lines of R = (9 log₁₀ S) + 1, where R is the “response location” and S is the “stimulus number.” But the resulting curve, superimposed in red on the graph above, doesn’t match the experimental data very well at all. And, looking at the data more closely, it’s hard to see how any plausible transformation is going to account for the positions of those dots and error bars. There’s trouble in the middle, where 5 was judged larger than 6. And there’s trouble at both ends: No matter where you place the numbers 2 through 9 on the scale, shouldn’t 1=1 and 10=10? The anomalies at the ends are made more puzzling by the instructions given to the test subjects:

Only two training trials were presented, with sets of dots whose numerosity corresponded to the ends of the scale (1 and 10). The participants were told that these two stimuli belonged to their respective ends, but that other stimuli could be placed at any location.

In view of these instructions, it seems peculiar that stimulus number 1 has a response location near 1.5, and stimulus number 10 corresponds to a response location of roughly 8.

I wonder if the data aren’t better explained by a simple step function. Perhaps the subjects counted dots up to 4, but beyond that merely estimated the number of spots, lumping together any stimulus with 5, 6 or 7 dots in one class, and putting patterns of 8, 9 or 10 spots in a second class.

Or maybe the arrangement is logarithmic after all. The Mundurucu may have a lot more mathematical sophistication than Dehaene et al. give them credit for. When presented with a scale that runs from 1 to 10, rather than 0 to 10, they intuit that the interval belongs to the series …, 0.01, 0.1, 1, 10, 100,…, rather than the more prosaic series …, –10, 0, 10, 20, 30, …. Anyway, I think that’s what I’ll tell my Editor-in-Chief.

When I finished writing about the Zeno wagering game recently, I had some trees left over, so I thought I would try planting them here.

In the Zeno article I was trying to understand and explain the structure of this peculiar-looking tree, which I’ll call the tangled tree:

As a warmup exercise, I started out with this simpler example, the combed tree:

These are both binary trees: Each node has exactly two descendants. And the trees also share a basic internal symmetry. In both structures, if a node has horizontal coordinate x, the two descendant nodes are symmetrically arrayed at x-d and x+d. The difference between the two trees is all in how the displacement distance d is calculated. In the combed tree, d has the initial value 1/4 at the root node, and it is reduced by half at each lower level of the tree. In the tangled tree, the formula is d = 1/2 min(x, 1-x). In other words, d is half the distance to the nearer boundary of the interval [0,1].

There was a third tree I didn’t have room to include in the article. I had stumbled upon it when I made a programming error. This rogue structure looks like this, and I’m calling it the braided tree:

The nature of my programming error is not hard to see. Intending to generate the tangled tree, I had meant to calculate the positions of the child nodes as follows:

      left = x - 1/2 min(x, 1 - x)
      right = x + 1/2 min(x, 1 - x)

But instead I carelessly wrote:

      left = x - 1/2 x
      right = x + 1/2 (1 - x)

Stupid goof, but the result is visually intriguing. And although the braided tree is a botched version of the tangled tree, it actually has a lot in common with the combed tree. In particular, both the combed and the braided trees have exactly the same set of nodes; the difference is that those nodes are wired differently.

One way to understand the difference is to look at the paths leading from the root to any given node. Each such path is a sequence of left and right turns. For example, in the combed tree you can get from the root to the node at x = 3/16 by turning left at the root, then left again at 1/4 and finally right at 1/8. In the braided tree the path to 3/16 goes right to 3/4 then left to 3/8 and left to 3/16. Paths of this kind can be encoded as binary numerals, letting a 0 stand for each left turn and a 1 for each right turn. In this scheme the two paths described above are 001 and 100.

In essence, the braided tree is a permutation of the combed tree. If you list all the nodes at some fixed level in the combed tree (say those three levels below the root, where all denominators are 16), then the corresponding paths are in numerical order:

    1/16    000    (0)
    3/16    001    (1)
    5/16    010    (2)
    7/16    011    (3)
    9/16    100    (4)
   11/16    101    (5)
   13/16    110    (6)
   15/16    111    (7)

Here’s the corresponding tabulation for the braided tree:

    1/16    000    (0)
    3/16    100    (4)
    5/16    010    (2)
    7/16    110    (6)
    9/16    001    (1)
   11/16    101    (5)
   13/16    011    (3)
   15/16    111    (7)

The order is “counting from the left,” incrementing the most significant bit first. I wonder what other permutations give interesting-looking trees.

Turning back to the tangled tree that began this whole investigation, I would argue that it looks tangled and unruly not so much because lots of edges cross (there are even more crossings in the braided tree) but because of many near collisions and coincidences. For example, just below the root of the tangled tree, the mirror-image paths <left-right-right> and <right-left-left> almost converge on the same value, but they miss by just a bit. We can fix this! All it takes is an adjustment in the formula for the displacement d. In the tangled tree that displacement is 1/2 min(x, 1-x). The constant 1/2 in this expression is quite arbitrary, and we can substitute any other value a, with 0 < a < 1.

So what is the magic value of a in the following tree, which I am inclined to call the crocheted tree?

Note: If the title of this post fails to ring a bell, see the poem by Robert Hass:

The gene pool threw up a wobbly stem
And the tree danced. No.
The tree capitalized.
No. There are limits to saying,
In language, what the tree did.

The latest issue of American Scientist is just out, both on the newsstand and on the web. My “Computing Science” column is titled “Wagering with Zeno”; it returns to a subject mentioned briefly in an earlier column, “Follow the Money.”

Consider a random walk on the interval (0,1), where the walker moves according to these rules:

• The walker begins at x = 1/2.
• At each step the walker moves either left (toward 0) or right (toward 1) with equal probability.
• The length of each step is one-half the distance to 0 or to 1, whichever is nearer. In other words, the distance moved is 1/2 min(x, 1–x).

If you want to know more about this process and why I bothered to write about it, please see the column. Here I just want to say a few words about visual aids that might be helpful in understanding how the random walk evolves and where the walker is likely to wind up.

Here is one of the illustrations that appears in the column:

We see four trajectories, each lasting 10 steps. Although the walk is actually one-dimensional—moving back and forth along an interval of the x axis—the trajectories are plotted in two dimensions for clarity, moving down the page so that the illustration becomes a kind of discrete spacetime diagram. Even with this device, though, some of the paths overlap for part of their course. If I tried to crowd more trajectories into the figure, the overlaps would make it hard to sort out one walk from another.

In making pictures like this, the issue is not just how you explain an experiment to other people; it’s also a matter of how you come to understand the process yourself. While I was trying to make sense of the Zeno walk, I plotted lots of trajectories like these, initially by hand and then with a program that generated Postscript files. Some important features were quickly apparent. In particular, I noticed that the walker takes much bigger strides in the middle of the space than near the edges. (Of course this fact follows directly from the definition of the walk, but it doesn’t hurt to see a picture.) I also observed that most of the walks seem to spend most of their time hugging one edge or the other, seldom venturing back across the midline of the space. Even after looking at a few hundred examples, however, I didn’t feel like I had a really secure sense of how a “typical” walk would proceed.

As with many processes that evolve over time, the illustrative possibilities are much richer if we can escape the static bounds of ink on paper. And thus I was led to try creating a more dynamic and interactive display.

What you see above is not dynamic; it’s merely static pixels on glass. But you can see it all in action in this Java applet. Feel free to click on the link and go play, but do come back here afterward so we can continue the conversation.

Hello again.

Does this program succeed in conveying an intuitive sense of how the Zeno walker walks? Personally, I’ve found it helpful, although it still comes up far short of ideal. Adjusting the number of steps in each walk gives a sense of how the walker’s apparent attraction to the edges gets more extreme over time. And adjusting the rate at which paths fade into the background allows for a degree of balance between clutter and evanescence. But there may well be a better way to go about visualizing these concepts. I’d be interested in hearing suggestions.

A note on the implementation: The applet was created with the programming language called Processing, invented by Ben Fry and Casey Reas. I’ve just reviewed two books on Processing, and so this project was undertaken partly to try out the language and its programming environment. I found it very slick, and mostly trouble-free. The source code of the zenowalk program is available through a link on the applet page. (Most of the code for the buttons and sliders was cribbed from the book by Fry and Reas.)

Of course there’s always something lacking in any programming language. In this case what I missed most acutely was the exact rational arithmetic I rely on in Lisp. Processing has only single-precision floating-point numbers. In the Zeno walk, these numbers begin running out of significant digits after about 150 steps (which is why I limited the program to 145 steps). As far as I can tell, no one has yet written a Processing library for bignums and exact rationals. I guess that’s my job.

The interesting thread of comments on Wednesday’s post about “electoral hex” led me to look more closely at the graph for the Lower 48 states:

I’ve constructed the graph—and it wasn’t easy, by the way—on the rule that two states are linked by an edge if they share a common boundary of more than one point. National boundaries are determined in the same way. Nodes half-shaded orange are east coast or west coast states; those half-shaded blue are north coast or south coast states. Underwater boundaries count in this scheme. Thus, for example, Illinois is adjacent to Michigan because there’s a section of boundary line between them in the middle of Lake Michigan. Similarly, Wisconsin is not a north coast state, even though it abuts Lake Superior, because it has no shared boundary with Canada.

Some properties of the graph:

• It has 48 vertices (no surprise!), 107 edges, and 60 faces (excluding the outer, embedding, face).
• It’s a planar graph (again no surprise).
• All but one of the faces are triangles. The exception is a quadrilateral formed by the Four Corners states.
• The degree sequence runs: 8 8 7 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 1. (The two octopus states are Missouri and Tennessee. The singleton is Maine.)
• The diameter is 11, and the characteristic path length (the length of the shortest path between two vertices, averaged over all pairs of vertices) is 4.1.

What about playing hex on this graph? In standard hex, one player tries to connect east to west, and the other player has to find a path from north to south. Those rules would hardly be fair with such an asymmetrical graph. So let’s adopt a modified version of the rules that I suggested for the political primaries: The players take turns, and the first to create a pathway either from north to south or from east to west is the winner. (Barry Cipra suggested that we call this the game of pox.)

Is the game a sure win for either the first or the second player (assuming correct play on both sides)? If so, what’s the right opening move?

It’s easy to find some really bad moves. As Paul Zorn noted, the New England states are not worth bothering with, because they’re sealed off by New York. But it turns out New York is not a very smart choice either. (If you take New York, I take Pennsylvania; then, if you want to get anywhere, you have to win all three of New Jersey, Delaware and Maryland, which gives me three chances to block you.)

The shortest bridging paths are along the I-5 and I-15 corridors, out west. In particular, there are five ways to construct a path of length 3 from north-to-south with the states WA, OR, CA, ID, NV, UT, AZ. But I don’t believe there’s any way a player can force a win using these states alone.

In hex, the best opening moves are generally near the middle of the board. The analogous pox strategy would choose one of the central and highly connected states such as MO, TN or KY. This seems sensible, but the games are too complicated to work out by hand.

On a regular 7 × 7 board, hex has been fully solved: The entire game tree is known for every possible opening move, so that each cell of the board is classified as a win or a loss for the first player. (This impressive feat of analysis and computation was done by R. Hayward, Y. Björnsson, M. Johanson, M. Kan, N. Po and J. van Rijswijck of the University of Alberta.) The Lower 48 graph is roughly the same size as the 7 × 7 hex board, so a similar method would presumably be feasible. Feasible but not easy.

Another question is whether the game can end without a winner. Jim Ward asked about this in the comments to the previous post, but I didn’t really understand the full force of the question. In the game of presidential primaries—where elections can occur simultaneously in multiple states—two or more winning paths could be created at the same time. Enforcing a strict alternating-turns policy, as I’m assuming here, eliminates that problem. But there’s another way the game might possibly fail to yield a winner, namely if all the states are chosen but there’s still no path along either axis.

In hex it’s easy to show that no such drawn game is possible. You can block the progress of a north-south path only by completing an east-west path. Hex is played on a regular and symmetrical lattice whose structure is equivalent to this graph:

The graph of the Lower 48 is not quite so uniform. The diagonals don’t all go the same way, and there’s that quadrilateral with no diagonal at the Four Corners. Does that feature (or some other oddity of the graph) allow all the states to be divided into two categories without creating either a north-south or an east-west path? I don’t think so; I haven’t been able to find such an assignment. But I’m not quite sure it can’t exist.

Update 2008-03-17: By popular request, I’ve posted a PDF version of the lower-48 graph and a text file with the vertex list and edge list. The vertex and edge lists actually take the form of a Scheme definition, but the semantics should be obvious and translation to other formats should be straightforward.

The answer to the question in the headline is: Too many. After I wrote about Sudoku a couple a years ago, I thought I had cured my addiction; but I’ve been a shameless backslider.

I return to the subject now, in this public confessional mode, to correct an error in my 2006 column. Citing a paper by Bertram Felgenhauer and Fraser Jarvis (pdf), I stated that there are 6,670,903,752,021,072,936,960 Sudoku solutions. This is simply the number of ways of filling in the 81 squares without violating the no-two-alike constraints in rows, columns and blocks. I then went on to discuss the symmetries of the Sudoku grid, and noted:

When all these symmetries are taken into account, the number of essentially different Sudoku patterns is reduced substantially…. although [the reduction] still leaves an impressive number of genuinely different solutions: 3,546,146,300,288, or 4×10¹².

The latter number also comes from Felgenhauer and Jarvis, but I misinterpreted it. Contrary to my statement, it takes into account only a few of the simplest symmetries. The true number of essentially distinct Sudoku solutions is reported in a slightly later publication by Ed Russell and Jarvis. The correct tally is smaller by three orders of magnitude: 5,472,730,538.

Thanks to Richard E. Dickerson for pointing out my error.

It needs to be emphasized that both of these calculations count the number of solutions, not the number of puzzles. For any given solution, there are many possible puzzles, each created by erasing a different subset of the entries in the solution. How many puzzles per solution? Does anyone know? An exact count seems beyond reckoning, but random sampling ought to yield a rough estimate. For example, consider just those puzzles that have 17 initial clues (the apparent minimum). For any given solution grid, there are (81 choose 17) ways of forming a 17-clue puzzle; this works out to 128,447,994,798,305,325. Most of those puzzles will not have a unique solution, and so they are disqualified as proper Sudokus. The random sampling is needed to estimate how many of the potential puzzles are admissible.

I’d try doing the calculation myself, but I’m too busy solving Sudokus.

Update 2008-04-05: Richard E. Dickerson discovered the error mentioned above in the course of preparing his own discourse on Sudoku-solving strategies. That work now has its own web site, The Sudokerson Matrix, where you can download the 61-page PDF file and an accompanying spreadsheet. Dickerson also mentions some other resources on Sudoku strategy, including a recent book by Andrew C. Stuart that I haven’t yet seen. Dickerson comments:

Few books on Sudoku go into strategies in any depth. Stuart’s The Logic of Sudoku (Michael Mepham, 2007) is a wonderful exception. But his book and mine represent the two opposite poles of Sudoku-solving strategy. I regard many of his methods as superfluous, and I am sure that he regards most of my strategies as heretical. You need to have a close look at both.

What I find intriguing in all this is the very idea that we could have contending doctrines of Sudoku strategy. But before the talk of “heresy” gets out of hand and leads to Sudoku holy wars, I’d like to remind everyone that there’s another view of Sudoku in which all strategies become superfluous. Give me a computer and a program for solving constraint-satisfaction problems, and every 9×9 Sudoku yields in milliseconds.