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

[chan79]

sommes nous bien d'accord?, le nombre de 1-6
est amputé des 1-4 et 1-3
ton 19 est les 1-6 non déjà comptabilisés dans les 1-4?

oui, par exemple les 26 sont ceux qui commencent par 26 mais qui ne sont "équivalents" à aucun des 11, 12, 13, 14, 15, 16, 17, 18, 21 ,22, 23, 24 et 25.

Par exemple, on ne peut pas comptabiliser
2637
5724
3186
8451

il est équivalent à (symétrie centrale)

1548
6831
4275
7362

qui est déjà comptabilisé dans ceux qui commencent par 1
De plus, il ne faut pas mettre deux 26 équivalents

Autrement, ça se complique de plus en plus... Va falloir trouver une astuce

pour ceux qui commencent par 1, j'ai

[img][IMG]http://imageshack.us/a/img546/3950/59296851.png[/img][/IMG]

Il faudrait stocker en mémoire les 1952 carrés et créer un test qui permette de comparer deux carrés. Il donnerait 1 s'ils sont équivalents ( image l'un de l'autre par une sym-rot) ou 0 sinon.
Mais je n'ai pas les outils pour faire ça.

[C.Ret]

Il faudrait stocker en mémoire les 1952 carrés et créer un test qui permette de comparer deux carrés. Il donnerait 1 s'ils sont équivalents ( image l'un de l'autre par une sym-rot) ou 0 sinon.
Mais je n'ai pas les outils pour faire ça.

C'est justement à cela que servent mes polynômes caractéristiques.

A chaque carré déterminé, je calcule le polynôme de valeur minimale. Selon la formule utilisée, je sais immédiatement s'il s'agit d'un carré direct (identitaire), ou d'une transformation simple (symétrie axiale horizontale, verticale, diagonale ou anti-diagonale) ou composée (voir les quatres compositions qui sont aussi en quelque sorte les rotation dont parle Dszlogic).

Comme l'a justement fait remarquer Dszlogic, stocker en mémoire le polynôme caractéristique (64 bit en hexa) fait une substantielle économie de mémoire. Mais ce n'est qu'un détail aujourd'hui étant donné la puissance de calcul dont vous disposez.

C'est surtout un moyen simple et systématique de vérifier si un carré ou l'un quelconque de ses symétriques a déjà été découvert.


C'est d'autant plus important qu'avec la répétition des nombres utilisés, les symétries "cachées" sont multipliées et que comme vous explorez séquentiellement et systématiquement les branches de l'arbre, il faut impérativement vérifier qu'une symétrie fortuite dans une branche ne fait pas un nœud avec une autre partie de l'arbre.


De plus, en codant comme je l'ai fait les "premières" case du carré par les puissances supérieures du polynôme, on est sûr que lors de l'exploration d'une branche (par exemple 1 2 4 ... ) tous les carré qui appartiennent bien à celle-ci auront d'office un nombre caractéristique minimal (identitaire). Si tout d'un coup votre exploration produit des carré symétriques simples ou composés, c'est que vous avez été "trop loin" ou qu'à cet endroit il y a un nœud qui vous a fait passer sur une autre "branche de l'arbre de recherche".

Ce peut être une information très importante. Surtout si vous cherchez à développer un algorithme qui sera capable par la suite d'explorer des carrés plus grands, ou simplement un autre jeu de nombres, ou utiliser des transformations de ces nombres (par exemple un carré magique composé de carrés).

[beagle]

Très intéressant tout ça.
Chan peux tu balancer les deux carrés 1-8,
qui sont par rapport à mon analyse des structures irrégulières,
et cela me ferait gagner du temps de ne pas avoir à tatonner pour retrouver ce genre de famille de structure, je vois comment faire, mais je risque d'y passer du temps.
Merci.

PS:Pour les 1-6, c'est à priori le mème endroit qui avait fait foirer ma première méthode et qui aboutissait à des faux qui marchent pas,
l'autre baguette magique permet de maitriser ce passage, à condition de le régler correctement, et j'ai été trop restrictif, et je vois où.
maintenant il y a aussi au moins 1 structure irrégulière dans les 1-6 j'imagine.

PS: ton décompte des 1-truc est le mème que Le Jeu, j'espère qu'il va revenir jouer.

[chan79]

Très intéressant tout ça.
Chan peux tu balancer les deux carrés 1-8,
qui sont par rapport à mon analyse des structures irrégulières,
et cela me ferait gagner du temps de ne pas avoir à tatonner pour retrouver ce genre de famille de structure, je vois comment faire, mais je risque d'y passer du temps.
Merci.

PS:Pour les 1-6, c'est à priori le mème endroit qui avait fait foirer ma première méthode et qui aboutissait à des faux qui marchent pas,
l'autre baguette magique permet de maitriser ce passage, à condition de le régler correctement, et j'ai été trop restrictif, et je vois où.
maintenant il y a aussi au moins 1 structure irrégulière dans les 1-6 j'imagine.

PS: ton décompte des 1-truc est le mème que Le Jeu, j'espère qu'il va revenir jouer.

les voilà
1827
8532
5463
4176

