A different idea:
when producing a random start configuration of the cube, do it the way that you create the cube with every color at place as if it were solved, and then make a certain number of random 'turns' to get the start position for the player, save these steps.
When the player starts his turns save them, too.
The solution way is then, that you follow back all steps.
Okay, that's more than brute, but it is a save, although not a very satisfying, solution...