/******  Backtracking dominos ******/

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* Domino */
struct domino_s {
    int x; // valeur de gauche
    int y; // valeur de droite
};

typedef struct domino_s Domino;

/* Maillon */
struct element_s {
    Domino d;
    struct element_s* suiv;
};

typedef struct element_s element;

/* Chaine */
typedef element* chaine;


/**** Partie 1 ****/

/* Affiche les dominos d'une liste */
void afficheDominos(element* L){
    element* l = L;
    while (l != NULL) {
        printf("(%d,%d)-", l->d.x, l->d.y);
        l = l->suiv;
    }
    printf("\n");
}

/* Alloue un maillon dans le tas, et l'ajoute en tête de liste */
element* ajouteTete(element* L, Domino d){
    element* elt = (element*) malloc(sizeof(element));
    elt->d = d; elt->suiv = L;
    return elt;
}

/* Obtenir le domino de tête de liste (sans modifier la liste) */
Domino tete(element* L){
    assert(L != NULL);
    return L->d;
}

/* Retire la tête de liste (et rend le maillon au tas) */
element* retireTete(element* L){
    assert(L != NULL);
    element* a_renvoyer = L->suiv;
    free(L);
    return a_renvoyer;
}

/* Destruction de liste - version récursive -*/
void detruireListe(element* L){
    if (L != NULL) {
        element* suiv = L->suiv;
        free(L);
        detruireListe(suiv);
    }
}

/**** Partie 2 ****/

bool possible(Domino di, Domino dj){
    return di.y == dj.x;
}

bool possibleAvecRotation(Domino di, Domino dj){
    return di.x == dj.x;
}

Domino rotation(Domino d){
    Domino res;
    res.x = d.y;
    res.y = d.x;
    return res;
}

bool estChaine(element* L){
    if (L == NULL || L->suiv == NULL) {
        return true;
    } else {
        Domino d1 = tete(L);
        Domino d2 = tete(L->suiv);
        if (possible(d1, d2)) {
            return estChaine(L->suiv);
        } else {
            return false;
        }
    }

}

/**** Partie 3 ****/

/* Tente de complèter la chaine avec les éléments libres du jeu. */
bool trouveChaine(Domino jeu[], bool libre[], int taille, int nrestant, element* chaine){
    /* jeu - libre - taille : représentent le sac */
    /* chaine : la chaine en cours de construction */
    /* nrestant : le nombre de dominos dans le sac, pour éviter de recompter à chaque appel */
    assert(estChaine(chaine)); // progr. defensive
    if (nrestant == 0){
        printf("Victoire !! : ");
        afficheDominos(chaine);
        detruireListe(chaine); // pour éviter une fuite de mémoire
        return true;
    } else {
        for (int i = 0; i < taille; i++){
            if (libre[i]) {
                Domino dom = jeu[i]; // le domino à ajouter
                bool tester_endroit = true;
                bool tester_envers = true;
                if (chaine != NULL) {
                    Domino tet = tete(chaine); // le domino de tête
                    if (!possible(dom,tet)) tester_endroit = false;
                    if (!possibleAvecRotation(dom,tet)) tester_envers = false;
                }
                libre[i] = false; // on marque le domino utilisé
                if (tester_endroit) {
                    // essayer avec le domino à l'endroit
                    chaine = ajouteTete(chaine, dom);
                    if (trouveChaine(jeu, libre, taille, nrestant-1, chaine)) {
                        libre[i] = true;
                        return true; // une chaine a été trouvée et affichée
                    }
                    chaine = retireTete(chaine); // on remet la chaine en état
                }
                if (tester_envers) {
                    // essayer avec le domino à l'envers
                    chaine = ajouteTete(chaine, rotation(dom));
                    if (trouveChaine(jeu, libre, taille, nrestant-1, chaine)) {
                        libre[i] = true;
                        return true; // une chaine a été trouvée et affichée
                    }
                    chaine = retireTete(chaine); // on remet la chaine en état
                } 
                libre[i] = true; // ATTENTION : on marque le domino non utilisé
            }
        }
        // aucune chaine trouvée, avec aucun des dominos libres
        return false; 
    }
}


