## Minimum Sudoku

As I worked on my checkers program, I’ve gone to a number of bookstores looking for books on checkers. Unfortunately, checkers has gone the way of the dodo: you might find a copy of Pike’s book of Checkers problems, or maybe Hopper’s book, but literally nothing else is in print. It’s kind of sad, when you consider that at my local borders there is an entire rack, eight separate rows, of books on Sudoku puzzles, something I consider to be of very minimal interest. In fact, whenever I try a sudoku, I can’t help but think that the only reason these things exist is to motivate the writing of an automatic solver in the language of your choice.

Still, the puzzles themselves (as a class) have some interesting properties. One might ask “what is the minimum number of non-blank entries that a Sudoku puzzle can have, and still have only a unique solution?” Currently, it appears there are a number of 17 number puzzles, but no known instances of a puzzle with only 16 numbers. You can download 36,000+ puzzles that have only 17 numbers at the link below, and use them to test either your own abilities, or the abilities of the program you write.

CommentfrommetameristTime5/7/2007 at 5:54 am“In fact, whenever I try a sudoku, I canâ€™t help but think that the only reason these things exist is to motivate the writing of an automatic solver in the language of your choice.”

Ha! After working three puzzles, I found the idea of writing a solver much more interesting. Wrote a simple one.

Lance Fortnow’s Computational Complexity blog had some intesting entries on the subject (e.g., http://weblog.fortnow.com/2005/05/complexity-and-sudoku.html).