Adventures in Applied Math

I realized that the title of this blog is starting to become sort of misleading; there's a whole lot about adventures, and very little about math, applied or otherwise. I think that there must be someone who's reading this thing for the math and is getting awfully disappointed as I blather on about bathmats and dishes and my feelings. There was a little mathematical action going on with the whole mortgage thing, but even that was disappointingly general. So, in honor of that hypothetical mathematically-deprived person, I am going to talk about one of my current favorite applications of math: SUDOKU.

Never fear, math-phobes and mathematically disinclined! I will do my best to keep this entry accessible to those without extensive math training. And if you have any questions you are more than welcome to ask in the comments section, and I will do my best to answer.

For those of you not in the know, Sudoku is the latest puzzle craze. “Su Doku” is Japanese for “numbers singly.” In the canonical puzzle, there is a 9 x 9 grid, in which nine of each number 1-9 must be placed such that each row, column, and 3 x 3 subgrid contains each digit only once. The puzzle is given to you with some numbers already placed, to assure that the solution to the puzzle is unique. (Think about it: if it were an empty grid, there would be a whole lot of correct solutions. And by a whole lot, I mean 6,670,903,752,021,072,936,960 [source: Wikipedia]. So you have to fill up at least a few squares in order to narrow it down.)

Before we get into this, let me say that this puzzle does not involve math in the traditional sense. That is, the digits 1-9 are simply placeholders, with no arithmetic value. You could just as easily use the letters A-I; the names of the planets in the solar system; Snow White, the prince, and the seven dwarves; or nine different colored crayons to represent the same thing. The reason numbers are used is because they’re a lot easier to write. (This square is Sneezy! No, wait, it’s Snow White! Damn! They both start with "SN"!)

The sort of math involved in the Sudoku puzzle is mathematical logic. You use logic to eliminate candidates for each square. For example, if there’s a five in square (1, 3), we know that there can’t be a five in any square (1, y) or (x, 3), or in any square (x, y) where both x = {2, 3} and y = {1, 2} (that’s the row constraint, column constraint, and subgrid constraint, respectively. The notation {a, b} means "a or b.").

According to Peter Lablans at www.multivaluelogic.com, the Sudoku puzzle is an example of a nine-way logic table. That is, instead of having binary, yes-no logic, we have nine choices (yes/no/maybe/almost always/usually/often/sometimes/rarely/when pigs fly?). I don’t know enough about multi-value logic to say much more than that, but if you’re interested, his site is very informative.

An interesting question to consider is how many squares do you have to pre-fill in order to assure a unique solution? Seventeen is the smallest number of pre-filled squares in a Sudoku puzzle with a unique solution found so far. But this does not mean that all puzzles with seventeen pre-filled squares possess a unique solution. For example, consider the puzzle in which all ones and all twos are pre-filled. (This puzzle has 18 pre-filled squares.) There are many valid solutions to that puzzle. The reason this puzzle does not have a single solution is that many of the pre-filled squares are redundant. For example, removing one of the twos, we lose no information, because we can deduce that that particular square must contain a two based on the location of the other eight twos.

Something else to ponder is how long it will take to solve a Sudoku puzzle. If there are n entries in the puzzle, we should be able to figure out how long it takes to solve the puzzle as a function of n. Meaning, if we are solving a bigger puzzle, such as a 16 by 16 Super Sudoku, or a 25 by 25 Mega Sudoku, there should be a formula into which we can plug our number of entries and come out with the expected time to solve the puzzle in some sort of arbitrary time units.

Sudoku puzzles are in a class of problems known as NP-complete. This means that solving a Sudoku puzzle of arbitrary size (probably) requires an algorithm that takes an amount of time proportional to n! or at best a constant raised to the power of n. This sounds like bad news, but it also means that if you can figure out a faster algorithm to solve the Sudoku problem, then you can apply the same algorithm to a long list of other problems, including the Traveling Salesman Problem (given an itinerary of n cities to visit, what is the fastest route?), the Graph Coloring Problem (given a set of vertices connected by edges, find the smallest number of colors required to color the vertices so that no adjacent vertices have the same color), and even Minesweeper and Tetris.

