[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.