Problème Carré magique

**Bukow** · 14/02/2012, 00h43

Bonjour,

Dans le cadre de mon cours d'algo a la fac, j'ai un petit exercice ou je dois trouver toutes les solutions d'un carré magique(donc en tenant compte des symétries etc).

La première question de l'exercice consistait a trouver toute les solutions d'un carré de taille 3. Celle ci j'y suis arrivé. Cependant la deuxieme question demande de trouver la solution d'un carré de taille n. Et biensur on nous demande de préciser a partir de quelle taille de n le calcul prend trop de temps ( note : il n'est pas précisé ce que "trop de temps" signifie en terme de minute/heure).

Tout ceci se fait dans une longue lignée d'exercice sur le thème du backtracking (problème des n reines etc). Donc je ne suis pas super a l'aise avec ca.

Le problème c'est que ca marche pour TAILLE_CARRE = 3, mais lorsque je met 4, là ca ne marche plus, du moins je n'ai pas testé plus de 3 minutes, ca tourne et ca ne me sort aucun résultat. J'ai essayé d'utiliser gdb, mais j'avoue n'être pas super a l'aise avec cet outil. Je compile tout ca sur une vieille débian et une vieille bécane a base de P3, c'est ptetre pour ca que ca prend trop de temps, ou alors c'est un problème d'algo. Fin bref, si vous pouvez jetez un coup d'oeil.
Voici mon code, en C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TAILLE_CARRE 4
 
//renvoi la somme d'une ligne
int sommeLigne(int ligne, int** carre)
{
	int col,res;
	res=0;
	for(col = 0;col<TAILLE_CARRE;col++)
	 	res+=carre[ligne][col];
	return res;
}
//renvoi la somme d'une colonne
int sommeCol(int col,int** carre)
{
	int lig,res;
	res = 0;
	for(lig = 0;lig <TAILLE_CARRE;lig++)
	 	res+=carre[lig][col];
	return res;
}
//renvoi la somme de la premiere diag
int sommeDiag1(int** carre)
{
	int i;
	int res = 0;
	for(i = 0;i<TAILLE_CARRE;i++)
		res+=carre[i][i];
	return res;
}
//deuxieme diag
int sommeDiag2(int** carre)
{
	int i=TAILLE_CARRE-1;
	int res = 0;
	while(i>=0)
	{
		res+= carre[TAILLE_CARRE-1-i][i];
		i--;
	}
	return res;
}
//renvoi vrai si le carré passé en paramètre est magique, faux sinon
bool estMagique(int** carre)
{
	int ligne;
	bool testL = true;
	bool testC = true;
	int somme = (TAILLE_CARRE*(TAILLE_CARRE*TAILLE_CARRE +1))/2;
	for(ligne = 0;ligne<TAILLE_CARRE;ligne++)
	{
		if(sommeLigne(ligne,carre) != somme)
			testL = false;
		if(sommeCol(ligne,carre) != somme)
			testC = false;
	}
	bool sommeD = false;
	if((sommeDiag1(carre) == somme) && (sommeDiag2(carre) == somme))
 		sommeD = true;
	return (sommeD && testL && testC);
}
//essaye de placer un numero passé en paramètre dans le carré magique
void placer(int numero,  int** carre)
{
		int i,j;
		if(numero == TAILLE_CARRE*TAILLE_CARRE +1)
		{
			if(estMagique(carre))
			{	//affichage
				int lig,col;
				for(lig = 0;lig<TAILLE_CARRE;lig++)
				{
					for(col = 0;col<TAILLE_CARRE;col++)
					{
 
						printf("%d ",carre[lig][col]);
						if(col == TAILLE_CARRE-1)
							printf("\n");
					}
 
				}
				//fin affichage
				printf("\n\n\n");
			}
		}
		else
		{
			for(i = 0;i<TAILLE_CARRE;i++)
			{
				for(j =0;j<TAILLE_CARRE;j++)
				{
					if(carre[i][j] == 0)
					{
						carre[i][j] = numero;
						placer(numero+1,carre);
						carre[i][j] = 0;
					}
				}
			}
		}
}
 
int main(void)
{
	//allocation dynamique du carré
	int** car = malloc(TAILLE_CARRE*sizeof(int*));
	int k;
	for(k = 0;k<TAILLE_CARRE;k++)
	{
		car[k] = malloc(TAILLE_CARRE*sizeof(int));
	}
 
 
	int i,j;
	for(i = 0;i<TAILLE_CARRE;i++)
	{
		for(j = 0;j<TAILLE_CARRE;j++)
		{
			car[i][j] = 0;
		}
	}
 
 
	placer(1,car);
 
 
 
 
	return 0;
}

Merci

**Neckara** · 14/02/2012, 07h12

Carré magique = somme des colonnes et des lignes égales non?

Si pour ton deuxième exercice, il faut juste trouver UNE solution, je ne sais pas quel algo tu utilise mais il y en a un très simple :

Tu as une grille vide.
Tu as les nombres 1 à n² à mettre
Tu choisit une case au hasard.
i := 1
Tant que les cases ne sont pas toutes remplie :
-Tu notes i sur la case
- Tu prend la case qui se trouve en haut à droite de celle-ci
- Si tu "dépasse" de la grille à droite, tu prend la case de la même ligne colonne 0
- Si tu "dépasse" en haut, tu prend la case de la même colonne ligne tout en bas (ligne n)
- Si la case est déjà prise, tu va sur la case qui est en-dessous.
- i := i+1
Fin tant que

Après si tu veux plusieurs solutions, ça marche en prenant "en bas à droite", "en-bas à gauche" "en haut à gauche" ... (c'est comme si tu pivotait ta grille de 90° )

Donc tu devrais trouver 4n² solutions, après existe-t-il d'autres solutions?

EDIT : premier réflexe, placer des printf aux bons endroits pour repérer s'il n'y a pas de boucles infinies ou autre.

**diogene** · 14/02/2012, 12h14

Fin bref, si vous pouvez jetez un coup d'oeil.

Il faut revoir l'algorithme utilisé. La force brute utilisée est trop brute.

Pour TAILLE_CARRE = 4 :
Ton algo commence à placer dans l'ordre 1,2,...16 puis essaye de replacer 15 et 16 , puis 14,15 et 16..., puis ...
L'ennui est que le nombre d'appel à la fonction croît plus vite que (16-p)! lorsqu'on tente de replacer p, p+1,...16 (la profondeur de récursion 17 n'est pas en cause)
Avant de tenter de replacer le 10..., on aura 13710 appels de la fonction, le 9... on aura 109 610 appels, le 8... 986 418 appels, le 7... 9 864 108 appels, le 6...108 505 118 appels, etc. On peut espérer avoir fini autour d'un nombre de 10^14 appels !

Tu peux donc aller dormir tranquille avant de voir le résultat !

**Bukow** · 14/02/2012, 12h23

Merci de vos réponses, Neckera oui un carré magique de taille n est une matrice ou la somme de chaque ligne/colonne/diagonale est égale a n(n²+1)/2

Et je dois trouver TOUTE les solutions même les symétries (quand tu me dis de tourner a 90° je suppose que c'est ce dont tu parle), en utilisant l'algorithme de backtracking qu'on a utilisé pour résoudre le problème des n reines.

Bon effectivement la complexité a l'air assez démesuré, je vais essayer de réfléchir pour améliorer tout ca.

**Bukow** · 15/02/2012, 14h06

Bon finallement voici quelques petites améliorations qui me permettent de calculer un carré de taille 4 :

Ca met environ 2 minutes sur ma machine pour tous les trouver.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TAILLE_CARRE 4
 
 
 
 
//renvoi la somme d'une ligne
int sommeLigne(int ligne, int** carre)
{
	int col,res;
	res=0;
	for(col = 0;col<TAILLE_CARRE;col++)
	 	res+=carre[ligne][col];
	return res;
}
//renvoi la somme d'une colonne
int sommeCol(int col,int** carre)
{
	int lig,res;
	res = 0;
	for(lig = 0;lig <TAILLE_CARRE;lig++)
	 	res+=carre[lig][col];
	return res;
}
//renvoi la somme de la premiere diag
int sommeDiag1(int** carre)
{
	int i;
	int res = 0;
	for(i = 0;i<TAILLE_CARRE;i++)
		res+=carre[i][i];
	return res;
}
//deuxieme diag
int sommeDiag2(int** carre)
{
	int i=TAILLE_CARRE-1;
	int res = 0;
	while(i>=0)
	{
		res+= carre[TAILLE_CARRE-1-i][i];
		i--;
	}
	return res;
}
//renvoi vrai si le carré passé en paramètre est magique, faux sinon
bool estMagique(int** carre)
{
	int ligne;
	bool testL = true;
	bool testC = true;
	int somme = (TAILLE_CARRE*(TAILLE_CARRE*TAILLE_CARRE +1))/2;
	for(ligne = 0;ligne<TAILLE_CARRE;ligne++)
	{
		if(sommeLigne(ligne,carre) != somme)
			testL = false;
		if(sommeCol(ligne,carre) != somme)
			testC = false;
	}
	bool sommeD = false;
	if((sommeDiag1(carre) == somme) && (sommeDiag2(carre) == somme))
 		sommeD = true;
	return (sommeD && testL && testC);
}
//essaye de placer un numero passé en paramètre dans le carré magique
 
 
//indique s'il est possible d'ajouter n a la case i,j
bool ajoutPossible(int n, int lig,int col,int** carre)
{
	int somme = (TAILLE_CARRE*(TAILLE_CARRE*TAILLE_CARRE +1))/2;
	bool testC = (sommeCol(col,carre) + n <= somme);
	bool testL = (sommeLigne(lig,carre) + n <= somme);
	bool testDiag1 = (sommeDiag1(carre) + n <= somme);
	bool testDiag2 = (sommeDiag2(carre) +n <= somme);
	if( (lig==col))
        	return testC && testL && testDiag1;
        else if((lig+col == TAILLE_CARRE-1))
        	return (testC && testL && testDiag2);
	else
		return testC & testL;
 
}
void placer(int numero,  int** carre)
{
		int i,j;
		if(numero == 0)
		{
			if(estMagique(carre))
			{	//affichage
				int lig,col;
				for(lig = 0;lig<TAILLE_CARRE;lig++)
				{
					for(col = 0;col<TAILLE_CARRE;col++)
					{
 
						printf("%d ",carre[lig][col]);
						if(col == TAILLE_CARRE-1)
							printf("\n");
					}
 
				}
				//fin affichage
				printf("\n\n\n");
			}
		}
		else
		{
			for(i = 0;i<TAILLE_CARRE;i++)
			{
				for(j =0;j<TAILLE_CARRE;j++)
				{
					if(carre[i][j] == 0 && ajoutPossible(numero,i,j,carre ))
					{
						carre[i][j] = numero;
						placer(numero-1,carre);
						carre[i][j] = 0;
					}
				}
			}
		}
}
 
int main(void)
{
	//allocation dynamique du carré
	int** car = malloc(TAILLE_CARRE*sizeof(int*));
	int k;
	for(k = 0;k<TAILLE_CARRE;k++)
	{
		car[k] = malloc(TAILLE_CARRE*sizeof(int));
	}
 
 
	int i,j;
	for(i = 0;i<TAILLE_CARRE;i++)
	{
		for(j = 0;j<TAILLE_CARRE;j++)
		{
			car[i][j] = 0;
		}
	}
 
 
	placer(TAILLE_CARRE*TAILLE_CARRE,car);
 
 
 
 
	return 0;
}

Voilà, je vais réfléchir au symétrie, peut être est-ce possible de trouver des carré de taille 5, pour le moment ca prend beaucoup trop de temps.

**diogene** · 16/02/2012, 11h55

Toujours sur ton modèle de programme, il est possible d'améliorer les choses.
Un point critique est la fonction ajoutPossible() appelée de nombreuses fois. On a intérêt à la rendre la plus rapide possible, notamment en en sortant dès que la décision est prise. Par exemple, celle-ci fait gagner un facteur 2 en temps (chez moi)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
bool ajoutPossible(int n, int lig,int col,int** carre)
{
	int somme = (TAILLE_CARRE*(TAILLE_CARRE*TAILLE_CARRE +1))/2;
        if(sommeCol(col,carre) + n > somme) return false;
        if(sommeLigne(lig,carre) + n > somme) return false;
        if(lig==col)
           if(sommeDiag1(carre) + n > somme)return false;
        if(lig+col == TAILLE_CARRE-1)
           if(sommeDiag2(carre) +n > somme)return false;
        return true;
}

Une source de ralentissement dans cette fonction vient du calcul des sommes qui impliquent à chaque fois une boucle sur TAILLE_CARRE éléments. On a intérêt à stocker la valeur courante de ces sommes. Par exemple, en regroupant ces données,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
typedef struct
{
   int ** carre; // les éléments du carré
   int * somL;   // sommes des éléments des lignes du carré
   int * somC;   // sommes des éléments des colonnes du carré
   int somD1;    // somme des éléments de la diagonale du carré
   int somD2;    // somme des éléments de l'antidiagonale du carré
} TCarreMagique;

SomL et somD nécessite une allocation de TAILLE_CARRE int initialisés à 0 et somD1 etsomD2 sont initialisés à 0.

ajoutPossible() devient alors :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
bool ajoutPossible(int n, int lig,int col,TCarreMagique* carreMagique)
{
	int somme = (TAILLE_CARRE*(TAILLE_CARRE*TAILLE_CARRE +1))/2;
        if(carreMagique->somL[lig] + n > somme) return false;
        if(carreMagique->somC[col] + n > somme) return false;
        if(lig==col) return carreMagique->somD1 + n <= somme ;
        if(lig+col == TAILLE_CARRE-1) return  carreMagique->somD2 +n <= somme;
        return true;
}

Il faut mettre à jour le carré et les différentes sommes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
void add(int n, int lig,int col,TCarreMagique* carreMagique)
{
  carreMagique->carre[lig][col] += n;
  carreMagique->somL[lig] += n ;
  carreMagique->somC[col] += n ;
  if(lig==col)carreMagique->somD1 += n;
  else if(lig+col == TAILLE_CARRE-1)carreMagique->somD2 +=n ;
}

placer() devient :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void placer(int numero, TCarreMagique * carreMagique )
{
  int i,j;
  if(numero == 0)
  {
      if(estMagique(carreMagique));//...affiche(carreMagique->carre);
  }
  else
      for(i = 0;i<TAILLE_CARRE;i++)
	for(j =0;j<TAILLE_CARRE;j++)
	   if(carreMagique->carre[i][j] == 0 && ajoutPossible(numero,i,j,carreMagique))
	   {
              add(numero,i,j,carreMagique);
	      placer(numero-1,carreMagique);
              add(-numero,i,j,carreMagique);
	   }
}

estMagique() est également à modifier pour la cohérence du code, mais appelé peu souvent n'apportera pas un gain appréciable. Les fonctions sommeLigne(), sommeCol(),... deviennent alors inutile.

Au total, un gain en temps d'un facteur ~4 est obtenu par rapport au code d'origine.
Pour aller plus loin, il va falloir, je crois, modifier le principe de l'algorithme lui-même.

**kwariz** · 16/02/2012, 14h15

Envoyé par Bukow

Bonjour,

Dans le cadre de mon cours d'algo a la fac, j'ai un petit exercice ou je dois trouver toutes les solutions d'un carré magique(donc en tenant compte des symétries etc).

La première question de l'exercice consistait a trouver toute les solutions d'un carré de taille 3. Celle ci j'y suis arrivé. Cependant la deuxieme question demande de trouver la solution d'un carré de taille n. Et biensur on nous demande de préciser a partir de quelle taille de n le calcul prend trop de temps ( note : il n'est pas précisé ce que "trop de temps" signifie en terme de minute/heure).

(...)

Hello,

pour info le nombre de carrés magiques (les solutions symétriques ne comptent que pour 1) en fonction de n, l'ordre du carré, est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
  n        NCM(n)
  1        1                              trivial
  2        0                              trivial
  3        1                              obtenu en -650
  4        880                            obtenu en 1693
  5        275305224                      obtenu en 1973
  6        de l'ordre de 10^19            obtenu en 2004
  7...     inconnu

cf A006052.

Autant 4 est jouable, 5 devient une gageure au-delà c'est infaisable.

**Bukow** · 16/02/2012, 16h00

Waouh c'est génial Diogene merci beaucoup.

Qu'entend tu par modifier le principe de l'algorithme lui même ?

Car si tu veux, le but de cette exercice est de nous faire travailler le backtracking, et si il faut changer radicalement l'algorithme, je sort du cadre du cours et ce n'est pas ce que mon prof attend.

Enfin en tout cas merci beaucoup pour toutes ces précisions, c'est vraiment super.

**anacharsis** · 20/02/2012, 19h35

salut !

on a inventé les logiciels de calcul formel pour ça.

j'ai téléchargé XCAS la semaine dernière et le système de 10 équations à 16 inconnues correspondant aux contraintes d'un carré magique d'ordre 4 est résolu en quelques secondes. on se retrouve avec seulement 7 paramètres entiers (moins que pour la résolution du carré d'ordre 3).

je pense pouvoir écrire un programme en C générant les arrangements de 7 parmi 16 en quelques secondes.

A+

Problème Carré magique

C

Vue hybride

Discussions similaires

Partager

Partager