算法解决纸牌难题

Question

给出了一个由九个方格卡片组成的拼图游戏。
每张卡片上都有4个图片，分别位于顶部、右侧、底部和左侧。
每个卡片上的图片描绘了动物（鳄鱼）的前部或后部。每个图片都有5种颜色之一。

目标：将这九张卡片以3x3网格的方式铺开，使得所有“内部”（完整的）鳄鱼与相邻卡片正确结合，即具有前端和后端以及匹配的颜色。

为了更好地理解问题，以下是谜题的图片： 我通过手工方法找到了上述的解决方案。尽管这个谜题乍一看很简单，但是由于每个图案可以旋转4次，所以可能的组合非常多。

现在的问题是我想要一个算法来生成所有可能的3x3布局，以便检查所有可能的解决方案（如果有其他解决方案）。最好用Processing/Java实现。

思路如下： 我的方法是用一个由4个整数数字组成的数组表示每个九块拼图的四个旋转状态。然后生成这9个拼图的所有可能排列，并从拼图数组中选择1个4个旋转状态之一。函数isValidSolution()可以检查一个解决方案是否违反约束条件（颜色匹配和前后匹配）。

你有实现这个思路的想法吗？

- Martin

Answer 1

可以找到所有的解决方案，而无需探索搜索树中所有不成功的路径。下面是C++代码，虽然不高度优化，但几乎瞬间在我的电脑上找到了2个解决方案（结果是相同的唯一解决方案，因为有一个重复的拼图块，正确吗？）。

这里避免探索所有可能性的技巧是在我们放置拼图块时调用函数isValidSolution()（该函数处理空拼图块）。此外，为了加速进程，我按照给定顺序放置拼图块，从中间开始，然后在左侧、右侧、顶部和底部形成交叉点，然后是左上角、右上角、左下角和右下角的角落。 可能其他组合可以更快地执行。

当然，由于这个难题中的特殊模式分布（只接受一个可能的匹配的字母模式），可以进行优化，但这超出了我的回答范围。

#include<iostream>

// possible pattern pairs (head, body)
#define PINK    1
#define YELLOW  2
#define BLUE    3
#define GREEN   4
#define LACOSTE 5

typedef int8_t pattern_t; // a pattern is a possible color, positive for head, and negative for body
typedef struct {
    pattern_t p[4]; // four patterns per piece: top, right, bottom, left
} piece_t;

unsigned long long int solutionsCounter = 0;

piece_t emptyPiece = {.p = {0,  0,  0, 0} };

piece_t board[3][3] = {
    { emptyPiece, emptyPiece, emptyPiece},
    { emptyPiece, emptyPiece, emptyPiece},
    { emptyPiece, emptyPiece, emptyPiece},
    };

inline bool isEmpty(const piece_t& piece) {
    bool result = (piece.p[0] == 0);
    return result;
}

// check current solution
bool isValidSolution() {
    int i, j;
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 3; j++) {
            if (!isEmpty(board[i][j]) && !isEmpty(board[i+1][j]) && (board[i][j].p[1] != -board[i+1][j].p[3])) {
                return false;
            }
        }
    }
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 2; j++) {
            if (!isEmpty(board[i][j]) && !isEmpty(board[i][j+1]) && (board[i][j].p[2] != -board[i][j+1].p[0])) {
                return false;
            }
        }
    }
    return true;
}

// rotate piece
void rotatePiece(piece_t& piece) {
    pattern_t paux = piece.p[0];
    piece.p[0] = piece.p[1];
    piece.p[1] = piece.p[2];
    piece.p[2] = piece.p[3];
    piece.p[3] = paux;
}

void printSolution() {
    printf("Solution:\n");
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("\t  %2i  ", (int) board[j][i].p[0]);
        }
        printf("\n");
        for (int j = 0; j < 3; j++) {
            printf("\t%2i  %2i", (int) board[j][i].p[3], (int) board[j][i].p[1]);
        }
        printf("\n");
        for (int j = 0; j < 3; j++) {
            printf("\t  %2i  ", (int) board[j][i].p[2]);
        }
        printf("\n");
    }
    printf("\n");
}

bool usedPiece[9] = { false, false, false, false, false, false, false, false, false };
int colocationOrder[9] = { 4, 3, 5, 1, 7, 0, 2, 6, 8 };

