A few entries ago I wrote about trying to create a Sudoku puzzle generator. As I expected at the time, it is a rather daunting project (especially with the Christmas Holidays coming up!) The good news is that the English translation of the Japanese site that I’ve gotten the instructions from is getting closer to completion, so I can at least see how far I’ve got to go!
What I find interesting, however, is the number of programs that bear titles like "Sudoku Generator." A google search of this phrase turns up dozens (hundreds? thousands?) of these programs, but most of them are in fact "Sudoku Solvers." The difference, of course, is that a solver expects you to enter the numbers that would appear in the newspaper-puzzle (the starting point), and it will tell you what the solution(s) is(/are). No, I’m looking for the greater challenge: Start with a blank piece of paper (or collection of phosphor) and end up with the newspaper equivalent!
Some sites and programs that actually generate puzzles do it in a brute-force method of simply screaming through the zillions of possibilities until it finds an 81-number solution that works, and then removes 50, 55, or 60 numbers and says "Done!" This, from what I’ve learned, isn’t always the best approach, because you can end up with puzzles that are unsolvable without guessing, or puzzles that have more than one solution. (Both are apparently considered rude in the Sudoku community.)
Another approach I recently found says "Start with a puzzle you already know, and juggle the columns and rows around, then permutate each set of 1’s to another digit, 2’s to another, 3’s, etc., and then randomly erase values." This would apparently speed up the creation dramatically, but A) doesn’t appear as elegant, and B) doesn’t avoid the above two problems.
So, again, I’m trying to turn the Japanese-to-English instructions on how to build a puzzle by hand into VB code. Some progress (I made it halfway through Step 2, Beginner), but not there yet.