Solving Rubik's cube programmatically

Question

I am trying to develop a program for solving a Rubik's cube in C. I used back tracking technique for this. It is a very long process and it takes lot of iterations, so I'm not able to solve it.

Please give me suggestions on how to solve this more efficiently - such as other techniques or adopting backtracking itself. In Google I found a lot of shortcuts for solving this but I don't want to solve this by using shortcuts.

Answer 1

Why not use a human oriented solution and program this.

You need some pattern matching, but it won't be that hard. (Besides there are programs solving the 1000x1000x1000).

The basic idea is to work in phases:

• First layer
• Second layer
• Third layer

For each layer you implement a couple of algorithms that turn pattern X into pattern X'. Each step in a phase should bring the cube close to solving. You can do this by adding a value to each pattern (where higher values are given to more unsolved cubes). You can also add a difficulty (for example the number of turns) so you can select an algorithm based on the best value gain per difficulty (or reach the best result with the least turns).

The fun of this approach, is that you can add new algorithms if you like and test how often they are used. So you can test the usefulness of each algorithm.

If you really want to earn those geekpoints, create a separate language to describe the algorithms and the pattern they are solving.

Answer 2

there are many algorithms to solve the rubik problem, however, you can refer to this optimal one http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

Answer 3

I'm not sure I understand your problem and what you mean by shortcuts. If you are using some dynamic programming method for solving the rubik's cube you need to make sure you are looking at enough steps ahead in order to reach a solution. I believe that if you only support 2 types of moves (rotate right, rotate up) you need to look 12 steps (not sure) ahead before deciding on each move in order to ensure a solution.

If you are doing something like this and you found that you have run out of space in memory then keep in mind that you only need to retain the path you are traversing in order to decide on the right solution (not the entire tree).

I used this approach successfully for solving a rubik's cube in Java so C should have no problems (as far as memory footprint).

Answer 4

Rubik's cube has state space size in the order of 2⁶⁵. A backtracking algorithm that searches the state space blindly may need to examine a large portion of the state space before it finds the solution, so clearly a simple backtracking algorithm is not going to work very well. But then, this problem is already solved many times. See e.g. http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf