Как вычислить все ориентации куба, вращая, не повторяя ориентации? - PullRequest
Новая
       41

Как вычислить все ориентации куба, вращая, не повторяя ориентации?

0 голосов
/ 02 февраля 2019

Я работаю над приложением, чтобы найти число возможных решений куба головоломки с заданной исходной структурой.

У меня есть все уникальные решения, хранящиеся в памяти, которые я буду сравниватьзаданная структура, чтобы определить, сколько решений возможно.

Чтобы сделать это, я должен повернуть куб на 90 градусов, 4 раза, вокруг каждой грани, чтобы проверить все возможные ориентации.Я рассмотрю отражения позже.

В кубе есть 6 граней с 4 поворотами, что дает в общей сложности 24 операции.

Я изо всех сил пытаюсь реализовать эффективный алгоритм из-затот факт, что вращение вокруг одной оси эквивалентно вращению вокруг другой оси 2.

Например: вращение вокруг оси x дает ту же ориентацию, что и вращение вокруг оси y, а затем оси z.Поэтому моей текущей реализации потребовалось 64 операции, что является избыточным, так как я проверяю одну и ту же ориентацию несколько раз.

Изображение приложения

Текущий алгоритм: 

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;
}

Как я могу улучшить это, чтобы я не повторял одну и ту же ориентацию, т.е. чтобы я мог проверить только 24 итерации, а не 64.

1 Ответ

0 голосов
/ 02 февраля 2019

Каждое из 24 вращений может быть однозначно идентифицировано по тому, какая грань направлена ​​вверх (6 вариантов), а какая направлена ​​влево (4 варианта для каждой восходящей грани).

Внешний цикл для определения восходящей грани, за которой следуетпо внутренней петле определить левую грань кажется достаточно просто.Учитывая аргументы, которые принимает ваш вызов rotate, я, вероятно, сделал бы это так: 

// 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;
}

Надеюсь, вы увидите, как он должен работать.Я сделал предположение о том, в какую сторону указывают ваши оси и как вращаются объекты, поэтому, если ROTATION_PATH не выполняет то, что должно для вас, отрегулируйте его соответствующим образом.

...