Sudoku-based puzzles?

Target Audience: Everyone

I've been seeing these Sudoku things all over the place recently. From a mathematical standpoint, they don't seem to be incredibly interesting; after all, there are only a few useful techniques for solving them, and the quickest methods seem to be based on guessing. This got me to wondering, however, if there were any puzzles based on Sudoku that might be interesting?

In case you've been living under a rock for the past year, a Sudoku is a 9x9 magic square in which each column, each row, and each of nine 3x3 boxes contains each digit from 1 - 9 exactly once (there is no such restriction on the diagonals). The square is presented with most of the numbers missing, with just enough information supplied to force a unique solution, and the reader is asked to fill in the remaining squares. For example,



(The puzzle above is from an outside source which changes daily, so I have no idea what it looks like at the moment you're reading this.)

There is some precedent for basing puzzles on games which are either mathematically uninteresting or, at the other end of the spectrum, too complicated for a mathematical solution at present. There is, for instance, the famous Knight's Tour, in which the victim is asked to place a knight on a chessboard and move it in such a way that it visits all 64 squares exactly once. For those who haven't tried it, there is a solution, but it is not the sort of thing one can work out without pencil and paper.

Of course, there are a couple things which come to mind -- you could ask how many distinct Sudoku there are, up to rotation, adding the stipulation that removing any of the clue numbers would give the puzzle extra solutions. I'm sure this will turn up as a question in some of the higher-end math contests; the solution would presumably involve a good deal of rather tedious combinatorics. Or you could take a page from Sam Loyd's book, and try to come up with impossible Sudoku whose impossibility was evident only to those with computer assistance or the incredibly patient. Neither of these seems to be particularly enjoyable or novel, however, and at the moment I'm at a bit of a loss.

Does anyone out there have some clever ideas for Sudoku-based puzzles? I'd love to hear them. Currently, I'm looking into a couple ideas of my own to see if they pans out; this post will be updated with the news when that happens. Oh, and if you're not familiar with Sam Loyd, the great American puzzle writer, you should be; check out the book below, edited by no less than Martin Gardner.