c++ - 在 c++ 中执行此操作的任何更好方法，计算拼图的解决方案(49!结果，49 个循环)

Question

这个拼图基本上有 49 block 拼图。它们每条边上都有 4 种颜色。我需要创建一个 7x7 拼图，其中一个图 block 的每个边缘都与与其相邻的图 block 边缘的颜色相匹配，例如 2x2 解决方案:

       blue             purple
yellow     green  green       pink
       pink              blue

       pink              blue
purple     yellow yellow     green
       blue              pink

我打算为每种颜色分配数字，然后执行类似(伪代码)的操作:

for i in 1 to 49
    for j in 1 to 48
       if left colour of j == right colour of i
           join them
       for k in 1 to 47
           if left colour of k == right colour of j
.....
......

如果所有49个都分配完毕

我什至不知道这么多次迭代是否可行，有什么建议吗？谢谢。

4个方 block 的示例图片(真正的拼图是49个方 block )http://i.stack.imgur.com/6ISpQ.png

仅当您真的想要真正的谜题时才阅读:

实际的拼图叫做“魔方拼图”

http://i.stack.imgur.com/K0MBl.jpg

我打算为甲虫的每一半分配一个小数，这样当它们加在一起时 == 1。然后我会像上面那样迭代并检查它们是否在添加时 == 1。

Answer 1

我想你需要的是Depth-first search algorithm .

每个方 block 的颜色可以用 enum 表示:

enum class TileColor {
    Blue,
    Purple,
    Yellow,
    Green,
    // ...
};

然后您可以用一个类来表示每个图 block :

struct Tile {
    TileColor up;
    TileColor down;
    TileColor left;
    TileColor right;
};

然后在主进程中，你可以像这样初始化一个 7*7 的拼图板:

int main() {
    // To define a 7*7 board, vector is recommended.
    std::vector<std::vector<Tile> > board(7, std::vector<Tile>(7));

    // You can loop the vector in a traditional way like:
    for (auto row = 0; row < board.size(); ++row) {
        for (auto col = 0; col < board[row].size(); ++col) {
            // Some code here.

            // To assign a value to a tile, the code looks like:
            // board[row][col].left = TileColor::Blue;

            // To test color is match, the code looks like:
            // if (board[row][col].right == (board[row][col + 1].left) { ... }
            // The boundary condition is also needed to be considered here.
        }
    }

    // To loop in a more "C++" way, you could use iterator:
    for (auto row = board.begin(); row != board.end(); ++row) {
        for (auto col = row->begin(); col != row->end(); ++col) {
            // Some code here.

            // To assign a value to a tile, the code looks like:
            // col->left = TileColor::Blue;

            // To test color is match, the code looks like:
            // if (col->right == (col + 1)->left) { ... }
            // The boundary condition is also needed to be considered here.
        }
    }
    return 0;
}

不过，以上只是对问题的基本数据类型的简单说明，对于解决问题的算法，DFS会是一个合适的算法。更具体地说，您可能想要使用 vector<Tile> tiles(7*7);存储从输入文件或控制台读取的所有图 block ，然后在循环中尝试从 tiles 中选取一个图 block 并将其放在 board 上，然后检查它是否与其他人匹配。如果匹配，则循环继续拾取下一个图 block 。如果不匹配，您可以通过从棋盘上拿走棋子并将其放回 tiles 来返回之前的状态。 .如果你所有的牌都放在棋盘上，那么解决方案就出来了。

另一个提示是您可能想要使用 9*9问题板 7*7其中为您添加了另外两行和两列，就像董事会的寄宿生一样。