Des carrés magiques : un problème vieux de plus de 200 ans

[LeJeu]

Ma moulinette me donne aussi 7040
Si on considère comme un seul carré magique ceux qui se déduisent par certaines transformations, il faut diviser par 8 et on arrive bien à 880

Pour éliminer les symétriques, comme on a fixé par les tests de rotations possibles la case en haut à gauche, la seule symétrie possible est celle par rapport à la diagonale descendante

pour éliminer les symétries il suffit d’éliminer les carrés dont la case en dessous du coin en haut à gauche est plus petite que la case à droite du coin en haut à gauche !!!

Et hop 880 !!!

[beagle]

Me suis jamais intéressé à la comptabilité du nombre de carrés magiques,
mais à leur structure,
un jour quand j'aurais le temps faudra que je vois si je sais construire tous les 4x4,
ou combien sont irréguliers et alors pourquoi comment.
Je devrais pouvoir faire du dénombrement avec les structures aussi.
Mais tout ceci est ancien, et si j'ai rechuté il y a quelques années, j'ai pas envie de replonger en ce moment.
Si personne ne m'embète à ma maison de retraite peut-ètre.

[LeJeu]

Me suis jamais intéressé à la comptabilité du nombre de carrés magiques,
mais à leur structure,
un jour quand j'aurais le temps faudra que je vois si je sais construire tous les 4x4,
ou combien sont irréguliers et alors pourquoi comment.
Je devrais pouvoir faire du dénombrement avec les structures aussi.
Mais tout ceci est ancien, et si j'ai rechuté il y a quelques années, j'ai pas envie de replonger en ce moment.
Si personne ne m'embète à ma maison de retraite peut-ètre.

Tu sais, dénombrer les carrés en informatique est assez 'trivial' voir bourrin, vu que tu n'es pas à un million d'opérations prêt

mais, quand même... il y a un certain plaisir à écrire le programme et à voir s'afficher : 880...

Sinon : je ( mon programme) trouve toutes les soluces en calculant 5 997 611 fois la somme de cinq cases : quelqu'un a mieux ?

Fatal_error est en we ???

[beagle]

esthétique du programme
versus esthétique de la structure comme je connais

sachant que cela peut se rejoindre

je ne saurais pas jugé l'esthétique du programme.
fatal te répondra en effet.

Pour le "simple" cube 5x5 Boyer en avait bavé il me semble mème avec l'ordi.

[LeJeu]

Pour le "simple" cube 5x5 Boyer en avait bavé il me semble mème avec l'ordi.

carré d'ordre 5 ?

Ok - Sors nous une formule à la beagle ... et je te la confirme en faisant tourner l'ordi
j'ai jeté un coup d'oeil sur le net, visiblement il y a moins de candidat au dénombrement que pour l'ordre 4 !

[fatal_error]

Fatal_error est en we ???

salut leJeu,

oui je suis en we :ptdr:
mais bon, pas mal de sport en ce moment po trop le temps de geeker

[beagle]

Perhaps you can see at magic square order 5:

http://www.gaspalou.fr/magic-squares/order-5.htm

http://www.knechtmagicsquare.paulscomputing.com/Magic%20Square%20Order%205%20Complete%20set.html

http://users.eastlink.ca/~sharrywhite/Order5.html

c'était forcément un multiple de 5 moins 1, hein Le Jeu?

PS: si un crétin parle de cube 5x5, fortes chances que cela soit une beaglerie
mais au vu du nombre de carrés magiques en 5x5, on comprend mieux la difficulté du cube!
Ceci étant Boyer ne cherchait pas tous les cubes 5x5x5, mais un seul (il en trouva quelques uns).

[chan79]

[quote="LeJeu"]
Juste pour rêver: un carré (trouvé sur le site de Gérard Villemin) constitué uniquement de nombres premiers !
[img][IMG]http://img51.imageshack.us/img51/7510/premh.png[/img][/IMG]
Sinon, beaucoup plus modestement, pour les amateurs de moulinettes, combien de carrés 4*4 en utilisant uniquement les entiers de 1 à 8 (deux fois chacun) ?

[beagle]

Bernard Gervais a publié un bouquin sur les carrés 5x5 uniquement.
Cela confirme le total de 275 305 224 des références sus-jaccentes,
la première ref est ce nombre fois 8, QS cela doit ètre les mèmes symétries que celles que tu as décrites Le Jeu pour le 4x4 où tu divisais par 8 aussi.

