Colored cubes isomorphism

Question

Consider two cubes with an arbitrary coloring of faces from 5 possible colors, where each color could appear $0$ to $6$ times. What could be an efficient algorithm for testing whether the two cubes are isomorphic?

Answer 1

A good general strategy for isomorphism testing of various structures is to figure out a canonical representation of each structure, such that two structures are isomorphic if and only if their canonical representations are equal. A basic idea behind a canonical representation is that whenever the order of several things does not matter, sort them. In many cases (such as for graph isomorphism) things get more complicated, but here we do not have to try very hard.

---

If you allow reflections, then two colorings are isomorphic if and only if they have the same three pairs of opposite face colors. That is, given the cube net

     +----+
     |    |
     | C1 |
     |    |
+----+----+----+----+
|    |    |    |    |
| C2 | C3 | C4 | C5 |
|    |    |    |    |
+----+----+----+----+
     |    |
     | C6 |
     |    |
     +----+

with colors $C_1, C_2, C_3, C_4, C_5, C_6$ on the faces, the isomorphism class is determined by the multiset of multisets $$\Big[ [C_1, C_6], [C_2, C_4], [C_3, C_5] \Big]$$ where the order within a pair, as well as the order of the three pairs, does not matter - but multiplicity does.

Sort each pair, then sort the multiset of three pairs, to determine a canonical representation of the coloring. For example, given $(C_1, C_2, C_3, C_4, C_5, C_6) = (1,2,3,3,1,2)$ our three sorted pairs are $[1,2]$, $[2,3]$, and $[1,3]$, which we sort to get the canonical representation $$\Big[[1,2], [1,3], [2,3]\Big].$$ Two colorings are isomorphic if their canonical representations are equal.

---

If we do not allow reflections, then there is an extra detail to keep track of. Swapping the two colors in a pair, as well as swapping the order of two pairs, is a reflection - but as long as we do an even number of reflections, then that's fine. One way to address this is the following:

1. Sort the multiset of multiset pairs as usual - but keep track of whether the number of swaps done is even or odd. In the above, the unsorted multiset is $\Big[ [C_1, C_6], [C_2, C_4], [C_3, C_5] \Big] = \Big[[1,2], [2,3], [3,1]\Big].$ We sort the last pair with one swap, and then there is another swap to switch the order of $[2,3]$ and $[1,3]$. So we record the result $\Big[[1,2], [1,3], [2,3]\Big]$ together with the detail that an even number of swaps are required.
2. As a special case, whenever a pair $[C_i, C_j]$ has $C_i = C_j$, or whenever two pairs are the same, the cube is symmetric: there is a reflection that leaves the coloring unchanged. In such a case, instead of recording that the number of swaps is even or odd, record "symmetric".

Now, two colorings are isomorphic iff their canonical representations are equal, and either both needed an even number of swaps, or both needed an odd number, or both are symmetric.