卡拼图的算法解决方案
鉴于是一个九方卡的益智游戏。
在每张卡片的顶部，右侧，底部和左侧有4张照片。
卡片上的每张照片都描绘了动物（鳄鱼）的前部或后部。 每张照片都有5种颜色之一。
目标：将9张牌以3x3网格布局，使所有“内”（完整）鳄鱼与相邻牌适当结合，即具有前端和后端以及匹配的颜色。
为了更好地理解这个问题，下面是一个难题的图片：
我手工找到了所描述的解决方案。
尽管乍看起来谜题看起来很简单，但考虑到您可以通过4种不同的方式旋转每一部分，组合的数量非常多。
现在的问题是，我想要一个算法生成所有可能的3x3布局，以检查所有可能的解决方案（如果有其他解决方案）。 最好在Processing / Java中。
思念至今：
我的方法是用一个由4个整数组成的数组表示9个片段中的每一个，表示一个片段的4个旋转状态。 然后生成这9个片段的所有可能的排列，从片段数组中选取4个旋转状态中的一个。 函数isValidSolution()然后可以检查违反约束（颜色匹配和前后匹配）的解决方案。
关于如何实现这个的任何想法？
可以找到所有的解决方案，试图不去探索搜索树的所有不成功的路径。 下面的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 solutionsn", solutionsCounter);
return 0;
}
只有9件，因此每个可能的解决方案都可以用一个小的结构来表示（比如说一个3x3的碎片，每个碎片都有它的旋转），所以碎片的确切描述并不重要。
尝试所有可能的排列方式都是浪费的（在这里滥用LaTeX，将9件放在网格上可以用9美元的订单完成，因为每个订单可以有4种不同的方向，总共9美元！ cdot 4 ^ 9 = 95126814720 大约10 ^ {11} $，有点太多检查他们都）。 你要做的就是放置一块，比如在左上方，然后尝试通过将匹配块装入其余块来完成该方块。 所以你永远不会考虑第一和第二部分不匹配的任何组合，从而大大减少搜索量。 这种想法被称为回溯。 为此，您需要描述部分解决方案（3x3网格包含已填充的部分和空白部分，尚未使用的部分;填充网格的特定顺序），向前移动的方式（放置下一部分如果不合适，则跳过那一个），然后向后（找不到任何拟合，撤消上一步并尝试下一个可能性）。
显然，你必须设计一种方法来确定是否存在潜在的匹配（给定填充的邻居，尝试所有方向的一个片段在它的签名的地方）。 对于这样一个小问题，这可能不是性能的关键，但如果你试图解决，比如100x100，情况就不同了。
链接地址: http://www.djcxy.com/p/40199.html上一篇: Algorithmic solution of card puzzle
下一篇: How can I find the highest poker hand from a 9 card hand between 4 players?