//<title>Construction de carrés magiques : applet Java </title>

// CarMagique.java   <xmp>
//   Trois classes:
//      CarMagique :  choix de méthode
//      CarreFen   :  présentation de carré
//      Carre      :  construction de carré
//
//    jar -cvf raCarreM.jar Car*.class
//    lancement de l'applet par: raCarreMagie.html

import java.awt.*;
import java.awt.event.*;


//  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //// 
//                   Choix de méthodes de construction                //
//                         applet ou application                      //
//  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  ////  



public class CarMagique extends java.applet.Applet
                           implements ActionListener, ItemListener {
  Choice choixP, choixI, choixI2, choixI3, choixI4, choixP4n, choixP4np2;
  // Pour utilisation mixte, applet ou application
  public void init() { creerIU(null); }

  private void creerIU(Frame f) {
     
     choixI = new Choice(); Button btnI=new Button("Ordre impair 1");
     for(int i=3; i<32; i+=2) choixI.add(""+i);
     choixI.addItemListener(this); // add(choixI);
     btnI.addActionListener(this); btnI.setActionCommand("impair1");

     choixI2 = new Choice(); Button btnI2=new Button("Ordre impair 2");
     for(int i=3; i<32; i+=2) choixI2.add(""+i);
     choixI2.addItemListener(this); // add(choixI2);
     btnI2.addActionListener(this); btnI2.setActionCommand("impair2");

     choixI3 = new Choice(); Button btnI3=new Button("Ordre impair 3");
     for(int i=3; i<32; i+=2) choixI3.add(""+i);
     choixI3.addItemListener(this); // add(choixI2);
     btnI3.addActionListener(this); btnI3.setActionCommand("impair3");

     choixI4 = new Choice(); Button btnI4=new Button("Ordre impair 4");
     for(int i=3; i<32; i+=2) choixI4.add(""+i);
     choixI4.addItemListener(this); // add(choixI2);
     btnI4.addActionListener(this); btnI4.setActionCommand("impair4");

     choixP = new Choice(); Button btnP=new Button("Ordre pair");
     for(int i=4; i<32; i+=2) choixP.add(""+i);
     choixP.addItemListener(this); // add(choixI);
     btnP.addActionListener(this); btnP.setActionCommand("pair");
     // this.add(choixP);

     choixP4n = new Choice(); Button btnP4n=new Button("Multiple de 4");
     for(int i=4; i<37; i+=4) choixP4n.add(""+i);
     choixP4n.addItemListener(this); // add(choixI);
     btnP4n.addActionListener(this); btnP4n.setActionCommand("pair4n");

     choixP4np2 = new Choice(); Button btnP4np2=new Button("2+ multiple de 4");
     for(int i=6; i<37; i+=4) choixP4np2.add(""+i);
     choixP4np2.addItemListener(this); // add(choixI);
     btnP4np2.addActionListener(this); btnP4np2.setActionCommand("pair4np2");

     Button aff=new Button("HyperMagique"); // this.add(aff);
     aff.addActionListener(this); aff.setActionCommand("c8");
     if(f != null) f.add(this);

     this.setLayout(new BorderLayout());
     Panel p1=new Panel(new GridLayout(0,2)), p2=new Panel();
     p1.add(btnI);p1.add(choixI);
     p1.add(btnI2);p1.add(choixI2);
     p1.add(btnI3);p1.add(choixI3);
     p1.add(btnI4);p1.add(choixI4);
     p1.add(btnP);p1.add(choixP);
     p1.add(btnP4n);p1.add(choixP4n);
     p1.add(btnP4np2);p1.add(choixP4np2);
     
     p2.add(aff);
     this.add(p1,BorderLayout.CENTER);
     this.add(p2,BorderLayout.SOUTH);
     }

  public void actionPerformed(ActionEvent evt){
     CarreFen f; int ordre=0, c[][]=Carre.c8;
     if(evt.getActionCommand().equals("c8")) ordre=8;
     else if(evt.getActionCommand().equals("impair1")) {
        ordre= Integer.parseInt(choixI.getSelectedItem());
        c=Carre.cImpair(ordre);
        }
     else if(evt.getActionCommand().equals("impair2")) {
        ordre= Integer.parseInt(choixI2.getSelectedItem());
        c=Carre.cImpair2(ordre);
        }
     else if(evt.getActionCommand().equals("impair3")) {
        ordre= Integer.parseInt(choixI3.getSelectedItem());
        c=Carre.cImpair3(ordre);
        }
     else if(evt.getActionCommand().equals("impair4")) {
        ordre= Integer.parseInt(choixI4.getSelectedItem());
        c=Carre.cImpair4(ordre);
        }
     // Ordre pair
     else if(evt.getActionCommand().equals("pair")) {
        ordre= Integer.parseInt(choixP.getSelectedItem());
        c=Carre.cPair(ordre);
        }
     else if(evt.getActionCommand().equals("pair4n")) {
        ordre= Integer.parseInt(choixP4n.getSelectedItem());
        c=Carre.cPair4n(ordre);
        }

     else if(evt.getActionCommand().equals("pair4np2")) {
        ordre= Integer.parseInt(choixP4np2.getSelectedItem());
        c=Carre.cPair4np2(ordre);
        }
     // Créer une fenêtre affichant le carré
     if(ordre>0 && ordre!=2)
        (new CarreFen(c)).show();
     }
 
  public void itemStateChanged(ItemEvent e) {
     int ordre= Integer.parseInt((String)e.getItem());
     Choice choix=(Choice)e.getSource();
     int c[][]=Carre.c8;
     if(choix==choixI)        c=Carre.cImpair(ordre);
     else if(choix==choixI2)  c=Carre.cImpair2(ordre);
     else if(choix==choixI3)  c=Carre.cImpair3(ordre);
     else if(choix==choixI4)  c=Carre.cImpair4(ordre);
     else if(choix==choixP)   c=Carre.cPair(ordre);
     else if (choix==choixP4n)c=Carre.cPair4n(ordre);
     else if (choix==choixP4np2)c=Carre.cPair4np2(ordre);
     CarreFen f=new CarreFen(c);
     f.show();
     }

  // Pour version application
  static Frame initAppli() {
     int xxFen=200, yyFen=220; 
     Frame fen = new Frame();
     fen.setSize(xxFen,yyFen);
     // Placer un composant dans cette fenêtre
     CarMagique cm=new CarMagique();
     cm.creerIU(fen);
     WindowAdapter pf = new WindowAdapter() {
	    public void windowClosing(WindowEvent e){System.exit(0);};
	    };
     fen.addWindowListener(pf);
     return fen;
     }

  // Utilisation application
  public static void main(String[] args) {
     Frame fen = initAppli();
     fen.show();
     // int c[][]=Carre.cImpair2(7); Carre.aff(c,c.length);
     }
  }



