c++ - Rubik's Cube Scramble 生成器算法

Question

我最近一直在从事一个项目，其中包括 Rubik's Cube scramble 生成器。基本上，该程序应该生成并显示随机的立方体符号，以便用户可以跟随每一步移动并获得一个相当困惑的立方体。符号包括“R”代表右转层，“L”代表转左层，“F”代表转前层，“D”代表下，“U”代表上，“B”代表后。因此，您总共有 6 个边“R、L、U、D、F、B”。任何这些符号后的撇号表示逆时针移动该层，“2”表示将该层移动两次。问题是你不能让相同的符号像“R，R”一样彼此相邻重复，因为它与“R2”相同，你也不能让“R，R'”彼此相邻，因为它们会互相抵消。我的解决方案是制作一个二维数组来存储每种类型的 3 组符号。

string notation_group[row][column] = { { "R ", "L ", "F ", "B ", "U ", "D " },
    {"R' ", "L' ", "F' ", "B' ", "U' ", "D' "}, { "R2", "L2", "F2", "B2", "U2", "D2"} };

这意味着每当程序从这些组中的任何一个中选择一个随机列时，程序必须防止下一个生成的符号选择任何其他组中的相同列。所以假设如果程序选择第一组“R”的第一个元素，那么在下一次迭代中它可以选择除“R”、“R'”和“R2”之外的任何符号，所有这些都属于第一列他们各自的团体。因此，程序所要做的就是在下一次迭代期间不选择该列。

我使用了一个“临时”变量来记住当前随机生成的符号并将其与下一个进行比较，并在它们相等时生成一个新符号。

int temp;

            scrambled_notation[i] = notation_group[pickGroup][pickColumn];

            temp = pickColumn;

            pickColumn = 0 + rand() % 6;

            while (temp == pickColumn) {
                pickColumn = 0 + rand() % 6;
            }

它确实有效，但还有另一个问题，每当你有像“R，L”或“R，L'，R”这样的东西彼此相邻重复多次时，它们会再次相互抵消而不会产生任何影响在立方体上。有什么想法可以防止两个对立面彼此相邻重复多次吗？我将不胜感激帮助。

    void initScramble(const int, string[][6], string[]);

int main() {

    srand(time(0));

    const int row = 3, column = 6;
    string notation_group[row][column] = { { "R", "L", "F", "B", "U", "D" },
    {"R'", "L'", "F'", "B'", "U'", "D'"}, { "R2", "L2", "F2", "B2", "U2", "D2"} };

    const int scrambleSize = 22;
    string scrambled_notation[scrambleSize];

    cout << "SCRAMBLE: " << endl;

    initScramble(scrambleSize, notation_group, scrambled_notation);

    system("pause");
    return 0;
}

void initScramble(const int scrambleSize, string notation_group[][6], string scrambled_notation[]) {

    int pickColumn = 0 + rand() % 6;

    while (true) {

        cin.get();

        for (int i = 0; i < scrambleSize; i++) {

            int pickGroup = 0 + rand() % 3;

            int temp;

            scrambled_notation[i] = notation_group[pickGroup][pickColumn];

            temp = pickColumn;

            pickColumn = 0 + rand() % 6;

            while (temp == pickColumn) {
                pickColumn = 0 + rand() % 6;
            }
        }

        for (int i = 0; i < scrambleSize; i++) {
            cout << scrambled_notation[i] << "  ";
        }
        cin.get();
        system("CLS");
    }

}

Answer 1

只要最后两步是可交换的，您就必须寻找它们。如果没有，那么您只检查最后一步。每对列都是可交换的这一事实简化了这一点:

void initScramble(const int scrambleSize, string notation_group[][6], string scrambled_notation[]) {
    while (true) {
        int lastColumn = 7; // Invalid columns
        int beforeLastColumn = 7;

        cin.get();

        for (int i = 0; i < scrambleSize; i++) {
            int pickGroup = 0 + rand() % 3;
            int pickColumn = 0 + rand() % 6;
            bool isCommutative = (lastColumn / 2) == (beforeLastColumn / 2);

            while (pickColumn == lastColumn || isCommutative && pickColumn == beforeLastColumn) {
                pickColumn = 0 + rand() % 6;
            }

            scrambled_notation[i] = notation_group[pickGroup][pickColumn];
            beforeLastColumn = lastColumn;
            lastColumn = pickColumn;
        }

        for (int i = 0; i < scrambleSize; i++) {
            cout << scrambled_notation[i] << "  ";
        }
        cin.get();
        system("CLS");
    }
}

您不必看得更远，因为按照您的打乱规则，您只能有 2 个可交换的连续 Action 。例如，'L,R,L' 和 'L,R,R' 将被丢弃，因此永远不会生成 3 个交换移动。