I like the rescramble idea. You could maybe go one step further by varying the difficulty of the rescrambling - I'm not sure if there's an established distance metric between rc states (something like a levenshtein distance, "minimum-number-of-changes-needed"), but the program could shuffle the cube out to some threshold on that metric to get easy, medium, hard, etc.