/* compte le nombre de chaines complètes possibles */
int nbChaineCompletes(Domino jeu[], bool libre[], int taille, int nrestant, element* chaine){
    assert(estChaine(chaine)); // progr. defensive
    if (nrestant == 0){
        // afficheDominos(chaine);
        return 1;
    } else {
        int c = 0; // compteur du nb de chaines complètes
        for (int i = 0; i < taille; i++){
            if (libre[i]) {
                Domino dom = jeu[i]; // le domino à ajouter
                bool tester_endroit = true;
                bool tester_envers = true;
                if (chaine != NULL) {
                    Domino tet = tete(chaine); // le domino de tête
                    if (!possible(dom,tet)) tester_endroit = false;
                    if (!possibleAvecRotation(dom,tet)) tester_envers = false;
                }
                // ATTENTION : ne pas tourner les dominos symétriques pour le comptage
                if (dom.x == dom.y) tester_envers = false; 

                libre[i] = false; // on marque le domino utilisé
                if (tester_endroit) {
                    // essayer avec le domino à l'endroit
                    chaine = ajouteTete(chaine, dom);
                    c += nbChaineCompletes(jeu, libre, taille, nrestant-1, chaine);
                    chaine = retireTete(chaine); // on remet la chaine en état
                }
                if (tester_envers) {
                    // essayer avec le domino à l'envers
                    chaine = ajouteTete(chaine, rotation(dom));
                    c += nbChaineCompletes(jeu, libre, taille, nrestant-1, chaine);
                    chaine = retireTete(chaine); // on remet la chaine en état
                } 
                libre[i] = true; // on marque le domino non utilisé
            }
        }
        // nombre total
        return c; 
    }
}


/* Partie 4 */
bool insoluble(Domino jeu[], bool libre[], int taille) {
    int compteurs[7] = {0,0,0,0,0,0,0}; // pour les valeurs indiquées sur les dominos
    for (int i = 0; i < taille; i += 1){
        if (libre[i]) {
            compteurs[jeu[i].x] += 1;
            compteurs[jeu[i].y] += 1;
        }
    }
    int nb_impairs = 0;
    for (int i = 0; i < 7; i += 1) {
        if (compteurs[i] % 2 != 0){
            nb_impairs += 1;
        }
    }
    return !(nb_impairs == 0 || nb_impairs == 2);
}



/* Tente de complèter la chaine avec les éléments libres du jeu. */
bool trouveChaineElag(Domino jeu[], bool libre[], int taille, int nrestant, element* chaine){
    /* DEBUT OPTIM  (NB : assez peu efficace ici : on refait le comptage complet à chaque appel) */
    if (insoluble(jeu, libre, taille)){ //
        return false;
    }
    /* FIN OPTIM */
    /* Le reste est identique ...*/
    if (nrestant == 0){
        printf("Victoire !! : ");
        afficheDominos(chaine);
        detruireListe(chaine);
        return true;
    } else {
        for (int i = 0; i < taille; i++){
            if (libre[i]) {
                Domino dom = jeu[i]; // le domino à ajouter
                bool tester_endroit = true;
                bool tester_envers = true;
                if (chaine != NULL) {
                    Domino tet = tete(chaine); // le domino de tête
                    if (!possible(dom,tet)) tester_endroit = false;
                    if (!possibleAvecRotation(dom,tet)) tester_envers = false;
                }
                libre[i] = false; // on marque le domino utilisé
                if (tester_endroit) {
                    // essayer avec le domino à l'endroit
                    chaine = ajouteTete(chaine, dom);
                    if (trouveChaine(jeu, libre, taille, nrestant-1, chaine)) {
                        libre[i] = true;
                        return true; // une chaine a été trouvée et affichée
                    }
                    chaine = retireTete(chaine);
                }
                if (tester_envers) {
                    // essayer avec le domino à l'envers
                    chaine = ajouteTete(chaine, rotation(dom));
                    if (trouveChaine(jeu, libre, taille, nrestant-1, chaine)) {
                        libre[i] = true;
                        return true; // une chaine a été trouvée et affichée
                    }
                    chaine = retireTete(chaine);
                }
                libre[i] = true; // on marque le domino non utilisé
            }
        }
        // aucune chaine trouvée, avec aucun des dominos libres
        return false;
    }
}


