[Howto] étoile magique

**Aryrel Xeon** · 08/01/2009, 17h59

Bonjour,
Connaissez-vous les carrés magiques ?

Et bien je me suis penché sur un problème des plus intéressants: les étoiles magiques.
J'ai tenté une approche purement mathématique, mais je me suis vite heurté à un mur: impossible de trouver un algorithme capable de résoudre de tels problèmes...

Je me dois peut-être de préciser que je ne me suis penché, pour l'instant, que sur les étoiles à six branches (hexagramme ou étoile de David).

Donc, après avoir travailler sur le problème, j'ai dû admettre que mon approche n'était pas la bonne.

Aussitôt, je me suis dit: la programmation !
Bin oui, ce que les maths ne pouvait pas résoudre d'une formule, j'étais sûr d'arriver à faire faire à un ordi le "sale boulot" qui prendrait des heures à un humain.

Malheureusement, je n'ai aucune idée de la manière dont je dois aborder le problème...

En effet, j'ai réussi à faire de mon étoile une matrice (4,6) qui résume le tout, intégrant les conditions, mais après...

Voici l'étoile que j'utilise (pour les variables):

Et voici sa matrice associée (sur la droite et en dessous, c'est la somme de chaque ligne/colonne (resp.) et donc les conditions !)

Je précise que je comprends le C# et le JavaScript, que j'ai des bases en Pascal/Delphi, ainsi qu'en HTML, PHP (surtout) mais que je programme principalement en Basic/TI-Basic. (Assembleur, il fut un temps, mais plus maintenant.)
Donc si vous voulez donner un exemple, ce serait bien que je puisse l'appréhender tout de même...

Je dois aussi dire que je ne vous demande en aucun cas de m'écrire un programme, bien au contraire, je souhaite le faire moi-même, toutefois je ne "vois" pas comment ce faire...
En effet, je ne peux pas lui demander de tester toute les possibilités !
Et je n'ai pas trouvé d'algorithme adapté.
Je me disais que par itération ou plutôt par récurrence, en éliminant au fur et à mesure les nombres testés, etc., je pourrais arriver à quelque chose, mais je tourne en rond !

Pour rappel:

mon étoile est une étoile à six branche
mon "total magique" est donc 26
j'ai à disposition une et une seul fois les nombres de 1 à 12

Ensuite, je précise que OUI, j'ai essayé avec Google, dans trois langues qui plus est !
Que j'ai trouvé quelques sites très intéressants, ainsi que toutes les solutions, mais que je n'ai rien trouvé quant à la programmation permettant de trouver les solutions.
(je pensais mettre en input seulement le nombre de solutions que je recherche, pour l'instant, plus tard, j'essayerai de l'étendre aux étoiles à n-branches)

Je me réjouis d'entendre vos avis sur la question, j'espère avoir trouvé le bon endroit pour mon message et je vous prie d'être indulgent si j'ai enfreint une règle quelconque du forum que je n'aurais pas vue.
(J'ai lu les règles avant de poster

)

Cordialement, Aryrel.

Annexe:
Lien intéressant sur les étoiles magiques (en anglais), on y trouve aussi des infos sur les carrés du même nom ainsi que sur d'autre curiosités du genre.

EDIT: excusez, je me suis trompé avec le lien des images, maintenant c'est corrigé.

**Tommy31** · 09/01/2009, 15h18

J'ai pas lu dans le détail, mais je pense que prolog est une réponse accessible à la découverte des solutions d'un tel problème.

Note que ca revient à explorer un espace, avec élimination des chemins qui n'aboutissent pas.

**Trap D** · 09/01/2009, 23h37

Prolog + bibliothèque de programmation par contraintes : voir ici. C'est tout à fait ça !

**pseudocode** · 10/01/2009, 13h14

Envoyé par Aryrel Xeon

Ensuite, je précise que OUI, j'ai essayé avec Google, dans trois langues qui plus est !
Que j'ai trouvé quelques sites très intéressants, ainsi que toutes les solutions, mais que je n'ai rien trouvé quant à la programmation permettant de trouver les solutions.
(je pensais mettre en input seulement le nombre de solutions que je recherche, pour l'instant, plus tard, j'essayerai de l'étendre aux étoiles à n-branches)

Tu peux employer le même genre d'algo que pour les Sudoku (exploration avec backtracking). Pour trouver TOUTES les solutions et pas juste une seule, il suffit de forcer un backtrack lorsque tu trouves une solution.

**Trap D** · 10/01/2009, 18h18

Envoyé par pseudocode

Tu peux employer le même genre d'algo que pour les Sudoku (exploration avec backtracking). Pour trouver TOUTES les solutions et pas juste une seule, il suffit de forcer un backtrack lorsque tu trouves une solution.

Chacun prône pour sa chapelle

**pseudocode** · 10/01/2009, 18h57

Envoyé par Trap D

Chacun prône pour sa chapelle

C'est clair. Je suis un agent de Sun, payé pour promouvoir Java.

Cela dit, je pense qu'il veut coder dans un langage impératif:

Envoyé par le PO

Je précise que je comprends le C# et le JavaScript, que j'ai des bases en Pascal/Delphi, ainsi qu'en HTML, PHP (surtout) mais que je programme principalement en Basic/TI-Basic. (Assembleur, il fut un temps, mais plus maintenant.)

Et puis de toutes façons, Prolog fait aussi du backtracking.

**Trap D** · 10/01/2009, 19h36

Ton raisonnement est tout à fait logique, tu devrais te contraindre à faire du Prolog

(j'ai honte )

**pseudocode** · 10/01/2009, 19h56

Envoyé par Trap D

Ton raisonnement est tout à fait logique, tu devrais te contraindre à faire du Prolog

(j'ai honte )

J'en ai fait... j'ai pas aimé la syntaxe, alors j'ai codé mon propre moteur d'inférence (j'étais fou à l'époque). Maintenant j'utilise Jess.

**Tommy31** · 10/01/2009, 23h57

Jess c'est du chainage avant, alors que prolog c'est du chainage arrière, non ?

**pseudocode** · 11/01/2009, 00h37

Envoyé par Tommy31

Jess c'est du chainage avant, alors que prolog c'est du chainage arrière, non ?

Jess fait du chainage avant et du chainage arrière. Il est basé sur CLIPS et donc utilise l'algo Rete. Mais c'est vrai qu'on l'utilise plutot pour faire du chainage avant.

**laurentibus** · 11/01/2009, 14h00

c'est vrai que le prolog c hardcore à integrer in da head

surtout quand on fait d autres langages a coté ....

y as deux ans quand je faisais du CSC ( programmation par contraintes ... ou un truc comme ca

... désolé j allais pas trop en cours

) alors on avait un problemes avec des carrées alpha magiques ... et on utilisé ILOG dans la version java .... vraiment tres utile et assez comprehensible

..
à tester ...

bon courage ++

**Trap D** · 11/01/2009, 15h17

J'ai un passé de programmeur C, j'ai mis plus d'un an à m'habituer à raisonner en Prolog (ceci dit je n'en faisais pas non plus 24 h sur 24)

**ToTo13** · 11/01/2009, 15h51

Bonjour,

si tu veux développer un modèle qui fasse cela, tu peux :
- calculer toute les combinaisons possible pour ton hexagramme.
- pour chaque combinaison calculer si elle forme une étoile magique.
- lancer une méthode par apprentissage (régression logistique, svm, pmc, forêt aléatoires) pour voir si une de ces méthode parvient à créer un modèle que saurait classer les combinaisons.

**Aryrel Xeon** · 12/01/2009, 18h03

Ok, merci pour ces réponses rapides...
En attendant, je me suis lancé dans la création en TI-Basic dudit programme avec simplement des boucles imbriquées contrôlant les conditions, mais je ne suis pas arrivé à quelque chose de concluant...

Je vais voir de plus près vos idées, dommage que cela soit uniquement en prolog et java (que je ne connais pas vraiment et que je peux à peine lire)

Je retiens également l'idée de toto, mais... ça en fait beaucoup d'essais ^^'

**SpiceGuid** · 12/01/2009, 19h27

Envoyé par ToTo13

si tu veux développer un modèle qui fasse cela, tu peux :
- calculer toute les combinaisons possible pour ton hexagramme.
- pour chaque combinaison calculer si elle forme une étoile magique.

Toutes les permutations

, fait "rechercher" car c'est un sujet qui revient souvent par ici.

Je retiens également l'idée de toto, mais... ça en fait beaucoup d'essais ^^'

Dans un premier temps il faut commencer par tester toutes les permutations, ça ne posera pas de problème de performance pour ton étoile à 6 branches où tu ne permute que les entiers de 1 à 12.
Dans un second temps pour augmenter la taille des données tu es obligé d'introduire des heuristiques liées à ton problème, pour te donner une idée de jusqu'où on peut aller avec cette méthode (petit défi aux fanas du Prolog

) :

**Aryrel Xeon** · 12/01/2009, 21h22

Je veux bien, mais pour rappel, avec 12 nombres, on a 479'001'600 permutations possibles...

Ça risque pas de rendre mon programme très lent, de toutes les chercher ???
Et en plus, il va être assez gourmand en mémoire, non ?

**Trap D** · 12/01/2009, 22h13

Je suis en train de tester en cherchant une pyramide de N lignes qui vérifie les conditions avec tous les nombres de 1 à N (N+1)/2, ça prend du temps pour N = 11 ...

**pseudocode** · 12/01/2009, 22h41

Envoyé par Aryrel Xeon

Je veux bien, mais pour rappel, avec 12 nombres, on a 479'001'600 permutations possibles...

Ça risque pas de rendre mon programme très lent, de toutes les chercher ???

Ce n'est pas la peine de toutes les tester. Il y a des symétries dans ton étoile magique. Et également une contrainte sur le total magique. A mon avis, cela serait plus simple de faire de la programmation dynamique que faire de l'exploration combinatoire.

**SpiceGuid** · 13/01/2009, 15h18

Envoyé par Aryrel Xeon

Je veux bien, mais pour rappel, avec 12 nombres, on a 479'001'600 permutations possibles...

Ne soit pas craintif, 479'001'600 permutations c'est vraiment rien du tout, surtout pour du code natif.
Dans un premier temps tu fais vite un programme qui marche.
Dans un second temps tu feras un programme qui marche vite.

Envoyé par Trap D

Je suis en train de tester en cherchant une pyramide de N lignes qui vérifie les conditions avec tous les nombres de 1 à N (N+1)/2, ça prend du temps pour N = 11 ...

Sur la machine que j'avais à l'époque (PIII 500Mhz) ça avait pris un certain temps

Si tu as déjà un programme (félicitations!

) tu peux le tester avec N=5, à partir de N=6 les entiers de 1 à N (N+1)/2 ne suffisent plus et tu dois passer des permutations aux arrangements.
Pour N=11 les entiers de 1 à 100 ne suffisent pas, il y a toutefois deux autres pyramides avec des entiers compris entre 1 et 101.

**Trap D** · 13/01/2009, 17h55

J'ai fait le prog en Prolog pour l'étoile, il trouve une solution en 0,64 s, et Prolog n'est pas réputé pour sa rapidité.

Pour ceux que ça intéresse, mon implémentation de ton prog de Pyramide est celle-ci :

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
:- use_module(library('clpfd.pl')).
 
test(N) :-
	Number is N * (N+1) / 2,
	length(Vars, Number),
 
	Vars ins 1..Number,
 
	all_different(Vars),
 
	% initialisation des règles de construction de la pyramide
	init_vars(Vars, 1, N),
 
	label(Vars),
 
       % ecriture de la pyramide
	write_vars(1, N, Vars), 
	nl, nl.
 
% initialisation ligne par ligne
init_vars(_L, N, N).
 
init_vars(L, N, Max) :-
	init_line(L, N),
	N1 is N + 1,
	init_vars(L, N1, Max).
 
% on a besoin du numéro de ligne 
% et de la liste des variables
init_line(L, N) :-
       % Calcul des indices dans la liste des variables
	Min is (N - 1) * N/2 + 1,
	Max is Min + N - 1,
	init_val(L, N, Min, Max).
 
% initalisation de chaque élément de la liste
init_val(L, N, M, M) :-
	!,
        % un nombre de la pyramide est la valeur absolue
        % des la différences des deux nombres qui sont en dessous
        % de lui
	nth1(M, L, E1),
	I1 is M + N,
	nth1(I1, L, E2),
	I2 is I1 + 1,
	nth1(I2, L, E3),
        % affectation de la contrainte à l'élément
	affecte_val(E1,E2,E3).
 
init_val(L, N, M1, M) :-
	!,
	nth1(M1, L, E1),
	I1 is M1 + N,
	nth1(I1, L, E2),
	I2 is I1 + 1,
	nth1(I2, L, E3),
	affecte_val(E1,E2,E3),
	M2 is M1 + 1,
	init_val(L, N, M2, M).
 
% il faut distinguer à cause des contraintes
% de la programmation par contraintes !!
% deux cas
affecte_val(E1,E2,E3) :-
	E2 #> E3,
	E1 #= E2 - E3.
 
affecte_val(E1,E2,E3) :-
	E2 #< E3,
	E1 #= E3 - E2.
 
% ecriture de la pyramide
write_vars(_, _, []). 
 
% ici on écrit N nombres
% On décale d'abord de la place de Max - N + 1 nombres
write_vars(N, Max, V) :-
	K is Max - N,
	forall(between(1, K, _), write('  ')),
	write_nombre(N, V, V1),
	N1 is N+1,
	write_vars(N1, Max, V1).
 
 
write_nombre(0, L, L) :-
	!,
	nl.
 
% l'affichage est prévu pour des nombres inférieurs à 100
write_nombre(N, [H|T], L) :-
	(   H < 10 -> write(' '); true), write(H), write('  '),
	N1 is N - 1,
	write_nombre(N1, T, L).

Résultat pour 5 :

Code :

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

1
2
3
4
5
6
7
8
9
10
1 ?- time(test(5)).
         5  
       9   4  
     2  11   7  
  10  12   1   8  
13   3  15  14   6  
 
 
% 50,717,242 inferences, 11.70 CPU in 12.19 seconds (96% CPU, 4333650 Lips)
true.

Je ne fais afficher que la première réponse.
Je vais étudier tes remarques.

[Howto] étoile magique

Algorithmes et structures de données

Discussions similaires

Partager

Partager