Discussion :

[SpiceGuid]

Je ne fais afficher que la première réponse.

Ça tombe bien il n'y a qu'une seule réponse pour N=5

Je trouve ça formidable que tu puisse prototyper aussi vite une solution en Prolog

Mon conseil pour améliorer ta solution: au lieu de permuter tous les nombres dans la pyramide tu peux ne tester que les arrangements sur la ligne de base.
C'est-à-dire que tu testes les arrangements de N entiers parmi N×(N+1)/2.
La partie supérieure de la pyramide ne sert plus qu'à valider l'arrangement sur la ligne de base.
Pour N=5 la seule ligne de base valide est 13 3 15 14 6 (ou bien son symétrique).

Atout supplémentaire: une fois que tu as réalisé cette optimisation il devient possible d'accroître la taille de la pyramide (chercher parmi plus de N×(N+1)/2 entiers) sans beaucoup modifier ton code.

[pseudocode]

Ça tombe bien il n'y a qu'une seule réponse pour N=5

Par contre pour l'étoile magique (n=6) il y en a 960 !

[Trap D]

Ça tombe bien il n'y a qu'une seule réponse pour N=5

Non il y en a 2 ... mais elle sont symétriques

Mon conseil pour améliorer ta solution: au lieu de permuter tous les nombres dans la pyramide tu peux ne tester que les arrangements sur la ligne de base.
C'est-à-dire que tu testes les arrangements de N entiers parmi N×(N+1)/2.
La partie supérieure de la pyramide ne sert plus qu'à valider l'arrangement sur la ligne de base.
Pour N=5 la seule ligne de base valide est 13 3 15 14 6 (ou bien son symétrique).

Atout supplémentaire: une fois que tu as réalisé cette optimisation il devient possible d'accroître la taille de la pyramide (chercher parmi plus de N×(N+1)/2 entiers) sans beaucoup modifier ton code.

Pas forcément facile à coder avec des contraintes, je vais y réfléchir

[pseudocode]

Et pour ceux que ça intéresse, mon code Java pour trouver les solutions des étoiles magiques pour N quelconque.

Code java :

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
int N = 6;
 
int magicnumber = 4*N+2;
int nmElements = 2*N;
int[] elements = new int[nmElements];
boolean[] used = new boolean[nmElements+1];
 
// assigne une valeur d'un element
void setElement(int index, int value) {
	elements[index]=value;
	if (value!=0) used[value]=true;
}
 
// supprime la valeur d'un element
void unsetElement(int index) {
	int value = elements[index];
	if (value!=0) used[value]=false;
	setElement(index,0);
}
 
// Test si la somme sur un segment est correcte
boolean isEdgeCorrect(int edgenumber) {
	// index des 4 elements alignés
	int n1 = 2*edgenumber;
	int n2 = (n1+1) % nmElements;
	int n3 = (n1+3) % nmElements;
	int n4 = (n1+4) % nmElements;
 
	// teste si la somme excede le magicnumber
	int sum = elements[n1]+elements[n2]+elements[n3]+elements[n4];
	if (sum>magicnumber) return false;
 
	// teste si le segment est rempli ET que la somme est égale au magicnumber
	boolean full=(elements[n1]>0) && (elements[n2]>0) && (elements[n3]>0) && (elements[n4]>0);
	if (full && sum!=magicnumber)  return false;
 
	return true;
}
 
// Test si la figure est correcte
boolean isStarCorrect() {
 
	// test la somme de chaque segment
	for(int i=0;i<N;i++)
		if (!isEdgeCorrect(i)) return false;
 
	return true;
}
 
/*** LA METHODE A APPELER POUR CALCULER LES SOLUTIONS ***/
void solve() {
	int solcount=0;
 
	// pour chaque element formant l'étoile
	int index=0;
	while(index>=0) {
 
 
		// valeur actuelle
		int value = elements[index];
 
		// retire la valeur
		unsetElement(index);
 
		// trouve la premiere valeur supérieur qui n'est pas utilisée
		value++;
		while(value<=nmElements && used[value]) value++;
 
		if (value>nmElements) {
			// pas de valeur trouvée : retour arrière de l'index
			index--;
			continue;
		}
 
		// assigne la valeur
		setElement(index, value);
 
		// le choix ne donne pas une figure correcte 
		if (!isStarCorrect()) {
			// on va a nouveau modifier l'element courant
			continue;
		}
 
		// sinon, c'est que la figure actuelle est correcte: on avance l'index
		index++;
 
		// la figure est remplie : on a une solution au probleme
		if (index >= nmElements) {
			// on affiche la solution
			System.out.println(Arrays.toString(elements));
			solcount++;
 
			// on force un retour arrière pour trouver les autres solutions
			index--;
		}					
 
	}
 
	System.out.println("Nb de solution(s):"+solcount);
}

Pour N=6 -> 960 solutions en 0.250 s
Pour N=7 -> 1008 solutions en 1.6 s
Pour N=8 -> 1792 solutions en 14.25 s

(et oui, la complexité est exponentielle )