int main(){
    printf("Backtracking - Dominos\n");

    /*NB : initialiseur de structure + initialiseur de tableau */
    Domino jeu0[3] = {{.x = 1, .y = 0}, {.x = 1, .y = 1}, {.x = 0, .y = 0}};  // faisable
    bool libre0[3] = {true, true, true};

    Domino jeu1[2] = {{.x = 2, .y = 1}, {.x = 0, .y = 1}};  // faisable avec rotation
    bool libre1[2] = {true, true};

    Domino jeu2[5] = {{.x = 5, .y = 4}, {.x = 4, .y = 0}, 
    {.x = 0, .y = 1}, {.x = 3, .y = 2}, {.x = 3, .y = 5}};  
    bool libre2[5] = {true, true, true, true, true}; // faisable avec rotation

    Domino jeu3[5] = {{.x = 0, .y = 0}, {.x = 0, .y = 1}, 
    {.x = 1, .y = 4}, {.x = 1, .y = 2}, {.x = 2, .y = 2}}; // infaisable
    bool libre3[5] = {true, true, true, true, true};

    Domino jeu4[6] = {{.x = 1, .y = 2}, {.x = 1, .y = 3},
    {.x = 1, .y = 1}, {.x = 2, .y = 3}, {.x = 2, .y = 4}, {.x = 3, .y = 4}};
    bool libre4[6] = {true, true, true, true, true, true};

    Domino jeu5[10] = {
    {.x = 0, .y = 1}, {.x = 0, .y = 2}, {.x = 0, .y = 3}, {.x = 0, .y = 4}, 
    {.x = 1, .y = 2}, {.x = 1, .y = 3}, {.x = 1, .y = 4},
    {.x = 2, .y = 3}, {.x = 2, .y = 4},
    {.x = 3, .y = 4}};
    bool libre5[10] = {true, true, true, true, true, true, true, true, true, true};

    Domino jeu6[15] = {
    {.x = 0, .y = 0}, {.x = 0, .y = 1}, {.x = 0, .y = 2}, {.x = 0, .y = 3}, {.x = 0, .y = 4}, 
    {.x = 1, .y = 1}, {.x = 1, .y = 2}, {.x = 1, .y = 3}, {.x = 1, .y = 4},
    {.x = 2, .y = 2}, {.x = 2, .y = 3}, {.x = 2, .y = 4},
    {.x = 3, .y = 3}, {.x = 3, .y = 4},
    {.x = 4, .y = 4}};
    bool libre6[15] = {true, true, true, true, true, true, true, true, true, true, 
                       true, true, true, true, true};

  
    // une solution ?
    printf("jeu0\n"); trouveChaine(jeu0, libre0, 3, 3, NULL);
    printf("jeu1\n"); trouveChaine(jeu1, libre1, 2, 2, NULL);
    printf("jeu2\n"); trouveChaine(jeu2, libre2, 5, 5, NULL);
    printf("jeu3\n"); trouveChaine(jeu3, libre3, 5, 5, NULL);
    printf("jeu4\n"); trouveChaine(jeu4, libre4, 6, 6, NULL);
    printf("jeu5\n"); trouveChaine(jeu5, libre5, 10, 10, NULL);
    printf("jeu6\n"); trouveChaine(jeu6, libre6, 15, 15, NULL);
  
    // nombre de solutions ?
    printf("jeu0 : %d solutions\n", nbChaineCompletes(jeu0, libre0, 3, 3, NULL));
    printf("jeu1 : %d solutions\n", nbChaineCompletes(jeu1, libre1, 2, 2, NULL));
    printf("jeu2 : %d solutions\n", nbChaineCompletes(jeu2, libre2, 5, 5, NULL));
    printf("jeu3 : %d solutions\n", nbChaineCompletes(jeu3, libre3, 5, 5, NULL));
    printf("jeu4 : %d solutions\n", nbChaineCompletes(jeu4, libre4, 6, 6, NULL));
    printf("jeu5 : %d solutions\n", nbChaineCompletes(jeu5, libre5, 10, 10, NULL));
    printf("jeu6 : %d solutions\n", nbChaineCompletes(jeu6, libre6, 15, 15, NULL));

    return 0;
}