//  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //// 
//                     Présentation  de  carrés                       //
//  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  ////  




/** Fenêtre affichant un carré, avec les ommes par ligne
 *  colonne ou diagonale
 */
class CarreFen extends Frame 
                  implements ActionListener, MouseListener, KeyListener {
  int car[][];    // le carré magique
  int n;
  // Cases sélectionnées pour alignement: ligne, colonne, diagonales ...
  boolean csa[][]; // vrai:case choisie,  faux:case simple
  
  Point caseClic;
  int choixCases;  // 1:ligne 2:colonne 3:diag.S 4:diag.P
  final int CXLI=1, CXCO=2,    // choix ligne, colonne   
            CXDM=3, CXDD=4,    //       diagonale montante, descendante
            CXC4=5, CXC2=6;    //       carré 4x4 ou 2x2
  static final String chChoix[][]= { // intitulé item, et commande associée
       {"Ligne","Colonne","Diagonale montante","Diagonale descendante"
        ,"Carre 4*4","Carre 2*2"}
      ,{"li","co","dm","dd","c4","c2"}};
  int nChoix=chChoix[0].length;

  Dialog info;
  Canvas can;

  // Position et dimensions de la case en haut à gauche
  int xchg=50, ychg=40, xxc=25, yyc=24;
  int xxFen, yyFen;
  
  public CarreFen(int c[][]) {
     car=c;
     n=c.length;
     // tous les choix pour carré hypermagique seul
     nChoix = (n==8) ? 6 : 4;
     xxc = (n<32) ? 25 : 30;
     
     csa = new boolean[n][n];
     caseClic=new Point(0,0); choixCases=1; selec(1);
      
     can = new Canvas() {
        public void paint(Graphics g) { afficheCarre(g); }
        };
     
     ScrollPane pa = new ScrollPane();
     add(pa); pa.add(can); 
       
     setMenuBar(barreMenus()); 
     setTitle("Carre magique d'ordre "+n);
     
     // Largeur variable pour avoir l'affichage de toute la somme
     xxFen = xchg+(n<7?7:n)*(xxc+1)+ 
                xchg*(n<10?1:(n<22)?2:3);
     yyFen = ychg+(n+1)*yyc+3*ychg;
     setSize(xxFen,yyFen);
     this.setLocation((int)(100*(1+Math.random())),100);
     // Pour fermer la fenêtre
     WindowAdapter pf = new WindowAdapter() {
	     public void windowClosing(WindowEvent e){dispose();};
	     };
     this.addWindowListener(pf);
     
     // On réagit à la souris et au clavier
     can.addMouseListener(this);
     can.addKeyListener(this);

     // Dialogue avec un texte et bouton fermer
     info=new Dialog(this,false); info.setSize(250,160);
     info.setLayout(new GridLayout(0,1));
     info.add(new Label("Carrés complétés par Roger Astier",Label.CENTER));
     info.add(new Label("Carré crée par Kathleen Ollerenshaw",Label.CENTER));
     info.add(new Label("Applet écrite par Yannick Devaux",Label.CENTER));
     Button vu=new Button("Fermer");
     info.add(vu); 
     // Pour fermer la boîte de dialogue
     vu.addActionListener(this); vu.setActionCommand("fermerBD");
     WindowAdapter pfInfo = new WindowAdapter() {
	     public void windowClosing(WindowEvent e){info.dispose();};
	     };
     info.addWindowListener(pfInfo);
     }

  MenuBar barreMenus() {
    // Choix type de ligne 
     Menu m1=new Menu("Type");
     MenuItem mi;
     for( int i=0; i<nChoix; i++) {
        mi=new MenuItem(chChoix[0][i]);
        ajoutItem(mi,chChoix[1][i],m1);
        }
     m1.addSeparator();
     MenuItem m1q=new MenuItem("Quitter"); ajoutItem(m1q,"Quitter",m1);
     // qui?
     Menu m2=new Menu("Info");
     MenuItem m21=new MenuItem("Qui ?"); ajoutItem(m21,"Info",m2);
     // Les menus dans la barre de menus
     MenuBar m=new MenuBar();
     m.add(m1); m.add(m2);
     return m;
     }
  
  // Aucune case colorée
  public void initCarré() {
     for (int i=0;i<n;i++) 
        for (int j=0;j<n;j++) csa[j][i]=false;
     }
 
  public void selec(int choix) {
     int xtmp,ytmp,i;
     int x=caseClic.x, y=caseClic.y;    // case sélectionnée
     
     choixCases=choix;
     initCarré();
     csa[x][y]=true;
     
     switch(choix) {
        case CXLI :             // ligne
           for (i=1;i<n;i++) {y=(y==n-1)?0:++y; csa[x][y]=true; }
           break;
        case CXCO :             // colonne
           for (i=1;i<n;i++) {x=(x==n-1)?0:++x; csa[x][y]=true; }
           break;
        case CXDM :             // diagonale montante 
            for ( i=1;i<n;i++) {
               x=(x==n-1)?0:++x; y=(y==0)?n-1:--y;
               csa[x][y]=true;
               }
            break;
         case CXDD :            // diagonale descendante
            for ( i=1;i<n;i++) {
               x=(x==n-1)?0:++x; y=(y==n-1)?0:++y; csa[x][y]=true;
               }
            break;
        case CXC4 :             // carré 4x4
           xtmp=x;
           for ( i=0;i<4;i++) {
              ytmp=y;
              for (int j=0;j<4;j++) {
                csa[xtmp][ytmp]=true;
                 ytmp=(ytmp==n-1)?0:++ytmp;
                 }
              xtmp=(xtmp==n-1)?0:++xtmp;
              }
           break;
        case CXC2 :              // carré 2x2
           xtmp=x;
           for ( i=0;i<2;i++) {
              ytmp=y; 
              for (int j=0;j<2;j++) {
                 csa[xtmp][ytmp]=true;
                 ytmp=(ytmp==n-1)?0:++ytmp;
                 }
              xtmp=(xtmp==n-1)?0:++xtmp;
              }
           break;
        }
     repaint();
     }
  
  
  void ajoutItem(MenuItem im, String txt, Menu m) {
     m.add(im);
     im.addActionListener(this);
     im.setActionCommand(txt);
     }

  // renvoie le déplacement
  int miniTexte(Graphics g, int x, int y) {
     int i, yy=15;
     String txt[]={
        "Sur une case:",
        "   premier clic déplace la somme",
        "   un clic de plus change la somme"
        };
     for(i=0, y+=yy; i<txt.length; i++, y+=yy) {
        g.drawString(txt[i], x,y);
        }
     return y;
     }

  public void afficheCarre(Graphics g) {
     String somme="", plusOuEgal;
     int i,j,p,jt=n/2
        ,nb        // nb.éléments dans la somme partielle
        ,som;      // somme des éjléments marqués
     
     // Affichage some magique
     somme = "Somme magique: " + (n*(1+n*n)/2);
     i= (n<7) ? xchg : xchg+30;
     g.drawString(somme,i,ychg-12);
     g.drawString(somme,i+1,ychg-11);
     // Rectangle externe
     g.drawRect(xchg-1,ychg-1,n*xxc+2,n*yyc+2);
     for (somme="", som=0, nb=0, i=0; i<n; i++) for (j=0; j<n; j++){
        int correc=xchg+10;
        correc -= (car[j][i]<10) ? 0 : 
                  (car[j][i]<100)? 3 : 7;
        g.setColor(new Color(180,180,255));
        if (csa[j][i]){
            if(i==n-1) jt=j;  // pour affichage du total à droite
            som += car[j][i];
            nb++; plusOuEgal=(nb<n)?"+":" = ";
            somme += Integer.toString(car[j][i])+plusOuEgal;
            g.fillRect(i*xxc+xchg,j*yyc+ychg,xxc,yyc);
            }
        g.setColor(Color.black); g.drawRect(i*xxc+xchg,j*yyc+ychg,xxc,yyc);
        // g.drawString(Integer.toString(car[j][i]),i*xxc+correc,j*yyc+78); 
        g.drawString( Integer.toString(car[j][i])
                    , i*xxc+correc,j*yyc+ychg+yyc/2+5); 
        }
     somme=(choixCases>=5)?"":somme;
     // dernière ligne
     g.drawString(""+som,xchg+n*xxc+10,ychg+jt*yyc+yyc/2+5);
     g.drawString("Somme : "+somme+som,xchg-xxc,ychg+n*yyc+yyc);
     // marquer le milieu
     if(n%2==0 && n>10){
        p=xchg+n/2*xxc;
        g.drawLine(p-1,ychg-1,p-1,ychg+yyc*n);
        g.drawLine(p+1,ychg-1,p+1,ychg+yyc*n);
        p=ychg+n/2*yyc;
        g.drawLine(xchg,p-1,xchg+xxc*n,p-1);
        g.drawLine(xchg,p+1,xchg+xxc*n,p+1);
        }
     else if(n>10) {
        p=xchg+n/2*xxc;
        g.drawLine(p-1,ychg-1,p-1,ychg+yyc*n);
        g.drawLine(p+xxc+1,ychg-1,p+xxc+1,ychg+yyc*n);
        p=ychg+n/2*yyc;
        g.drawLine(xchg,p-1,xchg+xxc*n,p-1);
        g.drawLine(xchg,p+yyc+1,xchg+xxc*n,p+yyc+1);
        }
     // Texte explicatif
     if(n<10) {
        p=ychg+n*yyc+yyc;
        g.drawLine(0,p+4,xxFen,p+4);
        miniTexte(g,xchg-xxc,ychg+n*yyc+yyc); 
        }
     }
        
  public void actionPerformed(ActionEvent evt){
     String act=evt.getActionCommand();
     if (act=="Quitter") dispose();
     else if (act=="Info") { info.show(); }
     else if (act=="fermerBD") {info.dispose(); }
     else
     {   // Changement ligne, colonne, diagonale ...
        int i;
        for(i=0; i<nChoix && !act.equals(chChoix[1][i]); i++);
        choixCases=1+i;
        selec(choixCases);
        can.repaint();
        }
     }
  
  public void mousePressed(MouseEvent evt) {
     int x, y; x=evt.getX(); y=evt.getY();
     if ((x>=xchg)&&(y>=ychg)) {
        x=(x-xchg)/xxc; y=(y-ychg)/yyc;
        if ((x>=0)&&(x<n)&&(y>=0)&&(y<n)) {
           // System.out.println("mousePressed:"+(y+1)+","+(x+1));
           if(caseClic.x==y && caseClic.y==x) {
              // change le type de somme à afficher
              choixCases = (choixCases==nChoix)?1:choixCases+1;
              }
           else {
              // somme sur une autre colonne, ligne ...
              caseClic=new Point(y,x);
              }
           selec(choixCases);
           can.repaint();
           }
        }
     }
  public void mouseReleased(MouseEvent evt) {}
  public void mouseEntered(MouseEvent evt) {}
  public void mouseClicked(MouseEvent evt) {}
  public void mouseExited(MouseEvent evt) {}
  
  
  public void keyPressed(KeyEvent e) {
     int x=caseClic.x, y=caseClic.y, choix=choixCases;
     boolean modifier=true;
     switch(e.getKeyCode() ) {
        case KeyEvent.VK_DOWN:
           if(choixCases==CXCO) modifier=false;
           x=(x==n-1)?0:x+1;
           break;
        case KeyEvent.VK_UP:
           if(choixCases==CXCO) modifier=false;
           x = (x==0)?n-1:x-1;
           break;
        case KeyEvent.VK_LEFT:
           if(choixCases==CXLI) modifier=false;
           y = (y==0)?n-1:y-1;
           break;
        case KeyEvent.VK_RIGHT:
           if(choixCases==CXLI) modifier=false;
           y = (y==n-1)?0:y+1;
           break;
        case KeyEvent.VK_D:
           if(choixCases==CXDM) { choixCases=CXDD; x=0; y=0;}
           else                 { choixCases=CXDM; x=0; y=n-1;}
           break;
        case KeyEvent.VK_4: choixCases=CXC4; break;
        case KeyEvent.VK_2: choixCases=CXC2; break;
        case KeyEvent.VK_L: choixCases=CXLI; break;
        case KeyEvent.VK_C: choixCases=CXCO; break;
        default: modifier=false; 
        }
     if(modifier){             // Changement effectif
        caseClic=new Point(x,y); selec(choixCases); can.repaint();
        }         
     }
  public void keyReleased(KeyEvent e) { }
  public void keyTyped(KeyEvent e) { }
  
  } //fin class CarreFen



