Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!ucsd!swrinde!cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!tank!cps3xx!eecae!netnews.upenn.edu!grad2.cis.upenn.edu!meuchen
From: meuchen@grad2.cis.upenn.edu (Paul Eric Menchen)
Newsgroups: comp.graphics
Subject: Re: Rubiks Cube
Summary: What type of solution?
Message-ID: <17537@netnews.upenn.edu>
Date: 1 Dec 89 04:13:40 GMT
References: <256@<4382> <207400039@s.cs.uiuc.edu>
Sender: news@netnews.upenn.edu
Reply-To: meuchen@grad2.cis.upenn.edu (Paul Eric Menchen)
Distribution: usa
Organization: University of Pennsylvania
Lines: 50

In article <207400039@s.cs.uiuc.edu> mcooper@s.cs.uiuc.edu writes:
>
>/* 4237_5202@uwovax.uwo.ca in s.cs.uiuc.edu:comp.graphics */
>>I am working on a 3-d graphics application in GKS and C
>>on a sun workstation to simulate Rubiks Cube.  Does anyone have
>>an algorithm to solve the cube or suggestions for structures.
...[stuff deleted]
>Well, the easiest solution I see is hitting up libraries and garage sales
>for the avalanche of book published in the early 80's called
>'How to solve Rubik's Cube' or variations thereof...

After reading about three of four posts concerning this, I began
thinking (uh oh, trouble).

What kind of solution is desired?  The way I solved the cube and the
way most of the book solutions I suppose went would follow a sequence
of first getting one side (actually a layer, I would make sure each
piece didn't have just, say green of the face, but the correct
color(s) on the other face(s)), then the middle layer (that is, the
middle if the side already solved is considered the top layer) along
with non-corner pieces of the bottom, and then the bottom corner
pieces. What I'm leading to is this ...

My solution is not the most efficient in terms of number of moves, but
doesn't require an inordinate amount of time to determine those moves.
I had it down to about 3-5 minutes or so after a while. My thinking
didn't look that far ahead though.  I solved the top layer first without
even considering what I was doing to the rest of the cube.  A computer
solution should, I think, be more holistic depending on what kind of
solution you want.  

Here are a few types of solution criteria.  Each could be implemented
by a number of algorithms:

   1)Least number of moves. This I think would take lots of time.
        My algorithm wouldn't fare well for this criteria.

   2)Fastest, Computer CPU time.  This I'm not sure about. My solution
        might fare well, but I'm not sure.  Its a trade off between
        number of moves made and considered vs. depth of thought. 
        
My summary:  Those books were made for human minds that couldn't solve
the cube on their own, and thus don't require much depth of thought.
A computer solution should probably not be based on these solutions,
except perhaps to solve it based on some criteria such as speed, but
maybe not even in this case.

Paul Eric Menchen
meuchen@grad1.cis.upenn.edu
    


Brought to you by Super Global Mega Corp .com