[teknomage1]

Solving is harder than pure generation because you're searching for a specific solution.
I think you can be a bit smarter in your generation if instead of generating random digits 1-9, you instead make pools of numbers (I would use linked lists to represent the pools), and remove digits from the pool as you fill in the puzzle row by row. If I understand the rules of the game correctly, you'd need one pool for each column, one for each row, and one for each of the 9 3x3 blocks.

So you algorithm would be to randomly generate the first row, remove the digits you used from the corresponding pools, then as you generate each consecutive row, you pull a number from that row's pool, check to see that the digit you are trying to assign is in the column's pool, and the block pool before you assign it, then remove it from the pools. If your number is missing from one of the pools, go back to the row pool and try again.
It should guarantee that anything you generate is a valid puzzle board. I'm not sure if it will get stuck in an unassignable state towards the end though.