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

[beagle]

Non, je me suis gourré.
ah, ces pouvoirs magiques,
il y aune petite faille.
adaptation possible?,
je sais pas, retour atelier!

[beagle]

Changement de baguette magique,
celle-ci ne marche pas mal non plus aux premiers essais,
mais je n'ose pas m'avancer,
donc j'ai bien 16 cas de 1-2 comme Le Jeu.
Et cela ne semble pas trop gourmand en ressources,

si ça marche!

pour preuve de ma bonne foi,
je balance les 16 carrés 1-2, si c'est bon

et on pourra continuer, enfin moi ...

[Dlzlogic]

Bonjour,
J'avance, mais je suis pas encore au bout.
Hier mon chien m'a fait la g..., parce qu'il n'a pas eu sa promenade.
Là, je suis en recherche de faute. La méthode est bonne, en tout cas, je pense.
Je teste toutes les combinaisons possibles, sans rechercher d'astuce.

[chan79]

Changement de baguette magique,
celle-ci ne marche pas mal non plus aux premiers essais,
mais je n'ose pas m'avancer,
donc j'ai bien 16 cas de 1-2 comme Le Jeu.
Et cela ne semble pas trop gourmand en ressources,

si ça marche!

pour preuve de ma bonne foi,
je balance les 16 carrés 1-2, si c'est bon

et on pourra continuer, enfin moi ...

OK pour 16 carrés commençant par 12(pas de sym rot)

[Dlzlogic]

Bon, j'ai franchi une étape importante Youpi !
Par contre, je n'en trouve pour l'instant que 1668.
Pour l'instant, je n'ai pas cherché à tenir compte des carrés semblables.
Deux hypothèses, soit j'en oublie (le plus probable) soit les lignes ou colonnes ou diagonales contenant 2 paires sont décomptées trop souvent dans les 1952 carrés.

[EDIT] Ok pour 1952.
Demain je fais la suite.

[beagle]

deuxième baguette magique semble plus au point,
j'ai 16 branches pour le 1-2 comme Chan et Le Jeu,
juste vérifié jusqu'au bout 8 des carrés mis par Chan.

Il doit ètre possible de vérifier les dénombrements que le Jeu a déjà mis,
et il peut mettre son décompte des 2-trucs.

[Dlzlogic]

Je décris ma méthode rapidement.
D'abord il y a 12 façons de faire 18.
8 façons avec 4 chiffres différents, et 4 façons avec 2 paires.
Il y a 24 façons de mettre 4 chiffres et 6 de mettre 2 paires.
Je travaille par lignes.
Pour chaque lignes, il y en a 4, j'essaye toutes les possibilités.
Pour chaque carré construit, je le compte s'il est bon.

[beagle]

Bon, j'ai franchi une étape importante Youpi !
[EDIT] Ok pour 1952.
Demain je fais la suite.

bravo, on attend la suite!
et parole de beagle, ne néglige pas le chien!

[chan79]

J'en ai profité pour compter mes soluces ( ce que Beagle me conseille depuis 2 jours !)
[FONT=Courier New]
1 1 -> 2
1 2 -> 16
1 3 -> 20
1 4 -> 25
1 5 -> 12
1 6 -> 19
1 7 -> 10
1 8 -> 2
========
1 -> 106[/FONT]

Hello
Pour 1 6 tu confirmes 19 ?

[LeJeu]

Hello
Pour 1 6 tu confirmes 19 ?

Comment il dit Beagle ?
Je retourne à l'atelier ?

[C.Ret]

Pour dénombre les symétries, j'avais déjà étudié cela lors de la mise au poitn d'un jeu de Morpion. Le système devait "reconnaitre" les grilles au fur et à mesure du jeu et "apprendre" à l'aide d'un arbre de décision les bon et mauvais coups.
Evidemment, l'arbre de décision était bien plus petit et l'aprrentisage se faisait d'autant mieux en tenant compte des symétries, rotations, etc.

En théorie des groupes, on apprend que les rotations dans le carré sont en fait obtenue par des composée de symétrie axiale (S = sigma). En particulier, la composé d'une symétrie axiale avec une symétrie diagonale.

Pour nos carré magique, il convient de tenir compte des quatres symétries axiales :
symétrie verivale, horisontale, diagonale et anti diagonale puisque qu'il n'y a aps de permutation possible des lignes ou colonnes (sinon les somme des diagonales sont cassées).


