- /****** 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;
- }