4237_5202@uwovax.uwo.ca (11/25/89)
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. I am currently working on the users interface, asking what areas to move or to view the cube differently. I will post my solution to anyone who offers help. Thanks Brian CS UWO third year
woody@rpp386.cactus.org (Woodrow Baker) (11/28/89)
In article <4382.256d6784@uwovax.uwo.ca>, 4237_5202@uwovax.uwo.ca writes: > 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. > I am currently working on the users interface, asking what areas > to move or to view the cube differently. > > I will post my solution to anyone who offers help. > > Thanks Brian CS UWO third year Try going back to 1980 or thereabouts in Kilobaud, or most of the computer magazines right after the cube came out. There are any number of cube solvers and visuals there. for my money, I would use a 3 dimensioned matrix and play with that for keeping the cube faces straight. There is an excellent book, that is titled something like "rubiks magic cube" or something similiar. It went deeply into the probablilities, possibilities and proofs and math on the cube... cheers Woody
josh@cditi.UUCP (Josh Muskovitz) (11/30/89)
In article <4382.256d6784@uwovax.uwo.ca>, 4237_5202@uwovax.uwo.ca writes: > I am working on a 3-d graphics application in GKS and C > on a sun workstation to simulate Rubiks Cube. [text deleted] > Thanks Brian CS UWO third year Congrats on a good challenge, but Silicon Graphics gives it away as a demo with any of their machines. If it doesn't seem like cheating to you, maybe you could look at it and solve their user interface problem. josh muskovitz computer design, inc. josh@uunet!cditi
mcooper@s.cs.uiuc.edu (12/01/89)
/* Written 3:08 pm Nov 24, 1989 by 4237_5202@uwovax.uwo.ca in s.cs.uiuc.edu:comp.graphics */ /* ---------- "Rubiks Cube" ---------- */ 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. I am currently working on the users interface, asking what areas to move or to view the cube differently. I will post my solution to anyone who offers help. Thanks Brian CS UWO third year /* End of text from s.cs.uiuc.edu:comp.graphics */ 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... Ther's a ton of them. You should be able to find one. Converting the cube moves into 3D matrix manipulation seems fairly trivial. The hard part seems to me to be writing the pattern matching algorithm. Most 'cube-solver' books had a set number of moves for a certain situation. i.e. if one face is all one color, but the corners of the face are switched, do this set of moves, etc... All you'd have to do is recognize the patterns and do the appropriate moves. +-------------------------------------+----------------------------------------+ | "When the going gets weird, | | | the weird turn pro." | Marc Cooper mcooper@cs.uiuc.edu | | | University of Illinois, C-U | | -Hunter S. Thompson | | +-------------------------------------+----------------------------------------+
meuchen@grad2.cis.upenn.edu (Paul Eric Menchen) (12/01/89)
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
phorgan@cup.portal.com (Patrick John Horgan) (12/02/89)
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! Patrick - Rather code than play with a cube - Horgan
mcooper@s.cs.uiuc.edu (12/03/89)
/* Written 11:44 am Nov 29, 1989 by josh@cditi.UUCP in s.cs.uiuc.edu:comp.graphics */ In article <4382.256d6784@uwovax.uwo.ca>, 4237_5202@uwovax.uwo.ca writes: > I am working on a 3-d graphics application in GKS and C > on a sun workstation to simulate Rubiks Cube. [text deleted] > Thanks Brian CS UWO third year Congrats on a good challenge, but Silicon Graphics gives it away as a demo with any of their machines. If it doesn't seem like cheating to you, maybe you could look at it and solve their user interface problem. josh muskovitz computer design, inc. josh@uunet!cditi /* End of text from s.cs.uiuc.edu:comp.graphics */ 1) SGI doesn't give source to their demos... (or at least I've never seen it. If I had, I would have modified 'Insect' to my liking long ago! :-) ) 2) As you pointed out, the interface to actually manipulate the cube on said demo is a problem. Keep in mind, though, that this was probably not written as a real cube simulation that was expected to be used with any serious effort at actually SOLVING the darn thing. 3) It will not solve the cube for you once it's scrambled. The original note suggested his program was supposed to simulate and SOLVE the cube... +-------------------------------------+----------------------------------------+ | "When the going gets weird, | | | the weird turn pro." | Marc Cooper mcooper@cs.uiuc.edu | | | University of Illinois, C-U | | -Hunter S. Thompson | | +-------------------------------------+----------------------------------------+
murphy@mfci.UUCP (Tom Murphy) (12/04/89)
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
gavin@krypton.sgi.com (Gavin A. Bell) (12/05/89)
mcooper@s.cs.uiuc.edu writes: >Congrats on a good challenge, but Silicon Graphics gives it away as a demo >with any of their machines. >1) SGI doesn't give source to their demos... (or at least I've never seen it. > If I had, I would have modified 'Insect' to my liking long ago! :-) ) Silicon Graphics will provide source code to most of the demos shipped on our machines for a duplication fee and your signature on a non-disclosure agreement (we try to keep straight ports from being done to our competitors' hardware). Last I heard the fee was about $100.00. The source code to both cube and insect is available (along with the flight simulator, etc). >2) As you pointed out, the interface to actually manipulate the cube on said > demo is a problem. Keep in mind, though, that this was probably not > written as a real cube simulation that was expected to be used with any > serious effort at actually SOLVING the darn thing. Yup, originally written in 1982 for the original Silicon Graphics machines just as a demonstration of the graphics capabilities. User interface design was not a priority. >3) It will not solve the cube for you once it's scrambled. The original note > suggested his program was supposed to simulate and SOLVE the cube... Yup, the closest it comes to solving the cube is a 'reset' option. --gavin
deutscherd@chisel.UUCP (Dale Deutscher) (12/05/89)
The July/August 1988 issue of PC AI has an article by Dennis Merritt describing a solution for Rubik's Cube written in Prolog. It doesn't contain all the source code, but has an address where you can get a copy. You can reach PC AI at: 3310 West Bell Rd., Suite 119 Phoenix, AZ 85023 602-439-3253 The article claims that well-documented source code and an executable version is available for $20 from the author at: Mynorca 30 Pembroke St. Newton MA 02158 Good Luck!
rener@cs.eur.nl (Rene Roelofs) (12/05/89)
murphy@mfci.UUCP (Tom Murphy) writes: >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. Not exactly true! If you take the cube and turn around say one corner (by breaking it out and replacing it again) then it is not possible to solve the puzzle. Therefore the permutation are less. ( I'm not gonne give a correct list ) And so the solving on a computer with the assumed speed should go faster, maybe it is when you leave all the 'wrong' permutations out, it is possible to solve in in less then ONE MILLION YEARS :-))). -- |-----\ Rene Roelofs | | Dept. of Computer Science /|-----/ Erasmus University Rotterdam, The Netherlands \| \ uucp: mcvax!hp4nl!eurtrx!euraiv1!rener /| \
murphy@mfci.UUCP (Tom Murphy) (12/07/89)
In article <1989Dec5.090928.9422@cs.eur.nl> rener@cs.eur.nl (Rene Roelofs) writes: >murphy@mfci.UUCP (Tom Murphy) writes: >>(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. > >Not exactly true! If you take the cube and turn around say one corner >(by breaking it out and replacing it again) then it is not possible to >solve the puzzle. >Therefore the permutation are less. ( I'm not gonne give a correct list ) >And so the solving on a computer with the assumed speed should go faster, >maybe it is when you leave all the 'wrong' permutations out, it is possible >to solve in in less then ONE MILLION YEARS :-))). And maybe not :-) . The numbers I stated were for different valid positions. Physically altering locations of cubes can make solution time quite long :-). Most of the factors in the above expression are smaller than what they would be if you allowwed use of a screwdriver in the solution of the cube. It may be faster (and more straightforward) to solve the Towers of Hanoi than to brute force the cube. 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
ron@vicorp.UUCP (Ron Peterson) (12/08/89)
In article <207400042@s.cs.uiuc.edu> mcooper@s.cs.uiuc.edu writes: >1) SGI doesn't give source to their demos... (or at least I've never seen it. > If I had, I would have modified 'Insect' to my liking long ago! :-) ) You can get source to many of the SGI demo's! Just call the HotLine and ask them to find who to send a tape to. I have the source to insect and have had fun making multiple spiders---slowed my 3030 down *real* fast though.
nigel@hp-ptp.HP.COM (Nigel_Clunes) (12/19/89)
If solving the cube is the purpose of the exercise, then my suggestion below is of no used. However if the purpose of the exercise is the graphics, then do it the easy way as follows. 1. Start with a "solved cube". 2. Make a random move on the cube. 3. Push the move onto a stack. 4. Repeat steps 2 and 3 the desired number of times. 5. Display the current state of the cube. 6. Now pop a move off the stack and reverse the move on the cube. 7. Display the cube in its new state. 8. Repeat steps 6 and 7 until the stack is empty. 9. Done. Another way is to save the state of the cube on the stack as each random move it made. Then simply pop each cube state off the stack and display it. Gook Luck with the project. If you get it working, please post a copy into one of the source groups.