~~~ From:

~~~ ~~~ Subject:

There are some standard algorithms involving time-memory tradeoffs for solving

problems like Knapsack in N^(1/2) steps instead of N...Hellman had a paper

in some IEEE journal about an application to breaking cryptosystems. The same

could be applied to solving the cube "exhaustively", given several hundred

billion memory locations storage and a willingness to go through a similar

number of table-lookups. Just make a table of all the positions that can

be reached within 10 meoves or less (with the route to that position recorded

too!)...then in order to solve an arbitrary cube set-up, begin working out

from that set-up, looking for a position included in the table. If Singmaster

is right and any position can be reached in 20 moves or less, one will

always succeed within 10 moves from the arbitrary start....

The several hundred billion entries in the table are a bit too large for my

home computer, but perhaps a smaller sub-group of the cube (slice, or

anti-slice, or such) could be done this way in a reasonable amount of time....

Hellman seems to think that solving the DES (which has 2^56 keys, I think) is

not impractical, given enough money and a few years.

How about a competition to find the shortest ways to get to the Crux

Christmanni & Plummeri(?)...a simpleminded corner-shifting I tried took 84

moves, I think, to get whichever one has two cycles of 3 colors...that leaves

lots of room for improvement! --Mark