void putNextPiece(piece_t pieces[9], int pieceNumber) {

    if (pieceNumber == 9) {
        if (isValidSolution()) {
            solutionsCounter++;
            printSolution();
        }
    } else {
        int nextPosition = colocationOrder[pieceNumber];
        int maxRotations = (pieceNumber == 0) ? 1 : 4; // avoids rotation symmetries.
        for (int pieceIndex = 0; pieceIndex < 9; pieceIndex++) {
            if (!usedPiece[pieceIndex]) {
                usedPiece[pieceIndex] = true;
                for (int rotationIndex = 0; rotationIndex < maxRotations; rotationIndex++) {
                    ((piece_t*) board)[nextPosition] = pieces[pieceIndex];
                    if (isValidSolution()) {
                        putNextPiece(pieces, pieceNumber + 1);
                    }
                    rotatePiece(pieces[pieceIndex]);
                }
                usedPiece[pieceIndex] = false;
                ((piece_t*) board)[nextPosition] = emptyPiece;
            }
        }
    }
}

int main() {

    // register all the pieces (already solved, scramble!)
    piece_t pieces[9] = {
        {.p = { -YELLOW,    -BLUE,     +GREEN,  +PINK} },
        {.p = { -YELLOW,    -GREEN,    +PINK,   +BLUE} },
        {.p = { -BLUE,      -YELLOW,   +PINK,   +GREEN }},
        {.p = { -GREEN,     -BLUE,     +PINK,   +YELLOW }},
        {.p = { -PINK,      -LACOSTE,  +GREEN,  +BLUE }},
        {.p = { -PINK,      -BLUE,     +GREEN,  +LACOSTE }},
        {.p = { -PINK,      -BLUE,     +PINK,   +YELLOW }},
        {.p = { -GREEN,     -YELLOW,   +GREEN,  +BLUE }},
        {.p = { -GREEN,     -BLUE,     +PINK,   +YELLOW }}
    };

    putNextPiece(pieces, 0);

    printf("found %llu solutions\n", solutionsCounter);

    return 0;
}

- Iban Cereijo

---

可以使用数组 int availabilityPerPiece[] 而不是 bool usedPiece[] 来处理重复的瓦片，并找到唯一的解决方案。 - Iban Cereijo

谢谢！计算解决方案只需一点时间。我真的以为要花很长时间才能遍历所有95亿个组合。而且我没有意识到有一个重复的瓦片...你发现得真好！ - Martin

你好，能否请您告诉我如何进一步优化这个解决方案？ - Jatin

Answer 2

只有9块拼图，因此每个潜在解决方案都可以用一个小结构来表示（比如一个3x3的拼图数组，每个拼图带有它的旋转），因此拼图的确切描述并不太重要。

尝试所有可能的排列是浪费的（滥用LaTeX，将9个拼图放在网格上可以有$9!$种方法，因为每个拼图可以有4种不同的方向，这总共给出了$9! \cdot 4^9 = 95126814720 \approx 10^{11}$种可能性，检查所有这些显然太多了）。你手动完成的方式是先放置一块拼图，比如在左上角，然后尝试通过将匹配的拼图拟合到其余位置来完成整个正方形。因此，你永远不会考虑任何第一和第二块拼图不匹配的组合，从而大大缩减了搜索范围。这种思想被称为回溯。为此，您需要描述部分解决方案（填充拼图和空白位置的3x3网格以及尚未使用的拼图；特定的顺序来填充网格），一种前进的方法（如果适合，则放置下一个拼图；如果不适合，则跳过该拼图），以及后退的方法（无法找到任何适合的情况下，撤销上一个移动并尝试下一个可能性）。

显然，您需要设计一种方法来查找潜在匹配项（给定填充的邻居，尝试将方块在其指定位置的所有方向）。对于如此小的问题，这可能不是性能关键，但如果您尝试解决例如100x100的情况，则情况就不同了...

- vonbrand

---

正确的可能性数量为：9！*4^9 = 95126814720。 - Jakube

不考虑旋转对称性（这相当于避免旋转第一块瓷砖），可能性的数量减少到9！*4^8 = 23781703680。 - Iban Cereijo