How to compute all orientations of a cube by rotating, without repeating orientations?

Question

I am working on an application to to find the number of possible solutions to a puzzle cube given a particular starting structure.

I have all of the unique solutions stored in memory, which I will be comparing the given structure against in order to determine how many solutions are possible.

In order to do this, I must rotate the cube 90 degrees, 4 times, about each face so that I check for all possible orientations. I will be considering reflections later on.

With a cube, there are 6 faces with 4 rotations giving a total of 24 operations.

I'm struggling to implement an efficient algorithm due to the fact that a rotation about one axis is equivalent to a rotation about the other 2 axis'.

For example: a rotation about the x axis yields the same orientation as rotating about the y axis and then the z axis. As such my current implementation required 64 operations which is redundant as I am checking the same orientation multiple times.

Image of application

Current algorithm:

public static int getPossibleSolutionCount(Map<PieceIndex, Piece> pieces)
{
    int count = 0;
    for (Solution s : solutions)
    {
        for (int z = 0; z < 4; z++)
        {
            for (int x = 0; x < 4; x++)
            {
                for (int y = 0; y < 4; y++)
                {
                    if (s.isDerrivedFrom(pieces))
                    {
                        count++;
                    }
                    //all rotation calls rotate the piece / structure byt 90 degrees
                    pieces.values().forEach(piece -> piece.rotate(GameObject.Axis.Y_AXIS));
                }
                pieces.values().forEach(piece -> piece.rotate(GameObject.Axis.X_AXIS));
            }
            pieces.values().forEach(piece -> piece.rotate(GameObject.Axis.Z_AXIS));
        }
    }
    return count;
}

How can I improve this so that I am not repeating the same orientation, ie so that I can check in only 24 iterations rather than 64.

Answer 1

Each of the 24 rotations can be uniquely identified by which face faces up (6 possibilities), and which faces left (4 possibilities for each upward face).

An outer loop to determine the upward face followed by an inner loop to determine the leftward face seems easy enough. Given the arguments that your rotate call takes, I would probably do it like this:

// Rotating around these axes in sequence will bring each face in turn
// to the top
private static GameObject.AXIS ROTATION_PATH = new GameObject.AXIS[] {
    GameObject.AXIS.X_AXIS,
    GameObject.AXIS.X_AXIS,
    GameObject.AXIS.Z_AXIS,
    GameObject.AXIS.X_AXIS,
    GameObject.AXIS.X_AXIS,
    GameObject.AXIS.Z_AXIS
};

public static int getPossibleSolutionCount(Map<PieceIndex, Piece> pieces)
{
    int count = 0;
    for (GameObject.AXIS path_axis: ROTATION_PATH)
    {
        for (int y = 0; y < 4; y++)
        {
            for (Solution s : solutions)
            {
               if (s.isDerivedFrom(pieces))
               {
                   count++;
               }
            }
            pieces.values().forEach(piece -> piece.rotate(GameObject.Axis.Y_AXIS));
        }
        pieces.values().forEach(piece -> piece.rotate(path_axis));
    }
    return count;
}

Hopefully you see how it's supposed to work. I made assumptions about which way your axes point and which way things rotate, so if ROTATION_PATH doesn't do what it's supposed to for you, then adjust it accordingly.