For small problems such as a 9 by 9 Sudoku puzzle, or a three-city trip, finding a solution in factorial or exponential time is okay, because the number we’re factorializing or raising to a power is relatively small. But for larger problems, beginning with even a dozen unknowns, the factorial or exponential time begins to take its toll.

Computer scientists don’t care about an iterant salesman, but they do care about your e-mail message getting from point A to point B and the connectivity of networks (graph coloring). They also care about making your messages safe, which is why they encrypt them in ways that make their decryption NP-complete (unless you have the right digital key). UPS and the postal service care a lot about how they should route their trucks and planes to minimize costs (traveling salesman). Computational scientists (such as myself) care a lot about how to evenly partition the workload of their computer program across a large set of processors (a variation of the subset sum problem, another NP-complete problem). So the stakes are much higher than one might think for a simple logic puzzle.

The way that these very important problems are solved in real life is with heuristics, or strategies. What we obtain are solutions that may or may not be optimal, but are "pretty good." For example, the only way to figure out the fastest itinerary for the traveling salesman is to look at every possible itinerary and pick the best one. If there are n cities, we’re talking on the order of n! different itineraries. Instead we use strategies like "visit cities that are close to each other before moving on," which make sense but are not guaranteed to give us the best solution. Instead they give us a pretty good solution for a fraction of the cost: more like n-squared time. So maybe the traveling salesman doesn’t go on the shortest possible trip, but at least this way he doesn’t have to wait hundreds of years for us to determine his itinerary!

Because I can’t write comfortably, I was delighted to discover a Sudoku widget for the Mac a couple of months ago. The widget spits out delightful Sudoku puzzles which I then dutifully solve. It has four settings for the puzzle difficulty: easy, moderate, hard, and diabolic. The widget that I use also has a timer on it. I’ve found that generally speaking, I can solve the easy puzzles in under ten minutes without having to make any notes. Sometimes, however, there are some supposedly easy puzzles that take me much longer.

I tried to figure out what the widget author’s definition of easy must be. I think it has to do with the number of pre-filled entries in the puzzle. So I did my own statistical analysis of the number of pre-filled entries in the puzzle, and here’s what I came up with: For easy puzzles, there are anywhere from 27-31 pre-filled, with an average of about 29. For medium puzzles, there were anywhere from 26-29 pre-filled, with an average of about 27. For hard puzzles, there were anywhere from 23-25 pre-filled, with an average of about 24. And for diabolic puzzles, there were anywhere from 21-24 pre-filled, with an average of about 23.

In my experiment, I observed that it took much longer to generate the diabolic puzzles than it took to generate the easy ones. Indeed, as the difficulty level rose, the time it took to generate the puzzle rose. I should have timed it to see if perhaps there was an exponential relationship, as the classification of this problem suggests. My theory is that the widget’s author starts with the lowest possible number of pre-filled squares (based on my experiments, it would be 27, 26, 23, and 21, for easy, medium, difficult, and diabolic, respectively), and checks that the solution is unique. If not, he fills another square and checks again.

Reading the Wikipedia article on Sudoku, I see that the number of pre-filled squares is not a good indicator of difficulty. Indeed, I could see how this would be true. If you pre-filled redundant squares (like my example of filling in all the ones and twos), no information would be gained. My guess is that this is what happens in those surprisingly difficult, allegedly easy puzzles.

There is so much more to talk about, but I think I will stop here for now. You could say that my explanation may not be optimal, but it is "pretty good." And it only took me n-squared time to write it! Ha ha ha, a little math humor there!

Resources:
http://geomblog.blogspot.com/2005/05/sudoku-ok-kudos-uk.html
http://www.multivaluelogic.com/
http://en.wikipedia.org/wiki/Sudoku
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku
http://www.shef.ac.uk/~pm1afj/sudoku/