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

[beagle]

Salut
J'ai dû arrêter un peu mon vieux PC, il commençait à fumer à force de faire des tests.
Il s'agit des carrés magiques 4*4 avec 2 fois chaque nombre de 1 à 8 (somme 18).
Parmi les 1952 solutions, je n'en ai pas trouvé une qui soit invariante par rotation ou par symétrie, ce qui semble légitimer la division par 8. Mais je reste sceptique ...
J'ai testé leur invariance par les symétries axiales du carré (4) les rotations de 90°(2) et la symétrie centrale(1).

Hum, pour le moment c'est surprenant, mais les configurations symétriques ne permettent pas d'avoir aussi les diagonales qui fonctionnent, on perd en degré de liberté à chaque fois.C'est marrant.
Je l'ai démontré pour certains cas, et j'ai juste essayé sur des exemples pour les autres symétries,...

Alors la balle est dans le camp de Le Jeu.
Et je repropose de compter avec 1 première case, combien chacun?
etc...

[beagle]

Lorsque tu poses les conditions avec des lettres.
Tu as soit a,b,c,d et leurs complémentaires à 9, 9-a,9-b,9-c,9-d
soit abcdef et les complémentaires à 9 , 9-a,9-d

Et les conditions sont telles que à chaque fois tu nécessites d'avoir une lettre qui doit ètre finalement un des complémentaires.Impossible cela ferait 4 fois le mème nombre!

Donc pas testé toutes les symétries mais j'imagine bien que c'est pour toutes pareils,
et donc que la division par 8 soit légitime comme le trouve Chan.

Le Jeu qui part se promener le dimanche sans avoir terminé ses devoirs!
Reviens ici!

[LeJeu]

Le Jeu qui part se promener le dimanche sans avoir terminé ses devoirs!
Reviens ici!

Salut !

Grosse sortie sport ce matin de 4h ( orientation) ... plus trajet +sieste +embouteillage
Me voila

Mais j'ai vu des carrés partout en courant - Je tente de trouver un carré qui a une transformé égal par rotation et par symétrie , de tête j'ai pas trouvé

[LeJeu]

Mais j'ai vu des carrés partout en courant - Je tente de trouver un carré qui a une transformé égal par rotation et par symétrie , de tête j'ai pas trouvé

J'ai fait un essai avec mon programme en supprimant le test " anti rotation" et bizarrement ca ne donne pas 4 fois plus de solutions ...
J'ai retiré le test anti symétrie et bizarrement ça ne multiplie pas par deux !

ce n'est donc pas une interférence entre rotation /symétrie

J'ai une idée que je cours coder de ce pas ... je vous tiens au courant

Ps - Sinon Mon Pc qui contrairement à celui de Chan79 est refroidi convenablement , continue son carré de 5 - On en est à 28 300 000 solutions et on décompte actuellement les solutions commençant par 1 18
Et donc si on vous demande combien de carrés magiques ont un 1 dans un coin la réponse est donc supérieure à 28 millions !!!

[beagle] Imagine que Chan79 ne soit pas d'accord ... tu fais la réconciliation des solutions ?

[beagle]

"[beagle] Imagine que Chan79 ne soit pas d'accord ... tu fais la réconciliation des solutions ? :-)"

Montrez-moi ces carrés un par un bon sang!

PS: Chan, t'es OK pour les carrés de 5x5 à remplir avec deux fois les nombres de 1 à 10 et une fois les nombres de 1 à 5?

[LeJeu]

PS: Chan, t'es OK pour les carrés de 5x5 à remplir avec deux fois les nombres de 1 à 10 et une fois les nombres de 1 à 5?

Moi je dis que c'est tentant.... une fois le carré de 4 maîtrisé ( cad convenablement métrisé ..)

[LeJeu]

Moi je dis que c'est tentant.... une fois le carré de 4 maîtrisé ( cad convenablement métrisé ..)

J'ai arrêté l'ordi, et j'ai commencé à réfléchir je pense que j'ai trouvé pourquoi la division par 8 n'est pas légitime - Je vous en cause ce soir

[fatal_error]

