/* Ce programme est une version optimisée pour p=4 du programme quad_n_p.c */ /* -------------------------------------------------------------------------- */ /* 31/07/1999 */ /* Source : quad_n_4.c */ /* Auteur : V. Menu (vmenu@wanadoo.fr) */ /* -------------------------------------------------------------------------- */ /* QUADRILLAGE : sur un carré de n*n cases noires, quel nombre minimum de cases faut-il blanchir pour qu'il n'y ait aucune suite de p cases noires alignées dans une des 4 directions horizontale, verticale et les 2 diagonales ? */ /* Le problème (n=9, p=4) faisait partie des éliminatoires aux championnats de France des jeux mathématiques et logiques en 1989 (éliminatoires parus dans Science et Vie). Son énoncé et ses 2 solutions ont été publiés dans les annales du championnat (Problème 21 du volume 5 intitulé "La fraction du bicentenaire", édition Hatier); aucune méthode n'était proposée */ /* Ce programme fonctionne de la façon suivante : on essaie de remplir la grille avec aucune case blanche, puis en cas d'échec, avec 1, puis 2, etc..., jusqu'à l'obtention d'un seuil max_blanc de cases blanches permettant de trouver des solutions. Pour chaque valeur de max_blanc étudiée, on appelle une procédure récursive de remplissage des cases de la grille. Pour cela, on progresse case par case (de gauche à droite, et de haut en bas). Dans une première phase, on noircit la case et on teste les contraintes d'alignement qui s'appliquent compte tenu du remplissage déjà effectué (de 0 à 4 contraintes suivant la position de la case). Si elles sont respectées, on avance d'une case et on recommence. Les 4 contraintes sur la case X sont indiquées avec des x : x o o x o o x o o o x o x o x o o o -> cases déjà remplies o o x x x o o o o x x x X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . -> cases non remplies . . . . . . . . . . . . . . . . . . Dans le cas contraire, ou si l'exploration de l'arborescence précédente n'a rien donné, on blanchit la case en vérifiant qu'il reste assez de cases blanches disponibles pour terminer la grille. Dans ce cas, on avance d'une case et on recommence. Afin de limiter au maximum l'explosion combinatoire, chaque contrainte est appliquée dès qu'on peut le faire (dès col >= p pour les tests en horizontal, et dès lig >= p pour les tests en vertical et en diagonale). On a trouvé une solution dès que l'on a réussi à atteindre la fin de la grille */ /* Solutions obtenues pour différentes valeurs de n n : cases blanches minimum 4 : 4 5 : 7 6 : 10 7 : 13 (solution triviale en croix) 8 : 20 9 : 25 10 : 32 11 : 40 ? (solution triviale en croix ?) */ #include #include #include #define MAX_N 20 /* Taille maximum du carré */ int i, j; /* Compteurs */ int fin; /* 1 si une solution a été trouvée, 0 sinon */ int n; /* Taille du carré */ int max_blanc; /* Nombre maximal de cases que l'on peut blanchir */ int blanc; /* Nombre de cases déjà blanchies */ int carre[MAX_N+1][MAX_N+1]; /* Couleur de la case : 0=noir, 1=blanc */ int blanc_minimum[MAX_N+1][MAX_N+1];/* Nombre minimum de cases blanches encore nécessaires pour terminer un carré solution depuis la case (i,j), supposée blanche */ clock_t time1, time2; /* Pour mesurer le temps d'exécution */ /* Affiche les grilles solutions */ void AfficheGrille () { int i, j; fin = 1; time2 = clock(); printf ("Temps cumulé=%4.2lf\n", (double) (time2-time1) / CLK_TCK); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) printf("%2d",carre[i][j]); printf("\n"); } printf("Appuyer sur pour continuer\n"); getchar(); } /* On teste la case située à la ligne "lig" et à la colonne "col" */ void place (int lig, int col) { /* Phase 1 : on met la case à noir et on applique les contraintes d'alignement. Pour cela, on teste les cases précédentes déjà remplies : horizontale, verticale, diagonale gauche, diagonale droite pour vérifier que l'ajout de cette case noire ne génère pas un alignement de 4 cases noires */ carre[lig][col] = 0; /* Les 3 cases de gauche sont-elles noires ? */ if ((col >= 4) && (carre[lig][col-1] == 0) && (carre[lig][col-2] == 0) && (carre[lig][col-3] == 0)) goto blanc; if (lig >= 4) { /* Les 3 cases au-dessus sont-elles noires ? */ if ((carre[lig-1][col] == 0) && (carre[lig-2][col] == 0) && (carre[lig-3][col] == 0)) goto blanc; /* Les 3 cases en diagonale en haut à gauche sont-elles noires ? */ if ((col >= 4) && (carre[lig-1][col-1] == 0) && (carre[lig-2][col-2] == 0) && (carre[lig-3][col-3] == 0)) goto blanc; /* Les 3 cases en diagonale en haut à droite sont-elles noires ? */ if ((col <= n-3) && (carre[lig-1][col+1] == 0) && (carre[lig-2][col+2] == 0) && (carre[lig-3][col+3] == 0)) goto blanc; } /* On a pu laisser la case (lig,col) à noir : on avance d'une case */ if (col < n) place(lig, col+1); else if (lig < n) place(lig+1, 1); else /* lig=n et col=n : on a trouvé un carré solution*/ AfficheGrille(); blanc:; /* Phase 2 : on met la case à blanc et on applique la contrainte sur le nombre total de cases blanches */ carre[lig][col] = 1; blanc++; /* Il faut vérifier qu'il reste assez de cases blanches utilisables pour trouver une solution sans prendre plus de "max_blanc" cases blanches en tout. Par exemple, pour le carré 9x9, il faut un minimum de 2 cases blanches par ligne : ce n'est donc pas la peine de continuer s'il reste 3 lignes entières à remplir et 5 cases blanches (ou moins) à utiliser. Le nombre minimum de cases blanches nécessaires pour arriver à une grille gagnante à partir de la position (lig,col) a été calculé dans le tableau "blanc_minimum" en début de programme */ if (max_blanc - blanc >= blanc_minimum[lig][col]) { /* Il reste assez de cases blanches, on avance d'une case */ if (col < n) place(lig, col+1); else if (lig < n) place(lig+1, 1); else /* lig=n et col=n : on a trouvé un carré solution*/ AfficheGrille(); } /* Pas assez de cases blanches restantes, on n'explore pas l'arborescence de cette position */ blanc--; } void main() { fin = 0; do { printf("Taille du carré (1 <= n <= %1d) : ", MAX_N); scanf("%d",&n); } while (!((n >= 1) && (n <= MAX_N))); time1 = clock(); /* Calcul du nombre minimum de cases blanches nécessaires pour terminer un carré solution depuis la case (i,j) supposée blanche (le minimum calculé n'est pas toujours le minimum réel (qui peut être plus grand), mais c'est quand même un minimum nécessaire) */ for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) blanc_minimum[i][j] = (n/4)*(n - i) + (n - j)/4; /* Recherche des solutions avec le minimum de cases blanches */ for (max_blanc = 0; fin == 0; max_blanc++) { /* Début du remplissage avec max_blanc cases blanches maximum */ blanc = 0; place(1, 1); time2 = clock(); printf("Fin étude des positions avec %2d cases blanches, Temps cumulé=%4.2lf\n", max_blanc, (double) (time2-time1) / CLK_TCK); } }