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