From news@nntp-server.caltech.edu Fri Dec 16 15:36:21 1994 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29220; Fri, 16 Dec 94 15:36:21 EST Received: from gap.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id MAA19196; Fri, 16 Dec 1994 12:36:15 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id MAA02485; Fri, 16 Dec 1994 12:36:07 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: txr From: txr@alumni.caltech.edu (Tim Rentsch) Newsgroups: mlist.cube-lovers Subject: Re: Cyclic Decomposition Date: 16 Dec 1994 20:36:05 GMT Organization: California Institute of Technology, Pasadena Lines: 23 Message-Id: <3cstnl$2dj@gap.cco.caltech.edu> References: <60.897.5834.0C1C4371@canrem.com> Nntp-Posting-Host: alumni.caltech.edu X-Newsreader: NN version 6.5.0 #4 (NOV) 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? regards, Tim Rentsch