I have recently read a book entitled
"Learning To Solve Problems By Searching For Macro Operators"

by Richard E. Korf (exact spelling not in my head).

In a nutshell the book discusses an algorithmic method of problem soving
by discovering useful operators. The method was applied to the 3D Rubik
cube and as I remember managed on average to solve the problem in about
37 - 38 QTW. Apparently it was slightly better than human experts. The
tables discovered by the program weren't terribly large :-)!

Also either in that book or another I remember an approach to the minimove
problem based on measuring the disorderedness of the cube after n random
moves. The measure of disorder was based on the number of correct colours
on each face or something like that. From a graph of this measure averaged
over (I suppose) some number of trials it seems as though the cube can be
maximally disordered in around 18 moves. It would seem that this means
that on average the cube should be restorable in about the same number of
moves.

Of course this doesn't help giving tight bounds, but I guess it gives
some hope to the clever guys.

As an aside I have something called a Supernova which is dodekahedral
(i.e. has 12 5 sided faces each of which can rotate) which is alledged
to be 10power 43 more complicated than the 3cube. I can solve it using
fairly standard cube methods (only the last face is slightly difficult)
in about 20 times my 3-bube time. Has anyone else seen this and or is
there any standard notation + information on this thing.
Robin (not batperson) Becker