1836
8361
5274
4527

Faudra que je regarde la méthode de C.Ret, ça a l'air pas mal

[beagle]

Génial, merci Chan,
j'ai analysé le premier,
c'est une structure irrégulière,
finalement régulière dans l'irrégulier.

[Dlzlogic]

Bonjour,
Après vérification, je confirme que je trouve 424 carrés différents.
Voila, à mon avis, la raison pour laquelle ce n'est égal à 1952/8 :
Il y a 12 façons d'assembler 4 chiffres de 1 à 8 pour totaliser 18.
strcpy(Tab4C[0],"1278"); strcpy(Tab4C[1],"1368"); strcpy(Tab4C[2],"1458");
strcpy(Tab4C[3],"1467"); strcpy(Tab4C[4],"2358"); strcpy(Tab4C[5],"2367");
strcpy(Tab4C[6],"2457"); strcpy(Tab4C[7],"3456");
strcpy(Tab4C[8],"1188"); strcpy(Tab4C[9],"2277");
strcpy(Tab4C[10],"3366"); strcpy(Tab4C[11],"4455");

Chacune de ces façons dite de base peuvent générer d'autres mots de 4 chiffres.
Les 8 premiers mots par permutation peuvent produire chacun 11 mots supplémentaires
les 4 derniers ne peuvent en produire que 5 supplémentaires.
Lorsqu'on fait le décompte de toutes les possibilités, on utilise pour chaque mot de base 12+6 possibilités. Ceci donne 1952, tout le monde est d'accord.
Par contre, si les mots comportaient toujours des chiffres différents, alors le décompte total ne viendrait pas de l'assemblage (12et6) mais de (12et12)
Dans le cas présent on a 8 x 24 + 4 x 6 = 216. (PM 24 = 4!)
Dans l'hypothèse de 4 chiffres tous différents, on aurait 12 x 24 = 288 possibilités.

Dans le décompte des carrés différents, la répétition d'un même chiffre dans un mot, n'a aucune influence que le phénomène symétrie/rotation.
Pour calculer le nombre de carrés indépendants, il faudrait diviser par 8 le nombre total de possibilités. Ce nombre n'a pas été calculé puisque on a considéré que 1188 était identique à 1188, en d'autres termes que le mot 1188 ne générait pas 11 autres mots par permutation, mais seulement 5.
Ceci n'est que mon avis.
Naturellement le source est à disposition.

[beagle]

Bravo Dlzlogic.
Maintenant Chan, Le Jeu et Dlzlogic ont 3 résultats différents.

le mieux pour comprendre comment des choses ont été oubliées ou bien mises en trop est de comparer.
Donc Dlzlogic, j'espère que ton programme te permetra de compter les
1-1
1-2
...
1-8
sachant que pour le moment Chan et Le jeu sont à égalité sur ce décompte et que leur nombre Nt est très proche.

Il faut continuer avec les
2-1
2-2
...
2-8

Dès que divergence, alors on pourra mettre sur la table.

j'espère que Le Jeu n' a pas été découragé,
et j'espère que Dlzlzogic a encore de la gniaque.
Bon courage à tous.

[beagle]

Je n'ai pas vraiment compris la démonstration de 1952/8 impossible de Dlzlogic.

A mes yeux, si on a 1952/8 valable, c'est parce que l'on ne peut pas créer un similaire superposable par transformation, et la raison en est dans le nombre de degré de liberté pour faire 18.
Sur du 8x8 j'imagine qu'on peut trouver les degrés de liberté pour y arriver.

Maintenant, il y a encore la possibilité de quelques cas rares que l'on va découvrir.
Mais si Chan a vérifié comme il le dit ses 244 cas, alors il n' y pas de place pour de tels cas.

[chan79]

Mais si Chan a vérifié comme il le dit ses 244 cas, alors il n' y pas de place pour de tels cas.

J'en suis loin; c'est de plus en plus complexe
sinon pour 2-1 j'ai 22 (même si ça me paraît beaucoup)
et pour 2-2 j'ai 2

[Dlzlogic]

"Je n'ai pas vraiment compris la démonstration de 1952/8 impossible de Dlzlogic."
Je ne sais comment LeJeu et Chen ont trouvé 1952. Mais voila ma méthode.
Je prends mes 12 mots de base. Compte tenu des permutations, il y a 216 possibilités différentes.
Pour chaque ligne, c'est à dire quatre, j'essaye les 216 possibilités, soit 216^4 carrés possibles.
Pour chacun de ces carrés je vérifie les colonnes et les diagonales, et je trouve bien 1952 carrés possibles.
Si mes 12 mots de base n'avaient pas eu de paires, c'est à dire tous différents, je n'aurais pas et 216 possibilités, mais 288;
Le nombre de carrés possibles aurait donc été 288^4. J'aurais donc obtenus un certain nombre de carrés possibles, mais avec des doublon, puisque 1188 == 1188. J'aurais probablement obtenu 3392 carrés possibles. La vérification est faisable.

Pour le décompte des carrés uniques, je mets à jour, au fur et à mesure, la liste des carré uniques, compte tenu des symétries/rotations. Si le carre en cours n'existe pas je le rajoute à la liste.

