Cube 3x3: Using just face rotations, transform the cube from configuration A to B
If the number of &quot;don't care&quot; 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.