1. /****** Backtracking dominos ******/
  2.  
  3. #include <stdbool.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <assert.h>
  7.  
  8. /* Domino */
  9. struct domino_s {
  10. int x; // valeur de gauche
  11. int y; // valeur de droite
  12. };
  13.  
  14. typedef struct domino_s Domino;
  15.  
  16. /* Maillon */
  17. struct element_s {
  18. Domino d;
  19. struct element_s* suiv;
  20. };
  21.  
  22. typedef struct element_s element;
  23.  
  24. /* Chaine */
  25. typedef element* chaine;
  26.  
  27.  
  28. /**** Partie 1 ****/
  29.  
  30. /* Affiche les dominos d'une liste */
  31. void afficheDominos(element* L){
  32. element* l = L;
  33. while (l != NULL) {
  34. printf("(%d,%d)-", l->d.x, l->d.y);
  35. l = l->suiv;
  36. }
  37. printf("\n");
  38. }
  39.  
  40. /* Alloue un maillon dans le tas, et l'ajoute en tête de liste */
  41. element* ajouteTete(element* L, Domino d){
  42. element* elt = (element*) malloc(sizeof(element));
  43. elt->d = d; elt->suiv = L;
  44. return elt;
  45. }
  46.  
  47. /* Obtenir le domino de tête de liste (sans modifier la liste) */
  48. Domino tete(element* L){
  49. assert(L != NULL);
  50. return L->d;
  51. }
  52.  
  53. /* Retire la tête de liste (et rend le maillon au tas) */
  54. element* retireTete(element* L){
  55. assert(L != NULL);
  56. element* a_renvoyer = L->suiv;
  57. free(L);
  58. return a_renvoyer;
  59. }
  60.  
  61. /* Destruction de liste - version récursive -*/
  62. void detruireListe(element* L){
  63. if (L != NULL) {
  64. element* suiv = L->suiv;
  65. free(L);
  66. detruireListe(suiv);
  67. }
  68. }
  69.  
  70. /**** Partie 2 ****/
  71.  
  72. bool possible(Domino di, Domino dj){
  73. return di.y == dj.x;
  74. }
  75.  
  76. bool possibleAvecRotation(Domino di, Domino dj){
  77. return di.x == dj.x;
  78. }
  79.  
  80. Domino rotation(Domino d){
  81. Domino res;
  82. res.x = d.y;
  83. res.y = d.x;
  84. return res;
  85. }
  86.  
  87. bool estChaine(element* L){
  88. if (L == NULL || L->suiv == NULL) {
  89. return true;
  90. } else {
  91. Domino d1 = tete(L);
  92. Domino d2 = tete(L->suiv);
  93. if (possible(d1, d2)) {
  94. return estChaine(L->suiv);
  95. } else {
  96. return false;
  97. }
  98. }
  99.  
  100. }
  101.  
  102. /**** Partie 3 ****/
  103.  
  104. /* Tente de complèter la chaine avec les éléments libres du jeu. */
  105. bool trouveChaine(Domino jeu[], bool libre[], int taille, int nrestant, element* chaine){
  106. /* jeu - libre - taille : représentent le sac */
  107. /* chaine : la chaine en cours de construction */
  108. /* nrestant : le nombre de dominos dans le sac, pour éviter de recompter à chaque appel */
  109. assert(estChaine(chaine)); // progr. defensive
  110. if (nrestant == 0){
  111. printf("Victoire !! : ");
  112. afficheDominos(chaine);
  113. detruireListe(chaine); // pour éviter une fuite de mémoire
  114. return true;
  115. } else {
  116. for (int i = 0; i < taille; i++){
  117. if (libre[i]) {
  118. Domino dom = jeu[i]; // le domino à ajouter
  119. bool tester_endroit = true;
  120. bool tester_envers = true;
  121. if (chaine != NULL) {
  122. Domino tet = tete(chaine); // le domino de tête
  123. if (!possible(dom,tet)) tester_endroit = false;
  124. if (!possibleAvecRotation(dom,tet)) tester_envers = false;
  125. }
  126. libre[i] = false; // on marque le domino utilisé
  127. if (tester_endroit) {
  128. // essayer avec le domino à l'endroit
  129. chaine = ajouteTete(chaine, dom);
  130. if (trouveChaine(jeu, libre, taille, nrestant-1, chaine)) {
  131. libre[i] = true;
  132. return true; // une chaine a été trouvée et affichée
  133. }
  134. chaine = retireTete(chaine); // on remet la chaine en état
  135. }
  136. if (tester_envers) {
  137. // essayer avec le domino à l'envers
  138. chaine = ajouteTete(chaine, rotation(dom));
  139. if (trouveChaine(jeu, libre, taille, nrestant-1, chaine)) {
  140. libre[i] = true;
  141. return true; // une chaine a été trouvée et affichée
  142. }
  143. chaine = retireTete(chaine); // on remet la chaine en état
  144. }
  145. libre[i] = true; // ATTENTION : on marque le domino non utilisé
  146. }
  147. }
  148. // aucune chaine trouvée, avec aucun des dominos libres
  149. return false;
  150. }
  151. }
  152.  
  153.  
  154. /* compte le nombre de chaines complètes possibles */
  155. int nbChaineCompletes(Domino jeu[], bool libre[], int taille, int nrestant, element* chaine){
  156. assert(estChaine(chaine)); // progr. defensive
  157. if (nrestant == 0){
  158. // afficheDominos(chaine);
  159. return 1;
  160. } else {
  161. int c = 0; // compteur du nb de chaines complètes
  162. for (int i = 0; i < taille; i++){
  163. if (libre[i]) {
  164. Domino dom = jeu[i]; // le domino à ajouter
  165. bool tester_endroit = true;
  166. bool tester_envers = true;
  167. if (chaine != NULL) {
  168. Domino tet = tete(chaine); // le domino de tête
  169. if (!possible(dom,tet)) tester_endroit = false;
  170. if (!possibleAvecRotation(dom,tet)) tester_envers = false;
  171. }
  172. // ATTENTION : ne pas tourner les dominos symétriques pour le comptage
  173. if (dom.x == dom.y) tester_envers = false;
  174.  
  175. libre[i] = false; // on marque le domino utilisé
  176. if (tester_endroit) {
  177. // essayer avec le domino à l'endroit
  178. chaine = ajouteTete(chaine, dom);
  179. c += nbChaineCompletes(jeu, libre, taille, nrestant-1, chaine);
  180. chaine = retireTete(chaine); // on remet la chaine en état
  181. }
  182. if (tester_envers) {
  183. // essayer avec le domino à l'envers
  184. chaine = ajouteTete(chaine, rotation(dom));
  185. c += nbChaineCompletes(jeu, libre, taille, nrestant-1, chaine);
  186. chaine = retireTete(chaine); // on remet la chaine en état
  187. }
  188. libre[i] = true; // on marque le domino non utilisé
  189. }
  190. }
  191. // nombre total
  192. return c;
  193. }
  194. }
  195.  
  196.  
  197. /* Partie 4 */
  198. bool insoluble(Domino jeu[], bool libre[], int taille) {
  199. int compteurs[7] = {0,0,0,0,0,0,0}; // pour les valeurs indiquées sur les dominos
  200. for (int i = 0; i < taille; i += 1){
  201. if (libre[i]) {
  202. compteurs[jeu[i].x] += 1;
  203. compteurs[jeu[i].y] += 1;
  204. }
  205. }
  206. int nb_impairs = 0;
  207. for (int i = 0; i < 7; i += 1) {
  208. if (compteurs[i] % 2 != 0){
  209. nb_impairs += 1;
  210. }
  211. }
  212. return !(nb_impairs == 0 || nb_impairs == 2);
  213. }
  214.  
  215.  
  216.  
  217. /* Tente de complèter la chaine avec les éléments libres du jeu. */
  218. bool trouveChaineElag(Domino jeu[], bool libre[], int taille, int nrestant, element* chaine){
  219. /* DEBUT OPTIM (NB : assez peu efficace ici : on refait le comptage complet à chaque appel) */
  220. if (insoluble(jeu, libre, taille)){ //
  221. return false;
  222. }
  223. /* FIN OPTIM */
  224. /* Le reste est identique ...*/
  225. if (nrestant == 0){
  226. printf("Victoire !! : ");
  227. afficheDominos(chaine);
  228. detruireListe(chaine);
  229. return true;
  230. } else {
  231. for (int i = 0; i < taille; i++){
  232. if (libre[i]) {
  233. Domino dom = jeu[i]; // le domino à ajouter
  234. bool tester_endroit = true;
  235. bool tester_envers = true;
  236. if (chaine != NULL) {
  237. Domino tet = tete(chaine); // le domino de tête
  238. if (!possible(dom,tet)) tester_endroit = false;
  239. if (!possibleAvecRotation(dom,tet)) tester_envers = false;
  240. }
  241. libre[i] = false; // on marque le domino utilisé
  242. if (tester_endroit) {
  243. // essayer avec le domino à l'endroit
  244. chaine = ajouteTete(chaine, dom);
  245. if (trouveChaine(jeu, libre, taille, nrestant-1, chaine)) {
  246. libre[i] = true;
  247. return true; // une chaine a été trouvée et affichée
  248. }
  249. chaine = retireTete(chaine);
  250. }
  251. if (tester_envers) {
  252. // essayer avec le domino à l'envers
  253. chaine = ajouteTete(chaine, rotation(dom));
  254. if (trouveChaine(jeu, libre, taille, nrestant-1, chaine)) {
  255. libre[i] = true;
  256. return true; // une chaine a été trouvée et affichée
  257. }
  258. chaine = retireTete(chaine);
  259. }
  260. libre[i] = true; // on marque le domino non utilisé
  261. }
  262. }
  263. // aucune chaine trouvée, avec aucun des dominos libres
  264. return false;
  265. }
  266. }
  267.  
  268.  
  269. int main(){
  270. printf("Backtracking - Dominos\n");
  271.  
  272. /*NB : initialiseur de structure + initialiseur de tableau */
  273. Domino jeu0[3] = {{.x = 1, .y = 0}, {.x = 1, .y = 1}, {.x = 0, .y = 0}}; // faisable
  274. bool libre0[3] = {true, true, true};
  275.  
  276. Domino jeu1[2] = {{.x = 2, .y = 1}, {.x = 0, .y = 1}}; // faisable avec rotation
  277. bool libre1[2] = {true, true};
  278.  
  279. Domino jeu2[5] = {{.x = 5, .y = 4}, {.x = 4, .y = 0},
  280. {.x = 0, .y = 1}, {.x = 3, .y = 2}, {.x = 3, .y = 5}};
  281. bool libre2[5] = {true, true, true, true, true}; // faisable avec rotation
  282.  
  283. Domino jeu3[5] = {{.x = 0, .y = 0}, {.x = 0, .y = 1},
  284. {.x = 1, .y = 4}, {.x = 1, .y = 2}, {.x = 2, .y = 2}}; // infaisable
  285. bool libre3[5] = {true, true, true, true, true};
  286.  
  287. Domino jeu4[6] = {{.x = 1, .y = 2}, {.x = 1, .y = 3},
  288. {.x = 1, .y = 1}, {.x = 2, .y = 3}, {.x = 2, .y = 4}, {.x = 3, .y = 4}};
  289. bool libre4[6] = {true, true, true, true, true, true};
  290.  
  291. Domino jeu5[10] = {
  292. {.x = 0, .y = 1}, {.x = 0, .y = 2}, {.x = 0, .y = 3}, {.x = 0, .y = 4},
  293. {.x = 1, .y = 2}, {.x = 1, .y = 3}, {.x = 1, .y = 4},
  294. {.x = 2, .y = 3}, {.x = 2, .y = 4},
  295. {.x = 3, .y = 4}};
  296. bool libre5[10] = {true, true, true, true, true, true, true, true, true, true};
  297.  
  298. Domino jeu6[15] = {
  299. {.x = 0, .y = 0}, {.x = 0, .y = 1}, {.x = 0, .y = 2}, {.x = 0, .y = 3}, {.x = 0, .y = 4},
  300. {.x = 1, .y = 1}, {.x = 1, .y = 2}, {.x = 1, .y = 3}, {.x = 1, .y = 4},
  301. {.x = 2, .y = 2}, {.x = 2, .y = 3}, {.x = 2, .y = 4},
  302. {.x = 3, .y = 3}, {.x = 3, .y = 4},
  303. {.x = 4, .y = 4}};
  304. bool libre6[15] = {true, true, true, true, true, true, true, true, true, true,
  305. true, true, true, true, true};
  306.  
  307. // une solution ?
  308. printf("jeu0\n"); trouveChaine(jeu0, libre0, 3, 3, NULL);
  309. printf("jeu1\n"); trouveChaine(jeu1, libre1, 2, 2, NULL);
  310. printf("jeu2\n"); trouveChaine(jeu2, libre2, 5, 5, NULL);
  311. printf("jeu3\n"); trouveChaine(jeu3, libre3, 5, 5, NULL);
  312. printf("jeu4\n"); trouveChaine(jeu4, libre4, 6, 6, NULL);
  313. printf("jeu5\n"); trouveChaine(jeu5, libre5, 10, 10, NULL);
  314. printf("jeu6\n"); trouveChaine(jeu6, libre6, 15, 15, NULL);
  315. // nombre de solutions ?
  316. printf("jeu0 : %d solutions\n", nbChaineCompletes(jeu0, libre0, 3, 3, NULL));
  317. printf("jeu1 : %d solutions\n", nbChaineCompletes(jeu1, libre1, 2, 2, NULL));
  318. printf("jeu2 : %d solutions\n", nbChaineCompletes(jeu2, libre2, 5, 5, NULL));
  319. printf("jeu3 : %d solutions\n", nbChaineCompletes(jeu3, libre3, 5, 5, NULL));
  320. printf("jeu4 : %d solutions\n", nbChaineCompletes(jeu4, libre4, 6, 6, NULL));
  321. printf("jeu5 : %d solutions\n", nbChaineCompletes(jeu5, libre5, 10, 10, NULL));
  322. printf("jeu6 : %d solutions\n", nbChaineCompletes(jeu6, libre6, 15, 15, NULL));
  323.  
  324. return 0;
  325. }