Quand tout est fini, je fais une vérification : je prends chaque carré de la liste et je le compare à tout les autres.

[beagle]

Hum, y a pas plus simple en informatique?
Chaque carré des 1952, posséde une case d'angle la plus petite,
à coté de dette case d'angle la plus petite on prend le plus petit nombre,
chaque carré peut se ranger dans une case
1-7
ou

2-5

cette classification sur les 1952
permet de trouver des
20x8=160
ou
12x8= 96

déjà si dans une classification a-b vous avez un nombre qui n'est pas x8 c'est à regarder

et ensuite sinon vous vérifiez les 96 ou les 160 ou les 2x8=16,
pas sur la totalité.

[Dlzlogic]

Hum, y a pas plus simple en informatique?
Chaque carré des 1952, posséde une case d'angle la plus petite,
à coté de dette case d'angle la plus petite on prend le plus petit nombre,
chaque carré peut se ranger dans une case
1-7
ou

2-5

cette classification sur les 1952
permet de trouver des
20x8=160
ou
12x8= 96

déjà si dans une classification a-b vous avez un nombre qui n'est pas x8 c'est à regerder

et ensuite sinon vous vérifiez les 96 ou les 160
pas sur la totalité.

En informatique il y a une chose qu'on sait très bien faire, c'est "tout essayer".
Par contre, ça n'interdit pas d'essayer intelligemment.
Assurément le gros danger consiste à faire des hypothèses pour économie et d'oublier des trucs.
Mais, c'est assurément un problème suffisamment difficile pour qu'on soit plusieurs à trouver le même résultat avec des méthodes différentes.

[beagle]

J'y connais rien en programation mais tu lances une recherche,
j'imagine que les solutions trouvées sont numérotées,
enfin bref tu trouves une solution et tu lui joins
my first name is:
les nombres première rangée+seconde rangée+troisième rangée+ quatrième rangée
my second name is:
case d'angle inf + case adjacente inf:
les nombres de: case d'angle inf direction adjacent inf + case adjacente pas inf direction idem ...
if deux adjacents idem then go to next adjacent...

Bon, tu te débrouilles Dlzlogic, mais tu dois nous donner ton décompte orienté ...
Sans délaisser le chien!

[Dlzlogic]

C'est quoi le décompte orienté ?
Je sais que la somme des chiffres de la ligne fait 18.
A partir de là j'essaye tout, et je ne retiens que les carrés magic, que je décompte.
Puis je mets à jour la liste si le carré en cours est le premier du genre.
Ma recherche se fait avec un ordre parfaitement logique.
A mon avis, ta recherche par adjacence sera vite inextricable dès le second caractère, soit en ligne, soit en colonne, soit en diagonale.
Comment peux-tu vérifier que tel carré qu tu viens de créer n'existe pas déjà à une symétrie/rotation près ? Voir un exemple cité par Chen où on retrouvait un 1 en position (0,0).
A tout à l'heure.

[beagle]

"C'est quoi le décompte orienté ?"

ce que font Chan et Le Jeu,
tu comptes les
1-1
puis les 1-2
puis les 1-3


puis les
2-5

avant les
3-4,

...

[Doraki]

moi je trouve entre 8*278 = 2224 et 16*278 = 4448 carrés magiques (en utilisant deux fois chaque nombre entre 1 et 8, de sorte que chaque ligne, chaque colonne, et chaque diagonale fasse 18)

en plus des symétries axiales/rotations, je prends aussi la symétrie obteune en inversant les nombres (1<->8, 2<->7, 3<->6, 4<->5).

Et je classifierais plutot les carrés selon les trucs qu'on met aux 4 coins.
on prend
a..c
....
....
d..b

tels que a+b+c+d=18, a<=b, et a <= 9-b <= c <= d, ce qui brise toutes les symétries, puis on continue comme on veut (et on trouve 278 carrés)

Ensuite il y a sans doute des carrés qui sont invariants par certaines transformations du genre si on inverse les nombres et qu'on fait une symétrie axiale, on retombe sur le même carré de départ.
(il n'y a pas de carré invariant par symétrie, ni par rotation, ni par inversion, mais j'ai pas pensé aux mélanges)

[beagle]

Ce qui donne le classement actuel:
Chan:244
Le Jeu:265 , avant était à 283
doraki:278
Dlzlogic:424

[Doraki]

Je crois que j'ai 212 carrés dont inversion = symétrie axiale ; 24 dont inversion = symétrie centrale ; et 42 qui sont invariants par rien, donc 8*(212+24)+16*42 = 2560 carrés.

[beagle]

Saluons l'arrivée de Doraki,
avec déjà une excellente idée: les inversions 1 vers 8 , 8 vers 1,
mais pour le moment on ne va pas en tenir compte.

ton 278 est un calcul théorique ou un résultat expérimental?

[Doraki]

un résultat expérimental.

Et puis il y a aussi la transformation qui passe de

abcd
efgh
ijkl
mnop

à

fehg
badc
nmpo
jilk

Donc maintenant j'ai un groupe de transformations de taille 32 =|