After numerous tries of trying to solve a Rubik's cube with A-star, i have given it up. The cube just has to many nodes to search (40 quintillion i believe). So I decided to come here. So here is the problem: I want to solve the Rubik's cube :) with AI. I myself can do it, but i can't seem to find a way to program it. I am not looking for a best solve (<20 moves) because that requires profile tables, etc.. and you need databases for that, which I have not learned about yet. Here is how i would like the cube to be solved: -Solve the white cross; -Solve the white layer; -Solve the second layer; -Orient the Yellow edges; -Permute the Yellow corners; -Orient the Yellow corners; -Permute the Yellow edges; ==> solved. This is a beginner method to solve the rubik's cube. Now i already have the classes to represent cubepositions and how to perform moves on them to get other cubepositions. Is there anyone here who can help me with some Pseudocode to solve the two first layers (white and the middle layer)? After that, I can manage because after that you only need do some (Well known) movesequences to get to the solved position. And preferably something that is executed really fast :) . Because theoretically i can solve the cube with Dijkstra's algorithm... but then i have to search 12^20 nodes :). I think you in advance.

How do you yourself go about finding the white cross? What's the penultimate step just before finding the white cross? Can you reach that? Or the step just before that?

Even if you just have those steps, without working out how to get to them, you've seriously cut down on the amount of searching required to reach each one. If the white cross is, say, a maximum five moves away, then that's only, what, 12^5 possible nodes you have to search, minus loops. That's a blink of an eye.

If, however, you can work out what rules you yourself are using to get to each step, even just working out what the penultimate step should look like, you'll be able to cut it down even more.

(Note, I've never solved a rubick's cube before, or programmed a computer to do it either...)

well i've tried to get the whitecross solved with A-star, but the problem is, that the algorithm gets terribly slow because after depth 4, i already have 20000 nodes on my open list, and that list needs to be sorted every iteration (i do it after 50 iterations) and every iteration it needs to check wether a certain node is on the list. And that causes LOTS of overhead.

And also the heuristic i am using is very , well, crappy. I'm just counting the correct faces. A good heuristic would be one where i would know how many steps i am from the solved position (or solved to white cross position). But i need a database for that, but that's something i don't know anything about that.


And I know it is possible to solve the cube without databases because many applets on the internet do it (using the steps in my firs post), but the source code isn't available :(. The only code or pseudo code i can find, is from universities who write papers about optimal solutions (gods's algorithm), but again, that is with profile tables and stuff..

*edit* The way i solve the 2 first layers is with pure logic. But you should try explaining that to a pc...

There is a load of work on the subject, search around.

If you dont want an optimal solution, its easy. You just need to solve a simpler problem first: You can find (through A* or other means) a series of rotations that will permute two squares whiles keeping all others in their original position. Once you have that for all non-symetric cases, its a piece of cake to queue all necessary permutations and compute the complete solution.

Quote: The way i solve the 2 first layers is with pure logic. But you should try explaining that to a pc...

...?...I'm inclined to think that explaining pure logic would be the easiest thing to do though I didn't post just to say that. What kind of instructions are you trying to program? The instructions that came with my rubik's cube were step by step and easy to read so if you can get instructions like that it should be just a matter of translating them into whatever language you are working in. A quick google on rubik's solutions returned this: http://jeays.net/rubiks.htm#sol1 . It lists the possibilities at each step and what to do in a way that looks like it could translate well into a simple( albeit long) if else structure.

Quote: from page linked to above