Les quatres symétries (vertical, horizontal, diagonale, anti-diagonale) pour le carré (ici carré 3x3, mais on arrive facilement au même diagramme et 4x4 ou nxn):

Code: Tout sélectionner

              a d g             
              b e h             
              c f i             
                ^               
                |               
                Sd               
                |                 
i f c         a b c         c b a
h e b  f e d
g d a         g h i         i h g
                |               
                Sh               
                |               
                V               
              g h i             
              d e f             
              a b c             


COmme dans l'arbre de décision du morpion, il n'y avait que 3 valeurs possibles dans chaque case des carrés, elles étaient codées 0,1,2 (respectivemtn case vide, joueur 1 ou 2).
Mon idée était de coder chaque jeu (carré) pour un polynôme (de base 3 pour le morpion) ce qui permettait de représenter chaque combinaison avec un nombre caractéristique.

Pour tenir compte des symétries, je ne retenais pour chaque grille que la grille symétrique (ou composée de plusieurs symétries) qui présentait le nombre caractéristique le plus faible.

Pour le carré, il n'y a que 8 grilles possibles. En effet, les composées multiples ont vite fait de redonner une grille identique. Ce qui fait que pour "coder" une grille, il suffisait de calculer les valeurs des huits polynômes suivant et de ne retenir que le plus petit :

Code: Tout sélectionner

 8 7 6 5 4 3 2 1 0  BASE (B)
           
 a b c d e f g h i  Idt
 a d g b e h c f i  Sd
 c b a f e d i h g  Sv
 c f i b e h a d g  Sh x Sa = Sv x Sd = Sd x Sh = SA x Sv
 g d a h e b i f c  Sa x Sh = Sd x Sv = Sh x Sd = Sv x Sa
 g h i d e f a b c  Sh
 i f c h e b g d a  Sa
 i h g f e d c b a  Sv  x Sh = Sh x Sv = Sd x Sa = Sa x Sd


Le nombre et la forme des grilles symétriques ne dépend pas du nimbre de case. On peux dont tout à fait utiliser le même principa pour les carrés 4x4 :

Code: Tout sélectionner

15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0   Base
                                 
a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p    Idt
a  e  i  m  b  f  j  n  c  g  k  o  d  h  l  p    Sd
d  c  b  a  h  g  f  e  l  k  j  i  p  o  n  m    Sv
d  h  l  p  c  g  k  o  b  f  j  n  a  e  i  m    Sh x Sa = Sv x Sd = Sd x Sh = SA x Sv
m  i  e  a  n  j  f  b  o  k  g  c  p  l  h  d    Sa x Sh = Sd x Sv = Sh x Sd = Sv x Sa
m  n  o  p  i  j  k  l  e  f  g  h  a  b  c  d    Sh
p  l  h  d  o  k  g  c  n  j  f  b  m  i  e  a    Sa
p  o  n  m  l  k  j  i  h  g  f  e  d  c  b  a    Sv  x Sh = Sh x Sv = Sd x Sa = Sa x Sd


Reste juste dans votre cas à bien choisir la base B pour être sûr de représenter de façon caractéristique et sans confusion l'ensemble des carrés possibles.

Si l'on fait un carré magique ayant toutes les valeurs de 1 à n², on peut utiliser une base B=n²+1
Mais, comme il ne sert à rien de "coder" des cases vides, on aura intérêt, pour limiter la taille des nombres utiliser une base B=n² en codant les valeur des case de 0 à n²-1.

Mais, cela risque fort de faire malgré tout de très grands nombres (numériquement). Par chance, il faut 4 bits par position, soit 64 bits par carrés en hexadécimal. Cela ^doit donc être possible en utilisant des entiers longs, voir même optimiser l'utilisation de sprocesseur 64 bits actuels ?

[fatal_error]

Reste juste dans votre cas à bien choisir la base B pour être sûr de représenter de façon caractéristique et sans confusion l'ensemble des carrés possibles.

slt C.ret
le probleme est legerement different pour les grilles avec deux fois les nombres de 1 a 8.

Le principe avec 1 a 16 consiste a prendre que la premiere grille et a dire: ok si on permute, on sait que le nombres de carre total c'est *8

Avec deux fois 1 a 8 on peut pas prendre la premiere et dire ok on permute et on multiplie par 8 parce que ya des cas ou ya deux perm differente qui donnent le meme carre (enfin je sais pas si on la demontre apres trois pages lol)

