Algorithmic puzzle map solution

Question

This is a nine square card puzzle game.
On each of the cards there are 4 photos on top, right, bottom and left.
Each image on the map depicts either the front of the animal or the rear of the animal (crocodile). Each image has one of 5 colors.

Purpose: lay out nine cards in a 3x3 grid so that all the "internal" (full) crocodiles are properly combined with neighboring cards, that is, they have a front and back end, as well as the corresponding colors.

To get visual control of the problem, here is a puzzle image:

.
, , , , .

, , 3x3, ( ). /Java.

:
, 9 4 , 4 . 9 , 1 4 . isValidSolution() ( ).

, ?

Answer 1

, . ++-, , 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;
}

Answer 2

9 , (, 3 × 3 , ), .

( LaTeX , 9 , $9! $order, 4 , $9!\cdot 4 ^ 9 = 95126814720\approx 10 ^ {11} $, , ). , , - , , , , . , , . . ( 3x3 , , , ), ( , , ) ( , ).

, , ( , ). , , , , , 100x100, ...