Bernard Gervais s'est amusé de façon originale.
Il colorie de façon différente les cases nombres pairs et les cases des nombres impairs.
cela forme des motifs géométriques,
et dans ces familles géométriques il recalcule combien elles possèdent de carrés magiques.

il a ainsi 721 familles géométriques différentes.
Et il retrouve entre autres choses le nombre total de 275 305 224.

[LeJeu]

Bernard Gervais a publié un bouquin sur les carrés 5x5 uniquement.
Cela confirme le total de 275 305 224 des références sus-jaccentes,
la première ref est ce nombre fois 8, QS cela doit ètre les mèmes symétries que celles que tu as décrites Le Jeu pour le 4x4 où tu divisais par 8 aussi..

Dès fois je ne doute de rien...
Fort de ma moulinette à carré de 4 qui marchait plutôt pas mal, je suis reparti comme en 14 en l'adaptant au carré de 5.
J'ai bien vu que le premier dénombrement ne datait que de 1971, mais je me suis dit que vu les progrès des processeurs, on pouvait éspérer faire aussi bien pour pas cher ..

Grand espérance...

Le programme tourne bien mais n' a trouvé "que" 2 000 000 de solutions en 1h30... ce qui devrait donner les 275 millions de solutions en un plus d'une semaine ....

Beagle je crois que vais avoir à regarder du côté de la structure interne ( et de son esthétisme) pour avancer un peu : une idée ?

[LeJeu]

Le programme tourne bien mais n' a trouvé "que" 2 000 000 de solutions en 1h30... ce qui devrait donner les 275 millions de solutions en un plus d'une semaine ....

Le programme est écrit en C avec fonction d'exploration récursive, le tout compilé et exécuté sur un Intel I7 3.40Ghz

On doit pouvoir gagner quelques % de temps en supprimant la récursivité mais rien par rapport au gain de performance à trouver !

[beagle]

Beagle pas toucher une bille en informatique.
Ce que j'appelle la structure interne repose sur les connaissances des méthodes de fabrication de certains carrés = pourquoi elles marchent, comment elles marchent.
La structure interne est différente pour les carrés pairs et les carrés impairs,
les méthodes de fabrication sont différentes.
Autant pour le 4x4 je suis assez confiant pour penser à pas ou très peu de structure irrégulière = ne correspondant aux méthodes de fabrication, car il n' y a pas beaucoup de place pour créer ces irrégularités,
autant dans le déjà 5x5, ce que je connais des structures dérivant des méthodes classiques de fabrication , cela ne doit représenter qu'une faible proportion des carrés.
Donc mon approche par la compréhension de ah ben oui, construit comme cela cela marche parce que ... ne permet pas une aide pour développer des recherches exaustives.

Si on reprend le boulot de Gervais, qui ne visait pas au programme informatique le plus rapide,
il bossait d'autres choses, mais dans son approche, il dit avoir conçu 218 programmes différents pour lister le nombre de carrés par familles géométriques telles qu'il les avait définies.

Je suis de la génération avant la microinformatique,
mes carrés sont faits à la main, sur une base géométrique, des notions vectorielles qui me passent au-dessus de la tète (malheureusement) ...,
des symétries axiales, des symétries centrales, du rangement -pliage pour enfant ...

[LeJeu]

Si on reprend le boulot de Gervais, qui ne visait pas au programme informatique le plus rapide,
il bossait d'autres choses, mais dans son approche, il dit avoir conçu 218 programmes différents pour lister le nombre de carrés par familles géométriques telles qu'il les avait définies.

Tu me diras, vu que mon programme me livre la solution dans une semaine, je peux me contenter d'aller boire un bière et de le laisser faire... Çà ira certainement plus vite que d'écrire 218 pgms ....

[LeJeu]

Sinon, beaucoup plus modestement, pour les amateurs de moulinettes, combien de carrés 4*4 en utilisant uniquement les entiers de 1 à 8 (deux fois chacun) ?

Dans un premier temps j'ai recyclé le programme 4*4 en changeant juste les chiffres utilisés ( et la somme attendue )

Code: Tout sélectionner

Nombre de solutions : 72448

Evidemment, c'est beaucoup trop .. au bas mot d'un facteur de 2^8 ( 256)

Bien sûr, dans ce genre de moulinette qui se veut donner la liste exhaustive des solutions, il ne suffit pas de dire je divise le nombre de solutions par 256... mais il faut changer l'algo pour ne plus compter les doublons !! Ici c'est tout simple.. il suffit de différencier les 2 chiffres de même valeurs et de n'autoriser l'usage du second que si le premier a été utilisé ( suis-je clair ?)

