Cube 3x3: Using just face rotations, transform the cube from configuration A to B

Question

I'm looking for some tips on how to best implement the algorithm to accomplish the following:

• Imagine a 3×3 cube with a rubik's cube mechanism, i.e. you can freely rotate any of the 6 faces.
• You don't care about colors.
• Instead you index the component 26 cubes A–Z and ignore the middle.

Illustration image (component cubes): https://paste.pics/AOYUS

Now, I would like to generate a list of face rotations that would get me from this configuration to some other configuration. E. g. this: https://paste.pics/AOYWM

Note: I don't care which component cubes end up in positions labeled as *

Ideally the algorithm produces the shortest list of transformations necessary, but it's not a firm condition. Any suggestions welcome, thanks!

Answer 1

If the number of "don't care" colours is large, as it is in this example, you probably can't do much better than A* search.

One simple heuristic function is the minimum number of moves required to move the currently-least-correct piece to its correct position. Since you're willing to tolerate some non-optimality, summing over all pieces that are not in their correct locations will probably do quite well in practice.

Answer 2

Answering this will be similar in difficulty to answering question's about Rubik's cube. The only difference is that in Rubik's cube some stones can come in two or three different orientations, which you want to ignore.

Optimal solution will be slightly shorter on average than optimal solution for Rubik's cube. Finding an optimal solution will be slightly easier than finding the optional solution for Rubik's cube, since there are probably no clever tricks that would allow you to find the optimal solution for Rubik's cube faster.