juste pour l'escargot que je suis...
vous listez en combien de temps les solutions du 4x4 avec les nombres de 1 a 16 utilise une et une seule fois?
(parce que je mets au moins plus d'une minute(comprendre j'ai pas attendu jusqu'a la fin, jai kille le programme))

[chan79]

J'ai arrêté l'ordi, et j'ai commencé à réfléchir je pense que j'ai trouvé pourquoi la division par 8 n'est pas légitime - Je vous en cause ce soir

Attendons ...
C'est vrai que cette division par 8 me laisse comme la fosse ...*
*sceptique :triste: pas drôle

[beagle]

J'ai arrêté l'ordi, et j'ai commencé à réfléchir je pense que j'ai trouvé pourquoi la division par 8 n'est pas légitime - Je vous en cause ce soir

division par 8 non légitime, parce que des fois:
-c'est moins de 8
-c'est plus que 8

Plus que 8 j'ai pas essayé, mais alors Le Jeu devrait avoir encore moins de cas que Chan, j'imagine, non?

Moins que 8, cela signifie qu'une des transformations connues se transforme en un identique.
J'ai démontré avec des lettres l'impossibilité , mais pas fait tous les cas non plus.
Et en rebossant la structure, ces carrés sont formés en vectoriel par 3 directions (ou 4),
or les rotations à 90 changent les axes
et les renversements nécessitent une symétrie axiale pour rester invariants, symétrie axiale impossible à trouver sur 3 directions.
De plus Chan dit avoir vérifier ce point.

J'attends donc avec impatience la réponse de Le Jeu ce soir!

[beagle]

Le carré que j'avais mis en haut de deuxième page de ce fil,
le:
1278
3456
6543
8721
donne une transformation qui retourne au carré intial.

mais il n'avait pas les diagonales de correct.
or quelle est la structure de ce carré, sur le plan vectoriel il n'utilise que deux axes.
or a priori avec deux axes on ne construit pas de carrés avec rangées colonnes et les deux diagos.
Mis a part le cas que Le jeu va nous sortir ce soir?

Je reste très curieux.

[beagle]

attention, il y a beaucoup de faux encore dans ce que j'ai dit,
j'étais (trop) en forme hier, ce matin je suis un peu à la peine.
et je dois décrocher un peu pour la vraie vie.

je regarde là où j'ai raconté des bétises et pourquoi,
ou alors j'efface tout, si c'est irrécupérable.

[beagle]

Entre les faux souvenirs, le problème qui diverge pour 1 à n^2 et avec deux fois les mèmes nombres, ce qui autorise des répétitions non autorisées auparavant,
je n'en ai pas pris toute la mesure,...

ce qui est faux, c'est que l'on peut construire un carré avec les diagonales et en utilisant uniquement deux directions.Il n' y a pas nécessité de 3 directions comme je l'ai dit par erreur.
exemple:
5238
7416
2583
4761
est juste dérivé de l'exemple précédent, il en est très proche, avec deux directions.
il n'est pas par contre identique à une de ses transformations.
et les cas beaucoup moins nombreux que 3 ou 4 directions laissent peu d'espoir de trouver un tel cas.

Ce que j'ai dit sur les directions et la possibilité d'identique par transformation,
nécessite plus de subtilité, j'y réfléchis .
Mais je ne vais pas chercher des heures un truc jugé impossible.
Je vais attendre Le Jeu, pour dire oui bien sur ...

[LeJeu]

juste pour l'escargot que je suis...
vous listez en combien de temps les solutions du 4x4 avec les nombres de 1 a 16 utilise une et une seule fois?
(parce que je mets au moins plus d'une minute(comprendre j'ai pas attendu jusqu'a la fin, jai kille le programme))

Salut fatal_error !
Je savais que tu te laisserai tenter par le bidule.

Mon algo donne le nombre le nombre de solutions distinctes en moins de 1s (certainement beaucoup moins) - et en 1 seconde en affichant les solutions trouvées

A priori pour avoir la liste des solutions différentes, si tu n'a pas changé de style, tu as calculé toutes les soluces et éliminer ensuite les doublons ? ce qui doit être cher...

Chan79 divise par 8 ce qui va plus vite , mais ne donne pas la liste !

[fatal_error]

ben j'ai un peu fait n'importe quoi en fait...j'expérimente le metaprogramming en c++ pour l'imbrication des boucles for, mais comme j'apprends sur le tas, j'ai pas trop de visibilité sur ce que je fais :ptdr:

Sinon, j'ai une petite idée d'optimisation...on verra bien si elle gère

[beagle]

"Mon algo donne le nombre le nombre de solutions distinctes en moins de 1s (certainement beaucoup moins) - et en 1 seconde en affichant les solutions trouvées"

à comparer aux trois jours d'incertitudes sur le nombre et le pourquoi.

[chan79]

Salut fatal_error !
Je savais que tu te laisserai tenter par le bidule.

Mon algo donne le nombre le nombre de solutions distinctes en moins de 1s (certainement beaucoup moins) - et en 1 seconde en affichant les solutions trouvées

A priori pour avoir la liste des solutions différentes, si tu n'a pas changé de style, tu as calculé toutes les soluces et éliminer ensuite les doublons ? ce qui doit être cher...

Chan79 divise par 8 ce qui va plus vite , mais ne donne pas la liste !

Salut
Alors, finalement, c'est 1952 /8 ou pas ?
S'il y a une erreur, je n'arrive pas à la trouver...

[LeJeu]

J'ai arrêté l'ordi, et j'ai commencé à réfléchir je pense que j'ai trouvé pourquoi la division par 8 n'est pas légitime - Je vous en cause ce soir

Résumé des épisodes précédents :
Avec Chan79 nous cherchons le nombre carrés magique d'ordre 4 :pas de soucis nous arrivons tous les deux à 880
Mais, et c'est important pour la suite, pour éliminer les doublons:
- Chan79 divise par 8 son nb de solutions ( 4 rotation et une symétrie / diagonale)
- je filtre les réponses à la volée
. en jetant les soluces dont un coin est inférieur au coin en haut à gauche ( anti - rotation)
. en jetant les soluces de type si y 499 712 carrés
En divisant par 2^16 on trouve bien le 1952 annoncé par Chan79 -> on parle bien de la même chose

Ensuite j'ai rajouté mon test "anti-symétrie"
=> 268 288 : oh zut ca ne fait pas la moitié .... je fais pas le fier
=> ce sont les carré de type que j'ai laissé passé: 36 864 cas quand même
Je suis en nage ....
Il semble donc que je compte trop de solutions ?

Mais, n'oublions pas que chan79 & moi avons mis en place un test anti doublon dû aux chiffres identiques; pour cela on distingue 2 chiffres de la même valeur, c'est ce j'expliquais hier avec le 1 bleu et le un rouge , on ne pose le rouge que si on on a posé le bleu
Et avec ce filtre on ne peut plus construire deux fois !!!

Donc Chan79 en divisant par 8 retire trop de solutions ! toutes les 1952 solutions n'ont pas de symétriques !!!

[chan79]

Résumé des épisodes précédents :
Avec Chan79 nous cherchons le nombre carrés magique d'ordre 4 :pas de soucis nous arrivons tous les deux à 880
Mais, et c'est important pour la suite, pour éliminer les doublons:
- Chan79 divise par 8 son nb de solutions ( 4 rotation et une symétrie / diagonale)
- je filtre les réponses à la volée
. en jetant les soluces dont un coin est inférieur au coin en haut à gauche ( anti - rotation)
. en jetant les soluces de type si y 499 712 carrés
En divisant par 2^16 on trouve bien le 1952 annoncé par Chan79 -> on parle bien de la même chose

Ensuite j'ai rajouté mon test "anti-symétrie"
=> 268 288 : oh zut ca ne fait pas la moitié .... je fais pas le fier
=> ce sont les carré de type que j'ai laissé passé: 36 864 cas quand même
Je suis en nage ....
Il semble donc que je compte trop de solutions ?

Mais, n'oublions pas que chan79 & moi avons mis en place un test anti doublon dû aux chiffres identiques; pour cela on distingue 2 chiffres de la même valeur, c'est ce j'expliquais hier avec le 1 bleu et le un rouge , on ne pose le rouge que si on on a posé le bleu
Et avec ce filtre on ne peut plus construire deux fois !!!

Donc Chan79 en divisant par 8 retire trop de solutions ! toutes les 1952 solutions n'ont pas de symétriques !!!

Merci, je vais me pencher là-dessus
Est-ce que tu en as un sous la main (parmi les 1952) à partir duquel on n'en a pas 7 autres par symétrie-rotation ?

[LeJeu]

Donc Chan79 en divisant par 8 retire trop de solutions ! toutes les 1952 solutions n'ont pas de symétriques !!!

Un petit exemple en dim 2 !

On considère tous les carrés remplis avec les chiffres {1,2,3,4}, et que tous les carré sont magiques!

on dénombre : 4*3*2*1 = 24 solutions
et fort du théorème de Chan79 on divise par 8 pour retirer les rotations et symétrie ;just perfect on a trois carrés distincts :
et et

Passons au cas qui nous intéresse : on utilise maintenant les chiffres {1,2}, on fait donc tous les cas en distinguant xb et xr, on remplit ligne par ligne , en déposant les bleu en 1°

et et et et et

on sent que la division par 8 va être compliquée....

Car à la fin il ne reste que
et