[next] [prev] [up] Date: Fri, 16 Dec 94 20:36:05 +0000 (GMT)
[next] ~~~ [up] From: Tim Rentsch <txr@alumni.caltech.edu >
[next] [prev] [up] Subject: Re: Cyclic Decomposition

mark.longridge@canrem.com (Mark Longridge) writes:

Certain states, such as the 12-flip, require quite a few moves, in
fact more moves than possible to search using brute force even when
using high-order computers. The best results using the Kociemba
algorithm need 28 q turns or 20 q+h turns for the 12-flip.

I found Mark's post generally interesting and thought provoking.
Without detracting from his ideas I would like to comment on the
paragraph above.

If a certain state (such as the 12 flip) is known to be reachable
in no more than 20 moves, then isn't that state within reach of
a brute force search? Start one brute force at the initial state,
one at the final state, expand the position trees one move at a time
until the trees touch. A state 20 moves from start will require a
tree (well, two trees) 10 moves deep, which is about 10 billion states.
That seems achievable in a reasonable time on fast computers of today.
Doesn't it?


Tim Rentsch

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