I should point out that these are both beginner-level solutions. They are easy to learn (in particular Solution #2). If you want to be able to solve the cube in 20 seconds, this is not the page for you: check out the speed cubing links later on in the page. The faster solutions generally require considerably more memorization and practice.

I've never done this personally so I'm not certain, but unless you are trying to get an optimal solution I don't think you will need something like A* . If it's possible, using pure logic will probably be easier( and faster) than using a search tree. There does seem to be a wide range of solutions varying in difficulty and speed(number of moves required to solve) so it could take quite a bit of searching to find the best method for your particular case.

Here's a neat little idea. Why not try using a genetic algorithm?

You know that you only need a maximum of N moves to solve a Rubik's cube. Personally, I've never solved one, but I would believe that this value is finite with a fixed upper bound. So, let's just say we can solve it in less than 40 moves no matter what.

Now we then fix the orientation of the cube and count all the possible moves and that would be our domain space. The GA will have individuals of length 40, where each value is a move. So, then you randomly generate your population and evaluate a candidate solutions by iterating through the moves until you either reach a solution or get to the end of 40 moves. At this point, you penalize the "move sequences" that do not solve the cube based on some fitness value, say, like how many in complete faces factoring in how incomplete. You might have to mess around with your crossover and mutation, but I believe you'll be able to successfully find A solution. To get the optimal or better solution, you might have to give shorter "solution sequences" a higher fitness.

Ok, I'm not sure if this will work, but it sounds like it is possible.

I don't think using a GA for the Rubik's cube is a good idea. You can almost certainly get a solution, but I think finding the solution itself will be very difficult, i.e., lots of generations. You'll have to battle stagnation and population convergence violently to keep it from getting lost. Also, there is a significant possibility that your answer will have redundant or self defeating moves (turn right, turn left, turn right). Putting the pieces in place to prevent this will likely be more work than a good tree search algorithm.

I think you've already described the answer to your problem. You can use A* for each segment of the solution you describe. Work toward the white cross as your goal using A*, disregarding any effects outside just the white cross. Then get the corners without disturbing the cross to get a single side.

As far as databases go, you could easily come up with a basic representation for specific scenarios. For example, to get to the white cross, there are very simple ways to move an edge block from an particular position to the position you want within a few moves. You could set up a series of moves that would accomplish your goal to reduce your search try. For example, "move lower left to upper front" can be done in two twists - lower clockwise, front half turn. This would be slightly more complicated if you want to prevent disrupting other cubies, but those can be figured out. The hard part would be determing the state of the cubies you want to move and matching them to the right set of moves. Very doable.

I hope this helps. Let me know if I can clarify.

-Kirk

Okay, it has taken me a MASSIVE ammount of coding to get loads of movesequences, but so far, i've gotten my program to solve the first 2 layers in a respective time-period (for searching the path that is)..

Though it takes about 150 moves to much :). But i'm trying to get that number down with some smaller movesequences.

So to give you an idea :
Rubik.rar

unzip anywhere and run RubikSolver.exe

for those who don't have the managed directx libraries (by default NOT installed with directx)

mdxredist.msi

Quote: Original post by kirkd
I don't think using a GA for the Rubik's cube is a good idea. You can almost certainly get a solution, but I think finding the solution itself will be very difficult, i.e., lots of generations. You'll have to battle stagnation and population convergence violently to keep it from getting lost. Also, there is a significant possibility that your answer will have redundant or self defeating moves (turn right, turn left, turn right). Putting the pieces in place to prevent this will likely be more work than a good tree search algorithm.

I think you've already described the answer to your problem. You can use A* for each segment of the solution you describe. Work toward the white cross as your goal using A*, disregarding any effects outside just the white cross. Then get the corners without disturbing the cross to get a single side.

As far as databases go, you could easily come up with a basic representation for specific scenarios. For example, to get to the white cross, there are very simple ways to move an edge block from an particular position to the position you want within a few moves. You could set up a series of moves that would accomplish your goal to reduce your search try. For example, "move lower left to upper front" can be done in two twists - lower clockwise, front half turn. This would be slightly more complicated if you want to prevent disrupting other cubies, but those can be figured out. The hard part would be determing the state of the cubies you want to move and matching them to the right set of moves. Very doable.

I hope this helps. Let me know if I can clarify.

-Kirk

Well, the point is you'll get a solution. And the way the GA is set up, you'll get a solution that is only 40 moves (based on my example formulation). Of course you'll go through multiple generations, that's definite for hard problems. but think of it this way, with 12^20 nodes, in the worst case, A* will search them all. With a GA of population size 100 and running 1000 iterations to find the solution, that would mean checking only 100,000 nodes. Even if we say A* got lucky and the problem really isn't that crazy, it would have to find a solution by searching through less than 12^5 nodes or less to come close to what you can do with a GA.

In implementations like this, you'll always get redundant moves, which you can always prune out during some solution preprocessing, or just leave in. Theoretically, it wouldn't matter, but I'd have to actually implement it to know.

I updated my Rubik.rar (in my previous post), so now it solves the ENTIRE cube. (perhaps still some small hickups, there are still a few bugs in it).

To comment on how I solved it: I made a special class Astar with a static function SolveTo(Condition condition, Node start).

Condition is an abstract class with a function (bool MeetsCondition(Node node)), and I write custom conditions for each fase of the solving process
so:

-Solving white cross ==> SolveTo(new WhiteCrossSolved(), new WhiteCrossNode());
In this WhiteCrossNode is a node with the default neighbours(just the twelve possible moves) and a specific heuristic for the white cross..

Then for all the other steps (solving white layer, solve second layer, ..., solve cube), I wrote custom Conditions and and custom nodes, which had their own heuristic, and an overridden SetupNeighBours() function with nodes that you become after a specific MoveSequence.

I still have to add more MoveSequences to my code, since the first layer is solved really inefficiently. My goal is to get below 100 Moves (and ideally below 60 or so).