[next] [prev] [up] Date: Thu, 25 Sep 80 08:59:00 -0400 (EDT)
~~~ [prev] [up] From: Mark Zimmermann <ZIM@MIT-MC >
~~~ ~~~ [up] Subject: search-from-both-ends ultimate cube algorithm

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

[next] [prev] [up] [top] [help]