Path: utzoo!attcan!uunet!mfci!murphy From: murphy@mfci.UUCP (Tom Murphy) Newsgroups: comp.graphics Subject: Re: Rubiks Cube Message-ID: <1149@m3.mfci.UUCP> Date: 4 Dec 89 02:10:07 GMT References: <256@<4382> <207400039@s.cs.uiuc.edu> <17537@netnews.upenn.edu> <24647@cup.portal.com> Sender: news@mfci.UUCP Reply-To: murphy@mfci.UUCP (Tom Murphy) Organization: Multiflow Computer Inc., Branford Ct. 06405 Lines: 43 In article <24647@cup.portal.com> phorgan@cup.portal.com (Patrick John Horgan) writes: > > Maybe I'm missing something, but isn't this just a search? >I mean, a depth first search with backtracking would rapidly find >a solution...Perhaps not with the fewest moves though...for that >use a bredth-first with pruning of branches that are already over >our best progress yet...Throw in some appropriate heuristics...I >believe some of the "solution books" would be a good source for >these...to prune off obvious bad paths, and there you go! This is good attact method in general, not good in specific for the Rubik's solution :). Suppose an algorithm and computer capable of displaying one million different permutations of the cube a second. It will still take over a million years to display all permutations containing one of the 2048 different solutions. As H. Callahan queried, "Do you feel lucky?". Intuitive Justification for numerical claims => 1) There are eight corners which gives 8!=40,320 permutations of where they can be. 2) Each corner has three positions it can be in one of which are correct. Positioning seven turns out to automatically position the eigth. Thus have 3^7=2187 different orientations of the corners. 3) This leaves placing the 12 edge blocks in the correct position. It turns out there are 12!/2=239,500,800 different permutations of them. 4) There are two positions each of the edge blocks can be in. Positioning 11 automatically positions the twelfth. Thus we have 2^11=2048 different orientations of the edges. 5) Each of the six centers of the faces can be in one of four positions. It turns out there are 4^6/2 = 2048 different ways to orient them. (40,320)(2,187)(239,500,800)(2028) = 43,252,003,274,480,856,000 possible permutations if we are unconcerned about the orientation of the center, which is true for non-logo'd cubes. Tom Murphy internet: murphy@multiflow.com Multiflow Computer, Inc. uucp: uunet!mfci!murphy 12 Del Rio Ct fax: (415) 943-1574 (call voice first) Lafayette, CA 94549 voice: (415)943-6293 Brought to you by Super Global Mega Corp .com