Sudoku puzzles are Assignment problems (http://en.wikipedia.org/wiki/Assignment_problem), and can be cast as Graph Coloring problems as well (http://en.wikipedia.org/wiki/Graph_coloring).

Although the performances reported are more than good, the discussion on brute-force algorithms omits that some of the cutting-edge research on the topic is in the Constraint Programming community (Sudoku is the typical example of the "all-different" modeling constraint).

One of the most commonly used algorithm used in Optimization (and in feasibility problems as well) is Branch and bound (http://en.wikipedia.org/wiki/Branch_and_bound). Combinatorial problems of that size are relatively small and can be solved in fractions of a second by off-the-shelf commercial software and very little modeling work.

Norvig has some great solutions. However I have still yet to see something that can beat a well coded dancing (http://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku... http://en.wikipedia.org/wiki/Dancing_Links) links solution to Sudoku, for speed.

For my money, giving humanistic solutions for sudoku is the more interesting problem. The size of the search space is so constrained that a correctly coded solution will finish so quickly that it's no longer an interesting race. Rating puzzles for how much trouble a real person will have solving is also very interesting.

If you want a "seriously hard" puzzle for optimization testing, scale up. What happens if you feed the program a 16x16 or 25x25 or 100x100 Sudoku?

If this is brand new to you, don't miss the TDD vs BPNDD ("Being Peter Norvig Driven Development"), recently discussed here http://news.ycombinator.com/item?id=3033446

edit btw I certainly don't mean to fan any flames of pro or anti TDD, I just think there's some interesting stuff to discuss.

In his section talking about the brute force method of solving the puzzle, he seriously overestimates the number of possibilities for the whole puzzle.

Example: For grid2, he lists square A2 as having 4 possibilities (1679) and A3 as having 5 possibilities (12679). Which is true, if you ignore the rules of sudoku. Specifically, not all of those combinations are worth trying. If you choose a 1 for square A2, you would not choose a 1 for square A3.

Wikipedia lists there as being 10^21 unique sudoku puzzles, which is many orders of magnitude smaller than his listed 10^38 different combinations for grid2.

In short, I think a proper brute force method would be significantly faster than what he initially thought it would be.

I became interested in Sudoku solving recently, and although I was aware of this essay, I wanted to study the problem first without knowing anything about constraint propagation:

http://cjauvin.blogspot.com/2011/10/journey-into-sudoku-spac...

Next I read the article, and then tried to adapt my previous, naive method with the CP ideas:

http://cjauvin.blogspot.com/2011/10/wormhole-through-sudoku-...

This one pops up from time to time; always an interesting read though.