How can I generate Rubik's cube algorithms equivalent to a given algorithm?

Question

I am developing a computer program that solves the Rubik's cube. It is not anything advanced nor fast. It solves the cube by the Friedrich method, using algorithms that I use in real life to solve the cube. Because of that, the output solving algorithm is quite a long one and I was wondering is there is a way to transform the output to an equivalent algorithm, but shorter. This might actually be impossible, but I think this is a question worth asking. For example here is a list of equivalent algorithms that orient the corners of the last layer of that cube state shown in the image.

L.E.: Friedrich splits the solve in 4 steps(cross, inserting corners and their corresponding edges(F2L), orienting the last layer(OLL) and permuting the last layer(PLL)). So far my program only solves the cross, and I am now beginning to code the algorithms for the second step(F2L). All the algorithms I find online for F2L, OLL and PLL are designed to be remembered and/or executed as easily and naturally as possible, so they are not necessarily the shortest ones. Using Kociemba's program I can find shorter algorithms equivalent to those used by humans only for PLL, where the entire cube stays the same except for the edges and corners of the last layer. This is because Kociemba only gives the algorithms that leads to complete solve of the cube(and only for PLL we need this solution). For F2L for example I don't know what configurations I should put the cube in in order to output the algorithm that only inserts the desired pair(corner and edge) in the correct place and doesn't care about the cubies in the last layer, or the cubies in the other corners(that are not solved yet). I hope that makes sense. I make this program for a project for my Algorithms course, first year in CS and the requirements are that it must solve any given state of the 3x3x3 cube and output the shortest solution. I know group theory can be used, but it is much more complex and requires more time than I was given to finish the project, so I thought that Friedrich would be easier to achieve.

So far my outputs an algorithm for solving the cross that averages at 10 moves with a maximum of 19 in half turn metric. The execution time varies from 0.02 to 0.03 seconds per cube. This data was obtained from running the program on 1500 randomly generated cube states.

Answer 1

Solutions

Finding solutions of a Rubik's cube is infeasible by enumeration (BFS - too much space required), DFS takes too much time and does not guarantee the optimal solution, I highly doubt that optimal solution would be required.

There are at least three algorithms worth noting: Kociemba's algorithm, Thistlewaite's algorithm and Iterative deepening $A^*$ (Korf's). Here is a methods comparison. Iterative deepening needs admissible heuristic, which for Rubik's cube is the sum of 3D Manhattan distances calculated separately for corners and cubies. Due to Korf, it also needs pattern database to achieve optimal solution in reasonable time.

Algorithm Optimization

For optimizing any given algorithm all above will work in reasonable time, including BFS for short algorithms. To make small number of turns in overall solution the structured system should yield low number of turns in average, Friedrich method is mainly used for manual solving with medium number of algorithms (more than 100 is huge number to learn at once, not that challenging to program), so instead of optimizing single steps it would be better to find system that scores better. For example ZBLL method with 493 algorithms (including mirrors) with average about 40 turns, Friedrich scores about 56.

Solving Between States

This step is inevitable: the modification of the stop condition in the search tree - at some point while processing partial algorithm the stop condition should be changed to check only target pieces and already solved ones. There is no good way to mitigate this effect, at initial phases enumerating all possible permutations of the cube is too memory and time consuming. Searching for shorter algorithm without changed condition (via ready to use solver or own algorithm) will yield very long solution, because all pieces will be preserved e.g. the last layer while solving the middle layer. To really improve the overall score instead of shortening given moves it is far more valuable to implement look ahead (e.g. better last layer orientation while solving the second one, or increasing number of algorithms possibly merging phases together).

There is also Hamilton circuit for Rubik's cube with included graph for cosets - this is not a full solution, but still worth reading.

Answer 2

I'm aware that you said that you don't want to use group theory in your algorithm, but here's one option that can act as a postprocessing step, i.e. you can apply it to your output sequence without having to modify your algorithm:

Given a group presentation for the moves on the Rubix cube (i.e. a collection of elementary moves and the equations that hold between them), then you can use the utilities provided with the automatic groups software MAF to convert any sequence of moves into its unique minimal equivalent.

MAF even has an examples directory entitled rubik, which AFAIK might contain the move descriptions you need.

Don't be too discouraged by the apparent complexity of automatic groups. In outline, what you need to do is:

1. Find a group presentation corresponding to your elementary moves.
2. Use the MAF utilities to obtain a confluent rewriting system for your group.
3. Use this rewriting system to reduce your lengthy move sequence.

Answer 3

There are many ways to achieve the 3x3x3 solution other than just an alg list and pre-search databases. While Korf, Kociemba, et al have worked on the 3x3x3, our discussion board group has a 5x5x5 author whose software can solve a randomly scrambled 5x5x5 cube in 5 seconds or less and solve cubes of any size. We have another author whose solver produces solutions to random 5x5x5 scrambles in the 70-75 move range. And a third program can bruce force search into the quintillions of nodes using 100 GB+ hash tables for the 5x5x5. Many of the algorithms and techniques are discussed, with screen shots and example solves linked to a 3D cube replay. Visit http://cubesolvingprograms.freeforums.net/ for more information.