There have been a number of threads lately talking about Sudoku, a Japanese (?) numeric crossword-like logic puzzle. They’re apparently something of a fad these days; while I’ve never seen them in the newspaper, a number of Dopers’ papers apparently print them now.

Anyway, I enjoy them, and I’ve got a program that generates them for my PocketPC. But…it seems to generate a fairly small set of them (it claims 5000 or so, but I’ve gotten the same one several times), the set it does generate seems pretty similar in form, and the user interface, to put it gently, sucks.

So I want to write a program to generate (not solve, which is easy) them myself. I’m not immediately seeing an algorithm, however.

Sudoku rules: a 9x9 grid, broken up into a 3x3 grid of 3x3 spaces. Each row and column of the main grid must have each numeral from 1 - 9 exactly once. Each 3x3 subgrid must have each numeral from 1 - 9 exactly once. A “puzzle” is a grid with some of the numbers filled in initially: the solver must start from this configuration.

A “valid puzzle” is one which has a single unique solution from the initial grid: no more, no less. An empty grid would not be a valid puzzle, for example (since there are a very, very large number of possible combinations). Nor would a puzzle with only one or two squares filled in: again, there would be multiple combinations.

It’s easy (well, not trivial, but relatively easy) to generate a “solved” grid of numbers. From this, I must determine a set of “clue” numbers to leave in the grid that (a) allow enough information to solve the puzzle, and (b) allow only a single solution. I’m pretty sure that (a) is a subset of (b).

Even better, many Sudoku programs claim to be able to produce puzzles of varying difficulty. The “difficulty” appears to be more than just a simple “number of clue squares” – I’ve seen “hard” puzzles with more initial numbers filled in than “easy” ones, for example. Ideally, I’d like to have a user-selected difficulty as part of the algorithm.

Just to make this tough, I’d like the algorithm to be comprehensive: it should be able to generate ANY valid puzzle – I don’t want it to be like the app that I’ve got that seems to generate only a few different puzzles, with a few simple variations.

So, anyone whose been doing these for a while care to guess (or tell) an algorithm for generating them? Plain English is fine, no need to drag this down to the code level.