/*
 * det4.c
 *
 * Déterminant maximal d'une matrice carrée nxn
 * d'éléments entiers 1, 2, ..., n2
 *
 * 16/09/2003 Jean-Paul Davalan <jpdvl@wanadoo.fr>
 * 
 * ---------------------------------------------------------------------
 * Compilation : gcc -O2 -o det4 det4.c
 * Utilisation : det4
 * ---------------------------------------------------------------------
 * 
 * La suite A085000 de N. Sloane donne les valeurs 1, 10, 412 comme valeurs maximales des
 * déterminants des matrices carrées à n lignes et n colonnes dont les
 * éléments sont les premiers entiers non nuls : 1, 2, 3, 4, ..., n<sup>2</sup>.
 * On cherche la valeur suivante lorsque n=4 et on trouve 40800
 *
 * Lorsque n est égal à 4, on peut se limiter aux déterminants de la forme
 * 1 a b c
 * d . . .
 * e . . .
 * f . . .
 *
 * tels que 1 < a < b < c, a < d, d < e et d < f.
 *
 * En effet, en permutant deux lignes ou deux colonnes, le déterminant change seulement de signe et
 * on peut toujours obtenir, sans changer la valeur du déterminant, une matrice satisfaisant les
 * inégalités ci-dessus en partant de toute matrice de déterminant maximum.
 *
 * Le programme ci-dessous permet donc, en principe, de déterminer une matrice de déterminant maximum.
 * 
 * Cette version écrite en C se termine après quelques heures et donne l'unique(1) solution.
 *
 * (1) une seule solution satisfait les conditions données plus haut, on obtient l'ensemble des
 * solutions en permutant lignes et colonnes et en ne gardant que les matrices de déterminants positifs.
 * 
 * */
#include <stdio.h>
int maxi=0;

// Au lieu de développer par rapport à la première ligne,
// le calcul du déterminant d'ordre 4 peut être optimisé
/*
inline int 
det(int a[]) {
  int d = // 48 *
	  a[0]*(a[5]*(a[10]*a[15]-a[11]*a[14])
		-a[6]*(a[9]*a[15]-a[11]*a[13])
		+a[7]*(a[9]*a[14]-a[10]*a[13]))
	  -a[1]*(a[4]*(a[10]*a[15]-a[11]*a[14])
		-a[6]*(a[8]*a[15]-a[11]*a[12])
		+a[7]*(a[8]*a[14]-a[10]*a[12]))
	  +a[2]*(a[4]*(a[9]*a[15]-a[11]*a[13])
		-a[5]*(a[8]*a[15]-a[11]*a[12])
		+a[7]*(a[8]*a[13]-a[9]*a[12]))
	  -a[3]*(a[4]*(a[9]*a[14]-a[10]*a[13])
		-a[5]*(a[8]*a[14]-a[10]*a[12])
		+a[6]*(a[8]*a[13]-a[9]*a[12]));
  return d;
}
*/

/* soustraire k*la première ligne aux lignes 2 3 4 avec k =
 * a[4] a[8] a[12] pour obtenir des zéros dans la 1e colonne
 * calculer le déterminant d'ordre 3 des lignes et colonnes 2 3 4
 */
int b[10];
inline int 
det(int a[]) { // 18 *
	b[0]=a[5]-a[4]*a[1];
	b[1]=a[6]-a[4]*a[2];
	b[2]=a[7]-a[4]*a[3];
        b[3]=a[9]-a[8]*a[1];
        b[4]=a[10]-a[8]*a[2];
       	b[5]=a[11]-a[8]*a[3];
	b[6]=a[13]-a[12]*a[1];
       	b[7]=a[14]-a[12]*a[2]; 
	b[8]=a[15]-a[12]*a[3];
	return  b[0]*(b[4]*b[8]-b[7]*b[5])-b[1]*(b[3]*b[8]-b[6]*b[5])+b[2]*(b[3]*b[7]-b[6]*b[4]);
}

void affiche(int mt[]) {
  int i;
  printf("\n");
  for(i=0;i<16;i++) {
    printf("%2d ",mt[i]);
    if((i+1)%4==0) printf("\n");
  }
  printf("---------------\n");
}

inline void 
  matr(int mt[], int k) {
  int m[16], i, j, d, D;
  if(k==16) {
    d=det(mt);
    if(d>maxi) {
       maxi=d;
       printf("D = %d\n",d);
       affiche(mt);
    }
  } else {    
    for(i=0;i<k;i++)
      m[i]=mt[i];
    for(j=k;j<16;j++) {
      for(i=k;i<16;i++) 
	m[i]=mt[i];	    
      m[j]=mt[k];
      m[k]=mt[j];
      if( (k>4 && k!=8 && k!=12) || (k>0 && k<4 && m[k]>m[k-1]) || (k==4 && m[4]>m[1])
	      ||(k==8 && m[8]>m[4]) ||(k==12 && m[12]>m[4]) || (k==0))
        matr(m,k+1);
    }
  }
}

int main() {
 int i, j, k, d, m[16];
 for(i=0;i<16;i++) m[i]=i+1;
 matr(m,1);
 return 0;
}