//  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //// 
//                      Construction de carrés                        //
//  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  ////  

class Carre {
  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[][] c3 = {{4,9,2} 
                     ,{3,5,7}
                     ,{8,1,6}};
  final  static int[][] c4 = {{ 1,15,14, 4} 
                     ,{12, 6, 7, 9}
                     ,{ 8,10,11, 5}
                     ,{13, 3, 2,16}};
  final  static int[][] c5 = {{11,18,25, 2, 9}
                     ,{10,12,19,21, 3}
                     ,{ 4, 6,13,20,22}
                     ,{23, 5, 7,14,16}
                     ,{17,24, 1, 8,15}};

  static int [][] c(int n){
     if(n%2==1) return cImpair2(n);
     else       return cPair(n);
     }
  
  // Première méthode pour construire des carrés d'ordre impair
  static int [][] cImpair(int n) {
     int c[][]=new int [n][n];
     int i,j,k,m,v;
     i=1; j=n/2-1;
     for(m=0, v=0; m<n*n; m+=n) {
        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;
     }
  
  // Deuxième méthode pour construire des carrés d'ordre impair
  static int [][] cImpair2(int n) {
     int c[][]=new int[n][n], a[][]=new int[n][n];
     int i,j,jj,k;
     // Premier 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;
     }

  // Troisième méthode pour construire des carrés d'ordre impair
  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;
     }
  