[C.Ret]

Oui, très juste, c'est pour cela qu'utiliser un "nombre caractéristique" pour chaque grille permettrait de facilement vérifer si elle est identique ou non avec une grille déjà découverte.

Comme les nombre vont uniquemetn de 1 à 8, on les "code de 0 à 7 et une base 8 pour le polynôme caractèristique est suffisante.

[Dlzlogic]

Oui, très juste, c'est pour cela qu'utiliser un "nombre caractéristique" pour chaque grille permettrait de facilement vérifer si elle est identique ou non avec une grille déjà découverte.

Comme les nombre vont uniquemetn de 1 à 8, on les "code de 0 à 7 et une base 8 pour le polynôme caractèristique est suffisante.

Bonjour,
Tout à fait d'accord sur le principe, mais je ne comprends pas s'il y a un autre intérêt que de diminuer l'occupation mémoire.
Il est bien évident que dans une application réelle et utile ce serait bon de faire des économies, mais dans le cas présent, je ne me casse pas la tête.
D'ailleurs, j'aborde le problème par l'autre bout, je teste toutes les possibilités.

[beagle]

Message pour Chan,
tu conteste le 19 nombres de 1-6 de Le Jeu,
donc j'ai cherché ces 1-6

Si on me demande de dénombrer les 1-6, j'en trouve 18.
(et cela ferait 18x8 dans Ns)
Mais seuls 12 appartiennent à Nt, car une famille entière de 6 éléments
est déjà comptabilisée dans les 1-4 et 1-3,
il s'écrivent:
16..
4...
....
....

C'est bon ou bien il me manque un groupe Chan?

PS: cela me fait penser que j'ai oublié de vérifier que le 1 ne se retrouvait pas dans un autre angle, avec du 1-inf à 6.je vais regarder quand j'aurai le temps.

[beagle]

Je n'ai pas fait que regarder les branches,
je suis allé jusqu'aux fruits,
ce qui fait deux branches en moins, pourries,

donc en nombre de 1-6 je passe à seulement 10 maintenant.
Chan?

[Dlzlogic]

Bonsoir,
Juste pour vous tenir informés.
Ns trouvé=1952 Nt=424
Les types 184 184 268 268 220 184 220
Je compte les carrés déjà existants sous une autre disposition, et je décompte le type de transformation.
Type 1 : symétrie à axe vertical
Type 2 : symétrie à axe horizontale
Type 3 : symétrie axe 1ere bissectrice
Type 4 : symétrie axe 2ème bissectrice
Type 5 : rotation 90°
Type 6 : rotation 180°
Type 7 : rotation 270°

Il y a 180 carré de trop par rapport aux 244 calculés par ailleurs.
Je n'ai actuellement aucune idée de la raison.
Les lignes où colonnes avec 2 paires posent un peu de problème.
En fait il est possible que ce soient celles-là qui font croire à ma machine que les carrés sont différents.
Suite demain.

[chan79]

Message pour Chan,
tu conteste le 19 nombres de 1-6 de Le Jeu,
donc j'ai cherché ces 1-6

Si on me demande de dénombrer les 1-6, j'en trouve 18.
(et cela ferait 18x8 dans Ns)
Mais seuls 12 appartiennent à Nt, car une famille entière de 6 éléments
est déjà comptabilisée dans les 1-4 et 1-3,
il s'écrivent:
16..
4...
....
....

C'est bon ou bien il me manque un groupe Chan?

PS: cela me fait penser que j'ai oublié de vérifier que le 1 ne se retrouvait pas dans un autre angle, avec du 1-inf à 6.je vais regarder quand j'aurai le temps.

salut à tous
je ne conteste pas le 19 pour 1-6 finalement
je suis en train de faire la répartition des 244 (?) en fonction des deux premiers; dès que c'est fini, je mets le tableau

[chan79]

Pour dénombre les symétries, j'avais déjà étudié cela lors de la mise au poitn d'un jeu de Morpion. Le système devait "reconnaitre" les grilles au fur et à mesure du jeu et "apprendre" à l'aide d'un arbre de décision les bon et mauvais coups.
Evidemment, l'arbre de décision était bien plus petit et l'aprrentisage se faisait d'autant mieux en tenant compte des symétries, rotations, etc.

En théorie des groupes, on apprend que les rotations dans le carré sont en fait obtenue par des composée de symétrie axiale (S = sigma). En particulier, la composé d'une symétrie axiale avec une symétrie diagonale.

