Anyone good with a Rubix Cube?

This is a discussion on Anyone good with a Rubix Cube? within the C++ Programming forums, part of the General Programming Boards category; Before this gets modded, I would just like to say two things. Yes this is for a program. For a ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    155

    Anyone good with a Rubix Cube?

    Before this gets modded, I would just like to say two things. Yes this is for a program.

    For a project we must make a rubix-cube solver. However, most online tutorials are very baaad >.< I have my own cube to practice on but unfortunately the colors differ from online tutorials. I know it is good to start with the corners/edges of a given piece, etc, but it's just the whole algorithm of moving them so---


    Guargh. I just need to know if anyone can give me a good explanation on this. I can write the program (I think) but it's the blasted algorithms...

    Secondly, if it matters, my colors are:

    Red front, white left, orange back, yellow right, blue top, green bottom

  2. #2
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    Thats a hard one...

    An algo to solve a Rubik's Cube is not simple. Not simple at all.

    There are two ways you could do it, that I can think of right now.

    1) Eater of memory...

    Basically start with a cube object (with members for all the different individual cells on the surface) and make a doubly linked tree 12 nodes wide (representing each of the 12 basic transforms you can do to a Rubik's Cube) and iterate recursively down the tree, until you find a mutation which matches the state of the target Cube, then go back up the tree (hence the double linkage) outputting the states of the Cube at each point, so you know which transforms to apply.

    With this one you would cross your fingers that you arrived at a solution before you ran out of new.

    2) Pattern matching

    This one would be harder to set up but would be quicker and more efficient when run. You would basically (using some complicated voodoo coding or a helluva lot of processor cycles) create a data file contaiing the optimal solution to every unique state of the Cube (This could take a while) and then use that to find the optimal soluion for a given state of the Cube later on.

  3. #3
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    What kind of project is this, anyway? What level, and was the Rubik's Cube problem chosen by you or assigned to you?

  4. #4
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    I used to be able to solve it in under 2 minutes (drove across country once, had nothing else to do but to clock myself...), but lost my cube and have forgotten the algorithms.

    Basically the idea is to do the top layer first (not the top color, the top layer). Then the middle, then the bottom. Its hard to explain it and I dont have the time to try right now. But, probably the easiest way write the prorgram would be to have a semi brute force method.

    Code an algorithm that will solve the top layer (should be pretty straightforward), then have it brute force the middle layer and last layers (individually) with a max depth of, say, 15, checking each move to see if the current position has more cells in their proper position than before.

    It would really help if you knew how to solve it correctly if you want to code an efficient algorithm. I suggest you keep at it and dont give up on those sites. Look for one that has good pictures so you can visualize what they are trying to explain and be persistent.
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  5. #5
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    ...cool a java simulation, perhaps I can remember some of the algorithms
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  6. #6
    Evil Member
    Join Date
    Jan 2002
    Posts
    638
    It might be helpful to know the depth of the longest optimal solution to a Rubik's Cube. Effectively the optimal solution to the Cube in a state that is the most distant from being in a solved state possible. That you might be able to find out.

  7. #7
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    I saw on a website it was something like 65 from any position, so depending on how you store your cube-state you could easily do a completely brute-force method
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  8. #8
    Registered User
    Join Date
    Oct 2002
    Posts
    3
    Not to dredge up older posts...but in reality it is only a day old, and I think I can help a little. You might want to check out this website: http://home.t-online.de/home/kociemba/cube.htm - the guy wrote a really good program to solve the rubik's cube, and most times it solves so it requires less than 25 moves, and it only takes about a second to solve. He provides a description of the algorithm he uses. Right now it is believed that the cube can be solved from any position in less than 20 moves. Brute force isn't a good idea with the rubik's cube, you have to have at least some heuristics in there, otherwise it would take an eternity to solve. You might be able to get away with using A* turning the thing into one big path that it has to navigate, or maybe you'd do better to represent it as a bunch of smaller cubes and solve them individually and then look for the solution in that set that satisifies the requirments the whole cube.

    Edit: I found some C source code for a solver, you can get it here: ftp://ftp.externet.hu/pub/mirror/sac/educult/miker.zip
    Last edited by Entropic; 11-05-2002 at 06:06 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. In a game Engine...
    By Shamino in forum Game Programming
    Replies: 28
    Last Post: 02-19-2006, 11:30 AM
  2. Good books for learning WIN32 API
    By Junior89 in forum Windows Programming
    Replies: 6
    Last Post: 01-05-2006, 05:38 PM
  3. Good resources for maths and electronics
    By nickname_changed in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 12-22-2004, 04:23 PM
  4. what is good for gaphics in dos
    By datainjector in forum Game Programming
    Replies: 2
    Last Post: 07-15-2002, 04:48 PM
  5. i need links to good windows tuts...
    By Jackmar in forum Windows Programming
    Replies: 3
    Last Post: 05-19-2002, 12:16 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21