I was on a “vacation” for the last week, which included a real vacation to visit my parents, and also a scare-quotes vacation to Detroit that is a totally different subject. But the side effect of this vacation that is to be the topic of this post is the strange game of Sudoku, which is popular with travelers.

Jessi was with me and she seems to like this Sudoku business (although she denies it), so I thought about playing, too. But I always get interested in the wrong parts of these games. Solving Sudoku puzzles seems more like a game for computers than humans, and writing a program to let computers have their fun is the way I would prefer to waste time while en route. There really isn’t much to it:

def solve(T): # if all cells are filled in, we win if all(T > 0): return 'success' # solve T recursively, by trying all values for the most constrained var pos = possibilities(T) i,j = most_constrained(T, pos) for val in pos[(i,j)]: T[i,j] = val if solve(T) == 'success': return 'success' # if this point is reached, this branch is unsatisfiable T[i, j] = -1 return 'failure'

Is this ruining anyone’s homework problems? Just in case it is, everything I said at the beginning of my post on minimum spanning trees still applies.

With plenty of time left in my flight, this was just the opening move, though. The real question is what makes this fun for the humans who find this kind of thing fun? One hypothesis, the kind that comes naturally when you have watched the statistical physicists in action, is that fun is some sort of phase transition, and if you take random Sudoku puzzles with a certain number of entries you will maximize fun. Half-baked, I know, but as interesting as the movies they show on planes, at least. And it raises the extremely important, and possibly unsolved challenge, how do you sample uniformly at random from Sudoku puzzles with *n* cells filled in?

In my travel-addled state, I thought maybe a good way to do it would be to start with some complete configuration, knockout a large fraction of the cells at random, permute the remaining cells, and then solve the resulting configuration. Repeating this has got to be an ergodic markov chain, right? I’m not sure… and even then, do you think the stationary distribution is uniform?

def rand(n, T=None): # start with an empty board if T == None: T = -1*ones([9,9]) # solve it to generate an initial solution solve(T) # do random shuffles to approximate uniformly random solution for k in range(5): select_random_cells(T, 20) randomly_permute_labels(T) solve(T) # remove appropriate amount of labels select_random_cells(T, n) return T

Now, when Jessi found out that I was helping computers take her sudoku-solving job away, she thought I was a geek, but when she found out I was generating puzzles with more than one solution, she was outraged. Sudoku puzzles have a unique solution! So maybe what is really fun is a random puzzle with a unique solution, and the right number of cells filled in, where a smaller number of cells means that harder puzzles are right. Fortunately/unfortunately my travel ended before I finished investigating this important issue.

I doubt it is related, but I got pretty sick the next day.

More? The computational complexity blog collected some thoughts on Sudoku years ago, and Joshua Cooper has a deck of slides that encourages anyone interested in getting serious about this line of research to contact him.

Oh, and here is the code to make your own (not-necessarily uniformly) random puzzles, draw them, solve them, and count the solutions: http://gist.github.com/460904

On your next flight try mathdoku: http://www.mathdoku.com

There was a talk on solving Sudoku at SciPy on Wednesday, wish I could remember who gave it…

And Keith is right, KenKen is far superior (nytimes.com/kenken)

What a great question! A while back, I became interested in the mathematics behind Sudoku, partly because I’m the same way: Sudoku seems like a run computer problem, but tedious for humans (since you’re basically simulating slowly what a computer can do better). As far as I can tell, it’s completely unknown how to generate a genuinely “hard” instance of Sudoku, which I would define as being a puzzle with a single unique solution that requires very long chains of guesses before realizing that you made a mistake further up in the search tree. Thus, this leads to long search times, deep search trees, and much backtracking. The “hard” puzzles you find in books are basically just puzzles with lots of missing initial entries, but there’s no guarantee that the solution you find is unique (in fact, it’s not hard to use something like Prolog to write a Sudoku solver that will return

allthe solutions) or difficult to find.As a HW problem we solved (it was a group HW)

sudoku as a integer programming problem (binary to be precise). It was kinda fun, constraints defined the solution, so optimization just found one (of usually many feasible solutions to a given puzzle).

We did some “experiments”, where conclusion was that at least for the IP solver in Matlab, usually time spent in sudokus tagged hard really took a lot more time than those tagged easy.

Could it be that feasible region is just much larger in easy puzzles…

Pingback: Joe’s Pyramid « Journey into Randomness

Research on having fun with Sudoku continues:

http://11011110.livejournal.com/253704.html

As does the enumeration of hard instances:

http://www.ics.uci.edu/~eppstein/0xDE/impossible-sudokus.txt