Code: Tout sélectionner

Nombre de solutions : 283

Ps - Et passage des 500 000 solutions pour le carré de 5 à l'instant (4 h), en ce moment sortent les solutions qui commencent par 1 5 sur la première ligne ....on n'est pas rendu

[chan79]

Dans un premier temps j'ai recyclé le programme 4*4 en changeant juste les chiffres utilisés ( et la somme attendue )

Code: Tout sélectionner

Nombre de solutions : 72448

Evidemment, c'est beaucoup trop .. au bas mot d'un facteur de 2^8 ( 256)

Bien sûr, dans ce genre de moulinette qui se veut donner la liste exhaustive des solutions, il ne suffit pas de dire je divise le nombre de solutions par 256... mais il faut changer l'algo pour ne plus compter les doublons !! Ici c'est tout simple.. il suffit de différencier les 2 chiffres de même valeurs et de n'autoriser l'usage du second que si le premier a été utilisé ( suis-je clair ?)

Code: Tout sélectionner

Nombre de solutions : 283

Ps - Et passage des 500 000 solutions pour le carré de 5 à l'instant (4 h), en ce moment sortent les solutions qui commencent par 1 5 sur la première ligne ....on n'est pas rendu

Ah, j'ai 1952 soit 1952/8=244
je vais revoir mon algo

[LeJeu]

Ah, j'ai 1952 soit 1952/8=244
je vais revoir mon algo

Et comme je disais un peu plus haut, il te faut de plus injecter la détection des doublons dans ton algo pour ne pas avoir à diviser par 8 ( rotation & symétrie) et pouvoir ainsi donner une liste exhaustive des solutions distinctes.

Dis moi, si tu es bien ok avec moi ou si je dois aussi allez vérifier mon algo ! ( mais sur ce coup je serais plutôt confiant sur ma proposition )

[chan79]

Et comme je disais un peu plus haut, il te faut de plus injecter la détection des doublons dans ton algo pour ne pas avoir à diviser par 8 ( rotation & symétrie) et pouvoir ainsi donner une liste exhaustive des solutions distinctes.

Dis moi, si tu es bien ok avec moi ou si je dois aussi allez vérifier mon algo ! ( mais sur ce coup je serais plutôt confiant sur ma proposition )

Pas vu d'erreur, mais bon ... ???

[LeJeu]

Pas vu d'erreur, mais bon ... ???

Mais comme on ne peut pas trouver des résultats différents et exacts il va falloir négocier ..

On attend un arbitre ? on échange nos codes ? Chan79 tu as le choix de la méthodologie !

[chan79]

[img][IMG]http://img853.imageshack.us/img853/1096/25669477.png[/img][/IMG]
Voilà ma méthode
Je fais varier de 1 à 8 les nombres dans les cases rouges.
Je fais des soustractions pour calculer les autres:
X=18-E-F-G
Y=18-A-B-C
etc
Si le résultat est inférieur ou égal à 0 ou strictement supérieur à 18, je passe.
Je vérifie que toutes les sommes font bien 18 (il y en a deux à vérifier)
Je fais un sous-programme pour vérifier que chaque nombre de 1 à 8 apparait deux fois.

[LeJeu]

Je fais varier de 1 à 8 les nombres dans les cases rouges.
Je fais des soustractions pour calculer les autres:
X=18-E-F-G
Y=18-A-B-C
etc
Si le résultat est inférieur ou égal à 0 ou strictement supérieur à 18, je passe.
Je vérifie que toutes les sommes font bien 18 (il y en a deux à vérifier)
Je fais un sous-programme pour vérifier que chaque nombre de 1 à 8 apparait deux fois.

J'ai un peu honte avec mon rouleau compresseur ....
Choix de ABCY - contrainte ABCY = 18
Choix de DVW - contrainte ADVW= 18
Choix de GF - contrainte WGFY = 18
Choix de EZ -...
....
Aucune anticipation "pour calculer", quelle que soit la situation : le pgm essaie tous les chiffres qui restent ( un humain verrait les impossibilités - les solutions évidentes - le pgm vérifie tout ..)

ceci dit :
1) j'ai du rater un truc : pourquoi dis tu que les cases rouges sont remplies par les nb de 1 à 8 ? pourquoi pas deux chiffres 1 par exemple ?
2) pourquoi dis tu que les 4 cases centrales font une somme de 18 ?