My gut-feeling is that building Sudoku puzzles shouldn't be too hard to generate, because every random choice you make reduces the space you need to pull from for the next choice.

Whether they're "hard enough to solve", though....

The difficulty comes from multiple solutions to your puzzles (which would force the player to guess). As it turned out, a purely randomly selected puzzle would 99.9%* of the time give you a puzzle with multiple solutions. I would have settled for 99%, but more was too much server resources to hog!

And then add the screening for difficulty levels.

*Not an exact figure =)

The sudoku difficulty can be very varied, but it doesn't rely on multiple solutions - a grid where multiple solutions are possible simply isn't a valid sudoku puzzle; a minimalistic puzzle is one where no numbers can be eliminated without losing uniqueness of the solution, but adding extra numbers to that minimalistic puzzle makes it easier.

Would you happen to know of a minimalistic puzzle approach? I've read about some, like at least 17 squares and 8 out of 9 numbers presented. It didn't actually worked out in tests, so I abandoned that approach. At some point, testing theories became a viable way of generating puzzles, so I went with the random approach instead. But of course, for an efficient program, developing parameters for minimalist is best. I have parameters that increase the success rate to 25% or so...

All my puzzles have unique solutions. I said the difficulty of generating is from multiple solutions, not that the puzzles are difficult because of them.

Ah, I misunderstood you - true enough, the multiple solutions cases slow down a random generation as the candidates have to be checked and eliminated.

> As it turned out, a purely randomly selected puzzle would 99.9%* of the time give you a puzzle with multiple solutions.

Ah, I see what you mean, you're not talking about generating the intended solution, you're talking about which cells TO BLANK before giving it to the user.