There is a pattern to the following simple solution (for each row, shift the previous by 3: caveat: when you reach a boundary (eg row 4/7) shift the first row of the previous block by 1). You can create this pattern every time, or just have them saved in memory:
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 4 5 6 7 8 9 1
5 6 7 8 9 1 2 3 4
8 9 1 2 3 4 5 6 7
3 4 5 6 7 8 9 1 2
6 7 8 9 1 2 3 4 5
9 1 2 3 4 5 6 7 8
Now shuffle...randomly swap rows and columns that belong to the same 'block' (eg row 1 and 2, column 4 and 6, etc...I'm using 1-based integers here). Swap as many as you want to randomize. Each time you do this you are generating a pseudo random puzzle (and it holds true for other dimensions, just the block and shift size changes). You can also save this solved puzzle as a 'seed' to the next randomization. There is no necessity to backtrack or use brute force. Its actually, in my opinion, a bit elegant.