Tilted Twister: A Lego Mindstorms robot that solves Rubik’s cube
tiltedtwister.com
tiltedtwister.com
I am waiting for 2.0 but maybe you could find some deals on the 1.0 versions.
Just FYI
presumably you'd be able to set this up in Linux but don't quote me on that.