Anyone good with a Rubix Cube?

**Nakeerb** · 11-03-2002

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

**Imperito** · 11-03-2002

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.

**Imperito** · 11-03-2002

What kind of project is this, anyway? What level, and was the Rubik's Cube problem chosen by you or assigned to you?

***ClownPimp*** · 11-03-2002

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.

***ClownPimp*** · 11-03-2002

...cool a java simulation, perhaps I can remember some of the algorithms

**Imperito** · 11-03-2002

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.

***ClownPimp*** · 11-03-2002

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

**Entropic** · 11-05-2002

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

Thread: Anyone good with a Rubix Cube?

Thread Tools

Search Thread

Display

Anyone good with a Rubix Cube?

Similar Threads

In a game Engine...

Good books for learning WIN32 API

Good resources for maths and electronics

what is good for gaphics in dos

i need links to good windows tuts...