|
Un carré magique est un carré rempli par des entiers
consécutifs à partir de 1, sans répétition et placés de telle sorte que
la somme des éléments d'une ligne soit la même pour chaque ligne
mais aussi que la somme des éléments chaque colonne soit la même,
et que de plus la somme des éléments de chaque diagonale soit cette même
somme.
On voit à droite un carré magique d'ordre 3, avec sa somme magique 15 et un carré magique d'ordre 4 avec sa somme magique 34.
Appelons n l'ordre du carré et remarquons que dès que toutes les
lignes ont la même somme, notée s , alors la somme de tous les
éléments du carré est n*s . On appelle somme magique
cette valeur, qui ne dépend pas de n.
|
carré d'ordre 3
8 1 6 : 15
3 5 7 : 15
4 9 2 : 15
.. .. ..
15 15 15
carré d'ordre 4
1 15 14 4 : 34
12 6 7 9 : 34
8 10 11 5 : 34
13 3 2 16 : 34
.. .. .. ..
34 34 34 34
|
♦ On choisit l'ordre, puis un carré magique est affiché en
appuyant sur bouton .
|
On remplit le carré par les entiers successifs de 1 à
n2 de façon particulière: on suit les "pseudo-diagonales
ascendantes", en observant les règles:
→ partir du milieu de la première ligne
→ quand on déborde vers le haut, continuer sur la dernière
ligne
→ quand on déborde vers la droite haut, continuer sur la
première colonne
→ quand une diagonale est remplie, commencer une autre
diagonale, par la case immédiatement en dessous
(voir signe + sur le schéma ci-dessous)
En bref, l'augmentation ou la diminution d'indice se font en
calculant modulo n.
| de 1 à 5 | de 6 à 10 | de 11 à 10 | de 16 à 20 | de 21 à 25 | Au complet |
|---|---|---|---|---|---|
- - 1 - - - 5 - - - 4 + - - - - - - - 3 - - - 2 - |
- - - 8 - - - 7 - - - 6 - - - 10 - - - - + - - - 9 |
- - - -15 - - -14 + - -13 - - -12 - - - 11 - - - - |
17 - - - - - - - -16 - - -20 - - -19 + - -18 - - - |
-24 - - - 23 - - - - - - - -22 - - -21 + - -25 - - |
17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9 |
On remplit plusieurs carré successifs, pour assurer l'égalité des sommes
en lignes, colonnes et diagonales, et assurer également que les nombres
placées dans le dernier soient deux à deux distincts.
On présente la construction d'un carré contenant les entiers de 0 à
n2-1 .
→
Pour le premier carré, noté A sur l'exemple ci-dessous, mettre
les nombres de 0 à n-1 sur la première ligne, dans un ordre quelconque;
puis remplir les lignes suivantes en décalant les éléments d'une ligne
de deux positions par rapport à la ligne immédiatement au-dessus.
→
Remplir B à partir de A en multipliant chacun de ses éléments
par n .
→
Déduire C de B par une symétrie sur les colonnes, par rapport à
la colonne centrale.
→
En faisant tout simplement la somme, éléments par
élements des carrés A et C , on obtient D qui
est magique (la somme magique est 60 sur l'exemple.
| A | B = 5*A |
C
déduit de B |
D = A + C est magique |
|---|---|---|---|
2 4 1 3 0 1 3 0 2 4 0 2 4 1 3 4 1 3 0 2 3 0 2 4 1 |
10 20 5 15 0 5 15 0 10 20 0 10 20 5 15 20 5 15 0 10 15 0 10 20 5 |
0 15 5 20 10 20 10 0 15 5 15 5 20 10 0 10 0 15 5 20 5 20 10 0 15 |
2 19 6 23 10 21 13 0 17 9 15 7 24 11 3 14 1 18 5 22 8 20 12 4 16 |
Remarques
♦
On voit facilement que les lignes et colonnes de A contiennent les
entiers consécutifs de 0 à n-1; donc les sommes de ces lignes ou colonnes
sont identiques, et valent la somme magique.
♦
Le décalage de 2 d'une ligne à la suivant assurre que la diagonale
descendante de A contient aussi ces mêmes entiers.
♦
Les éléments de la diagonale ascendante ne sont pas forcément
deux à deux distincts, mais en plaçant sur la première ligne n/2
puis les entiers obtenus en ajoutant 2 (modulo n), on est assuré
que la somme des éléments sur la diagonale montante est la somme magique.
♦
Puisque toutes les sommes (lignes colonnes et diagonales)
sont identiques pour A, elles le sont aussi pour les carrés B,
C et D . Elles le seraient également pour le carré
calculé comme somme de A et B .
♦
La présence dans D des entiers consécutifs de n2-1
, donc aussi l'unicité des éléments, est obtenu grâce à la symétrie
effectuée entre B et C.
|
Elle ressemble à la première méthode qui place les entiers consécutifs
sur des pseudo-diagonales. Cependant cette fois on commence au dessus du
milieu du carré (voir ci-contre la position de 1), et quand une
pseudo-diagonale est remplie (voir passage de 5 à 6), on commence la
suivante deux cases au-dessus.
|
23 6 19 2 15
10 18 1 14 22
17 5 13 21 9
4 12 25 8 16
11 24 7 20 3
|
On commence par placer régulièrement les entiers de 1 à n2 (64) sur les lignes, en plaçant les entiers de 1 à n sur la première ligne, ainsi de suite. On constate alors (un peu d'arithmétique le démontre) que la somme des éléments portés par chaque diagonale est la somme magique.
Comme l'ordre est multiple de 4, il est possible d'arriver simplement à
obtenir les égalités des sommes d'éléments, par ligne ou colonne,
sans jamais toucher aux éléments sur les diagonales.
On commence par effectuer une première série d'échanges pour assurer
l'égalité des sommes des éléments de chaque ligne. Puis on effectue
une deuxième série d'échanges pour obtenir les égalités des
sommes par colonne, tout en conservant la propriété sur les
diagonales et sur les lignes.
Voyons cette méthode en 3 étapes, pour un carré d'ordre 8.
|
Après avoir placé les nombres de 1 à 64, le calcul des sommes par ligne
(résultat écrit à droite) permet de voir que certaines lignes ont
un déficit par rapport à la somme magique et qu'il existe une ligne
présentant un excédent égal à ce déficit. Ainsi la ligne 2 a un
déficit de 160, alors que la ligne 7 a un excédent de 160.
|
: somme 1 2 3 4 5 6 7 8 : 36=260-224 9 10 11 12 13 14 15 16 : 100=260-160 17 18 19 20 21 22 23 24 : 164=260- 96 25 26 27 28 29 30 31 32 : 224=260- 32 33 34 35 36 37 38 39 40 : 292=260+ 32 41 42 43 44 45 46 47 48 : 356=260+ 96 49 50 51 52 53 54 55 56 : 420=260+160 57 58 59 60 61 62 63 64 : 484=260+224 |
Pour obtenir les égalités de somme par ligne, on échange des éléments
(situés même colonne) entre les lignes symétriques (1 et 8; 2 et 7; 3
et 6; 4 et 5), sans jamais toucher aux éléments placés sur les
diagonales.
Une possibilité avec le carré ci-dessus (voir les nombres écrits en
gras), est d'échanger 4 éléments par ligne:
|
Sur le carré obtenu après ces échanges, on a calculé ci-contre les
sommes par colonnes et l'écart de la somme obtenue par rapport à la
somme magique est affiché sur la ligne en dessous.
|
1 58 59 4 5 62 63 8 : 260 9 10 51 52 53 54 15 16 : 260 41 18 19 44 45 22 23 48 : 260 33 34 27 28 29 30 39 40 : 260 25 26 35 36 37 38 31 32 : 260 17 42 43 20 21 46 47 24 : 260 49 50 11 12 13 14 55 56 : 260 57 2 3 60 61 6 7 64 : 260 .. .. .. .. .. .. .. .. 232 240 248 256 264 272 280 288 -28 -20 -12 -4 +4 +12 +20 +28 |
Pour obtenir les sommes par colonnes identiques, on va donc faire des échanges entre les colonnes symétriques (1 et 8; 2 et 7; 3 et 6; 4 et 5), sans jamais toucher aux éléments placés sur les diagonales; le choix de nombres placés la même ligne, conserve la somme de la ligne.
|
L'égalité des sommes par colonne est acquise en échangeant 4
éléments par colonne.
On a indiqué en gras et souligné, sur le carré ci-dessus à droite, les
nombres qui changent de place (échanges entre colonne 1 et 8, ou 2 et 6
...) pour obtenir le carré ci-contre.
|
Un carré magique d'ordre 8
1 58 62 5 4 59 63 8
9 10 54 53 52 51 15 16
48 23 19 44 45 22 18 41
40 39 27 28 29 30 34 33
32 31 35 36 37 38 26 25
24 47 43 20 21 46 42 17
49 50 14 13 12 11 55 56
57 2 6 61 60 3 7 64
|
La méthode ci-dessous permet de construire un carré magique d'ordre n (n pair) à partir d'un carré magique d'ordre moitié n/2. Comme il n'existe pas de carré magique d'ordre 2, la méthode n'est pas appliquable pour n=4. Par contre dès que n est au moins égal à 6, elle est valide.
Dans les exemples ci-desssous, on a placé les entiers de 0 à n2-1; cela simplifie légèrement la présentation, sans changer la construction. On note p=n/2.
♦ On va placer les entiers de 0 à n2-1, ou de 1 à 4p2-1 en respectant les les contraintes:|
La première idée est de considérer, dans un carré d'ordre n,
les quatre sous-carrés d'ordre p=n/2 notés A, B, C, D ci-contre; un
exemple de carré 6x6 montre les 4 sous-carrés 3x3 (n=6, p=3).
|
+++++ +++++
+ A + + B +
+++++ +++++
+++++ +++++
+ C + + D +
+++++ +++++
|
M | 34 0 5 25 18 23 | 2 31 6 20 22 24 | 30 8 1 21 26 19 | | 3 35 28 12 17 10 | 29 4 33 11 13 15 | 7 27 32 16 9 14 |
|
Si on décompose chaque nombre en la somme d'un multiple de
p2 et d'un reste, et qu'on éclate chaque partie dans un
carré respectif, on obtient les deux carrés ci-contre en bleu, dont la
somme est le carré en vert, à droite ci-dessus.
|
M1
27 0 0 18 18 18
0 27 0 18 18 18
27 0 0 18 18 18
0 27 27 9 9 9
27 0 27 9 9 9
0 27 27 9 9 9
|
M2
| 7 0 5 7 0 5
| 2 4 6 2 4 6
| 3 8 1 21 8 1
|
| 3 8 1 3 8 1
| 2 4 6 2 4 6
| 7 0 5 7 0 5
|
Si on note u le nombre de fois où 3p2 intervient dans chaque ligne de A1, et v le nombre de fois où 2p2 intervient dans chaque ligne de B1, alors on aura égalité des sommes par lignes et par colonnes de M1 dès que:
Si on note d le nombre de fois où 3p2 intervient dans la diagonale descendante de A1, et e le nombre de fois où 2p2 intervient dans la diagonale descendane de D1 alors la somme des diagonales de M1 vaut aussi 3p3, dès que:
Une fois obtenu A1 contenant u fois 3p2 par ligne et d fois 3p2 sur la diagonale descendante, on obtient C1 immédiatement. On obtient obtient D1 à partir de B1 de la même façon.
Remarque:
Si SM(p) est la somme magique du carré magique contenant les
entiers de 0 à p2-1, alors
final static int c8[][]={{1,63,3,61,12,54,10,56}
,{16,50,14,52,5,59,7,57}
,{17,47,19,45,28,38,26,40}
,{32,34,30,36,21,43,23,41}
,{53,11,55,9,64,2,62,4}
,{60,6,58,8,49,15,51,13}
,{37,27,39,25,48,18,46,20}
,{44,22,42,24,33,31,35,29}};
final static int[][] c4 = {{ 1,15,14, 4}
,{12, 6, 7, 9}
,{ 8,10,11, 5}
,{13, 3, 2,16}};
static int [][] c(int n){
if(n%2==1) return cImpair2(n);
else return cPair(n);
}
static int [][] cImpair(int n) {
int c[][]=new int [n][n];
int i,j,k,m,v;
i=1; j=n/2-1;
for(v=0, m=0; m<n; m++) {
for(k=0; k<n; k++) {
// -1 en ligne, +1 en colonne
i=(i==0)?n-1:i-1;
j=(j==n-1)?0:j+1;
c[i][j]=++v;
}
// Avant la collision
i+=2; if(i>=n) i=i-n;
j=(j==0)?n-1:j-1;
}
return c;
}
static int [][] cImpair2(int n) {
int c[][]=new int[n][n], a[][]=new int[n][n];
int i,j,jj,k;
// Premiere ligne du carré initial: mettre n/2 sur la première case et
// ajouter 2 pour passer à chaque case suivante.
for(i=0, k=n/2; i<n; i++, k=(k<n-2)?k+2:k+2-n) a[0][i]=k;
// Décalage de 2 entre une ligne et la précédente
for(i=1; i<n; i++) {
for(k=0; k<n; k++) {
j=(k<n-2)?k+2:k+2-n;
a[i][k]=a[i-1][j];
}
}
// Carré magique
for(i=0; i<n; i++)
for(k=n-1, j=0; j<n; j++, k--) c[i][j]=1+a[i][j]+n*a[i][k];
return c;
}
static int [][] cImpair3(int n) {
int c[][]=new int [n][n];
int i,j,k,v;
int j0=n/2, i0=1+j0;
c[i0][j0]=1;
for(v=1, i=i0-1, j=j0-1; v<=n*n; ) {
for(k=0; k<n; k++, v++) {
i=(i==n-1)?0:i+1;
j=(j==n-1)?0:j+1;
c[i][j]=v;
}
// A la collision
i=i+1; if(i>=n) i=i-n;
j=j-1; if(j<0) j=n-1;
}
return c;
}
static int [][] cPair4n(int n) {
int c[][] = new int[n][n], nn=n/2,p=n/4;
int i,ii,j,jj,k, aux;
// Les entiers consécutifs
for(i=0,k=1; i<n; i++) for(j=0; j<n; j++,k++) c[i][j]=k;
// Assurer égalité des sommes par ligne: p valeurs à échanger
for(i=0,ii=n-1-i; i<nn; i++,ii--)
for(k=0,j=nn-1, jj=nn; k<p; k++,j--,jj++) {
if(i==j) {j--; j++;} // Ne pas modifier la diagonale
aux =c[i][j]; c[i][j]=c[ii][j]; c[ii][j]=aux;
aux=c[i][jj]; c[i][jj]=c[ii][jj]; c[ii][jj]=aux;
}
// Assurer égalité des sommes par colonnes: p valeurs à échanger
for(j=0,jj=n-1-j; j<nn; j++,jj--)
for(k=0,i=0, ii=n-1; k<p; k++,i++,ii--) {
if(i==j) {i++; ii--;}
aux =c[i][j]; c[i][j]=c[i][jj]; c[i][jj]=aux;
aux=c[ii][j]; c[ii][j]=c[ii][jj]; c[ii][jj]=aux;
}
return c;
}
static int [][] cPair4np2(int n) {
int m=(n-2)/4;
if(4*m+2 != n) return null;
int c[][] = new int[n][n], nn=n/2,p=n/4;
int i,j // indices dans carré d'ordre n=4*m+2
,r,s // indices dans carré d'ordre 2*m+1
,rr,ss ,k,v,lux;
final int L=0,U=1,X=2; // L U X
int xx[][] = new int[][] {{1,0,1,0},{0,0,1,1},{0,1,0,1}}; // delta colonne
int yy[][] = new int[][] {{0,1,1,0},{0,1,1,0},{0,1,1,0}}; // delta ligne
s=1; // départ ligne 0 du carré (2m+1)x(2m+1)
r=m-1; // colonne milieu
for(rr=0, v=-3; rr<(2*m+1); rr++) {
for(ss=0; ss<(2*m+1); ss++) {
// -1 en ligne, +1 en colonne
s=(s==0) ? 2*m : s-1;
r=(r==2*m) ? 0 : r+1;
v+=4;
// Suivant lignes du haut, milieu(presque) ou bas
lux = (s<=m) ? L : (s==m+1 ? U : X);
if((s==m || s==m+1) && r==m) lux=1-lux;
for(k=0; k<4; k++) {
i=2*s+yy[lux][k];
j=2*r+xx[lux][k];
c[i][j]=v+k;
}
}
// Avant la collision
s+=2; if(s>=2*m+1) s=s-2*m-1;
r=(r==0)?2*m:r-1;
}
return c;
}
static int [][] cPair(int n) {
// utilise:
// la constante c4
// les méthodes: cPAir, cImpair, complement, isoLiDi, symetrieLigne
if(n<6) { return c4;}
// ta, tb, tc, td sontdes carrés d'ordre n/2
// ta ne contient que des 0 et des 3; ta et tc sont complémentaires
// tb ne contient que des 1 et des 2; tb et td sont complémentaires
// cm est un carré magique d'ordre n/2; cn est symétrique-ligne de cm
// Le carré est | ta tb | | ca cm |
// (n/2)^2 * | | + | |
// | tc td | | cs cs |
int nn=n/2, n2=nn*nn;
int ta[][], tc[][];
int tb[][], td[][], tt[][];
tb = new int[nn][nn];
tc = new int[nn][nn]; tc = new int[nn][nn];
// m2=nb.de 2 par ligne dans tb; m1= nb.de 1 dans tb
// m3=nombre de 3 par ligne dans ta;
// à vérifier: 3*m3+m2 = nn
// Générer ta et tc
int m3=nn/2, d3=nn-m3;
ta = isoLiDi(m3,d3,nn,3,0); tc = complement(ta,nn,3);
// Générer tb et td
int m2=2*nn-3*m3,m1=nn-m2; // dans tb
m2=nn-m2;m1=nn-m1; // dans td
int d2=nn-m2,d1=nn-d2;
td = isoLiDi(m1,d2,nn,1,2); tb = complement(td,nn,3);
// Un carré magique,et son "symétrique ligne"
int cm[][], cc[][];
if(nn%2==0) cm=cPair(nn); else cm=cImpair(nn);
int cs[][] = symetrieLigne(cm,nn);
// Carré complet
int i,ip,j,jp, c[][] = new int [n][n];
for(tt=ta, cc=cm, ip= 0, jp= 0, i=0; i<nn; i++)
for(j=0; j<nn; j++) c[i+ip][j+jp]=tt[i][j]*n2+cc[i][j];
for(tt=tb, cc=cm, ip= 0, jp=nn, i=0; i<nn; i++)
for(j=0; j<nn; j++) c[i+ip][j+jp]=tt[i][j]*n2+cc[i][j];
for(tt=tc, cc=cs, ip=nn, jp= 0, i=0; i<nn; i++)
for(j=0; j<nn; j++) c[i+ip][j+jp]=tt[i][j]*n2+cc[i][j];
for(tt=td, cc=cs,ip=nn, jp=nn, i=0; i<nn; i++)
for(j=0; j<nn; j++) c[i+ip][j+jp]=tt[i][j]*n2+cc[i][j];
return c;
}
static int[][] isoLiDi( int p, int q, int n, int vp,int va) {
// Construction de matrice en 0/1 contenant p fois vp par ligne
// et q fois vp sur la diagonale principale
// les autres elements contiennent va
// Le matrice construite est symétrique par rapport au point n/2,n/2:
// t[i][j] == t[n-1-i][n-1-j]
// CONDITION: (0<p<n && 0<=q<=n) || (p==0 && q<n) || (p==n && q==n)
int t[][] = new int[n][n];
int i,iip1,j,md, ml;
// p fois vp et n-p fois va par ligne ou diag.princ
// iip1 vaut 0 ou 1 suivant qu'on place vp sur la diagonale ou non
// md nombre de vp sur la diagonale; ml nombre de vp par ligne
for(i=0, md=0; i<n; i++) {
iip1=0;
if(md<q) md++; else iip1=1;
// p fois vp à partir de [i][i] ou [i][i+1]
for(ml=0,j=i+iip1; ml<p; ml++,j++) {
if(j>=n) j-=n;
t[i][j]=vp;
}
// va pour les autres positions de la ligne i
for( ; ml<n; ml++,j++) {
if(j>=n) j-=n;
t[i][j]=va;
}
}
return t;
}
static int[][] complement( int a[][], int n, int vc) {
// Construit le complément du carré a
// c est rempli de haut en bas d'après les lignes de a, utilisées
// de bas en haut
// si a[i][j]==v, alors c[n-1-i][j]==vc-v
int i,j,ii, c[][] = new int[n][n];
// c est rempli de haut en bas; les lignes de a de bas en haut
for(i=0, ii=n-1; i<n; i++, ii--) {
// ligne i de c: échange v1 <--> v2 par rapport à ligne ii de a
for(j=0; j<n; j++) c[i][j] = vc-a[ii][j];
}
return c;
}
static int[][] symetrieLigne(int a[][], int n) {
int i,j, c[][] = new int[n][n];
for(i=0; i<n; i++) {
// ligne i de cs = ligne symétrique de cm
for(j=0; j<n; j++) c[i][j] = a[n-1-i][j];
}
return c;
}