  // Quatrième méthode pour construire des carrés d'ordre impair
  static int [][] cImpair4(int n) {
     int m=(n-1)/2;
     if(2*m+1 != n) return null;
     
     int c[][]=new int [n][n];
     int i0,j0,d,i,j,k,kk,vp,vi;
     i0=m; j0=0; d=1; vi=1; vp=2;
     for(k=0; k<n; k++, d=1-d ) {
        i=i0; j=j0;
        // Valeurs impaires
        for(kk=0; kk<m+d; kk++) {
           c[i][j]=vi;
           vi = vi+2;
           i = (i==0)   ?n-1:i-1;
           j = (j==n-1) ? 0 : j+1;           
           }
        // Valeurs paires
        for(kk=0; kk<m+1-d; kk++) {
           c[i][j]=vp;
           vp = vp+2;
           i = (i==0)   ?n-1:i-1;
           j = (j==n-1) ? 0 : j+1;           
           }
        i0=i0+1-d; j0=j+d;
        }
     return c;
     }
  

  // Construction d'un carré d'ordre multiple de 4  
  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;
            }
           // afficher(c,n);
    return c;
    }
 
  // Construction d'un carré d'ordre multiple de 4
  // mathworld.wolfram.com/MagicSquare.html
  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,r,rr,s,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; r=m-1;
     for(rr=0, v=0; 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;
           c[s][r]=++v;
           }
        // Avant la collision
        s+=2; if(s>=2*m+1) s=s-2*m-1;
        r=(r==0)?2*m:r-1;
        }
 */
     s=1;          // indice ligne du carré (2m+1)x(2m+1)
     r=m-1;        // indice colonne
     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;
     }
  

  // Construction d'un carré d'ordre pair (méthode pour n>=6)
  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;
     }
   

  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //  //
  // Affichage simple
   static void aff(int a[][], int n) {
     int i,j;
     for(i=0; i<a.length; i++) {
        for(j=0; j<a[i].length; j++)  {
           System.out.print(" "
               +((a[i][j]<10)?" ":"")+a[i][j]);
           }
        System.out.println();
        }
     }
   
  }

               

//fin CarMagique.java               </xmp>