Pour nos carré magique, il convient de tenir compte des quatres symétries axiales :
symétrie verivale, horisontale, diagonale et anti diagonale puisque qu'il n'y a aps de permutation possible des lignes ou colonnes (sinon les somme des diagonales sont cassées).


Les quatres symétries (vertical, horizontal, diagonale, anti-diagonale) pour le carré (ici carré 3x3, mais on arrive facilement au même diagramme et 4x4 ou nxn):

Code: Tout sélectionner

              a d g             
              b e h             
              c f i             
                ^               
                |               
                Sd               
                |                 
i f c         a b c         c b a
h e b  f e d
g d a         g h i         i h g
                |               
                Sh               
                |               
                V               
              g h i             
              d e f             
              a b c             


COmme dans l'arbre de décision du morpion, il n'y avait que 3 valeurs possibles dans chaque case des carrés, elles étaient codées 0,1,2 (respectivemtn case vide, joueur 1 ou 2).
Mon idée était de coder chaque jeu (carré) pour un polynôme (de base 3 pour le morpion) ce qui permettait de représenter chaque combinaison avec un nombre caractéristique.

Pour tenir compte des symétries, je ne retenais pour chaque grille que la grille symétrique (ou composée de plusieurs symétries) qui présentait le nombre caractéristique le plus faible.

Pour le carré, il n'y a que 8 grilles possibles. En effet, les composées multiples ont vite fait de redonner une grille identique. Ce qui fait que pour "coder" une grille, il suffisait de calculer les valeurs des huits polynômes suivant et de ne retenir que le plus petit :

Code: Tout sélectionner

 8 7 6 5 4 3 2 1 0  BASE (B)
           
 a b c d e f g h i  Idt
 a d g b e h c f i  Sd
 c b a f e d i h g  Sv
 c f i b e h a d g  Sh x Sa = Sv x Sd = Sd x Sh = SA x Sv
 g d a h e b i f c  Sa x Sh = Sd x Sv = Sh x Sd = Sv x Sa
 g h i d e f a b c  Sh
 i f c h e b g d a  Sa
 i h g f e d c b a  Sv  x Sh = Sh x Sv = Sd x Sa = Sa x Sd


Le nombre et la forme des grilles symétriques ne dépend pas du nimbre de case. On peux dont tout à fait utiliser le même principa pour les carrés 4x4 :

Code: Tout sélectionner

15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0   Base
                                 
a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p    Idt
a  e  i  m  b  f  j  n  c  g  k  o  d  h  l  p    Sd
d  c  b  a  h  g  f  e  l  k  j  i  p  o  n  m    Sv
d  h  l  p  c  g  k  o  b  f  j  n  a  e  i  m    Sh x Sa = Sv x Sd = Sd x Sh = SA x Sv
m  i  e  a  n  j  f  b  o  k  g  c  p  l  h  d    Sa x Sh = Sd x Sv = Sh x Sd = Sv x Sa
m  n  o  p  i  j  k  l  e  f  g  h  a  b  c  d    Sh
p  l  h  d  o  k  g  c  n  j  f  b  m  i  e  a    Sa
p  o  n  m  l  k  j  i  h  g  f  e  d  c  b  a    Sv  x Sh = Sh x Sv = Sd x Sa = Sa x Sd


Reste juste dans votre cas à bien choisir la base B pour être sûr de représenter de façon caractéristique et sans confusion l'ensemble des carrés possibles.

Si l'on fait un carré magique ayant toutes les valeurs de 1 à n², on peut utiliser une base B=n²+1
Mais, comme il ne sert à rien de "coder" des cases vides, on aura intérêt, pour limiter la taille des nombres utiliser une base B=n² en codant les valeur des case de 0 à n²-1.

Mais, cela risque fort de faire malgré tout de très grands nombres (numériquement). Par chance, il faut 4 bits par position, soit 64 bits par carrés en hexadécimal. Cela ^doit donc être possible en utilisant des entiers longs, voir même optimiser l'utilisation de sprocesseur 64 bits actuels ?

Merci pour tout ça
Dès que la répartion des 244 est finie, j'y regarde de près

[beagle]

salut à tous
je ne conteste pas le 19 pour 1-6 finalement
je suis en train de faire la répartition des 244 (?) en fonction des deux premiers; dès que c'est fini, je mets le tableau

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?