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