There are two basic issues here;

A) the way the Rockbox plugin works

B) the rating of difficulty of Sudoku puzzles

A) the way the plugin works(if I remember correctly) is to randomly add numbers to a blank grid in a symmetrical manner and see if it can be solved and has a unique solution. You might be able to tweak the algorithm to make it have more givens.

BUT

B) the number of givens is not a very accurate guide of how difficult a puzzle is - in one Christmas edition the NewScientist gave two puzzles with 17 givens (the minimum) one was fairly easy - the other a nightmare!

Programs like Simple Sudoku

http://angusj.com/sudoku/ seem to have a better algorithm based on what techniques the solver needs to use to solve them (the Rockbox one is brute force), you could pre-calculate a load then put them on your player.