Magic_Square_Generator

#include <stdio.h>

#define N 4
#define SUMA  ((N*(N*N+1))/2)

int cont =0;
/*
int correcto(int cuadrado[][N]){
int i,j;
int columna, fila, diagonal;

    //revisar columnas
    for(i=0;i<N;i++){
        columna=0;
        for(j=0;j<N;j++) columna+= cuadrado[i][j];
        if (columna != SUMA) return 0;
    }

    //revisar filas
    for(j=0;j<N;j++){
        fila=0;
        for(i=0;i<N;i++) fila+= cuadrado[i][j];
        if (fila != SUMA) return 0;
    }

    // diagonal principal
    diagonal=0;
    for(i=0;i<N;i++) diagonal+= cuadrado[i][i];
    if (diagonal!= SUMA) return 0;
    //diagonal secundaria
    diagonal=0;
    for(i=0;i<N;i++) diagonal+= cuadrado[i][N-i-1];
    if (diagonal!= SUMA) return 0;

    return 1;
}

*/

void print(int cuadrado[][N]){
    int i,j;
    for(i=0;i<N;i++){
        for(j=0;j<N;j++) printf("%3d",cuadrado[i][j]);
        printf("\n");
    }
    printf("\n");

return ;
}

int completar(int check[], int cuadrado[][N]){
    int i,j,k;
    int modificados[N*N+1];

    for(i=1;i<=N*N;i++) modificados[i]=check[i];

    int diagonal;
    int ultimo;

    for(j=0;j<N;j++){

        ultimo=SUMA;
        for(k=0; k<N-1;k++){
            ultimo= ultimo-cuadrado[k][j];
        }

        if (ultimo>0 && ultimo<=N*N && !modificados[ultimo]){
            modificados[ultimo]=1;
            cuadrado[N-1][j]=ultimo;
        }
        else    return 0;

    }



    // diagonal principal
    diagonal=0;
    for(i=0;i<N;i++) diagonal+= cuadrado[i][i];
    if (diagonal!= SUMA) return 0;
    //diagonal secundaria
    diagonal=0;
    for(i=0;i<N;i++) diagonal+= cuadrado[i][N-i-1];
    if (diagonal!= SUMA) return 0;

    return 1;
}



void backtrack( int i, int j, int check[], int cuadrado[][N]){
    int k;
    int ultimo;

    if (i==N-1) {if (completar(check, cuadrado)){ print(cuadrado); cont++; } }

    else if (j==N-1){

        ultimo=SUMA;
        for(k=0;k<j;k++) ultimo=ultimo-cuadrado[i][k];
        //printf("Deberiamos asignar %d a %d %d\n",ultimo,i,j);
        if (ultimo>0 && ultimo<=N*N && !check[ultimo]){
            check[ultimo]=1;
            cuadrado[i][j]= ultimo;
            //printf("Asignamos %d a %d %d\n", ultimo, i,j);
            backtrack(i+1, 0, check, cuadrado);
            check[ultimo]=0;
        }
    }

    else{
        for(k=1;k<=N*N;k++) if (!check[k]){
            check[k]=1;
            cuadrado[i][j]=k;
            //printf("Asignamos %d a %d %d\n", k, i,j);
            backtrack(i,j+1,check, cuadrado);
            check[k]=0;
        }

    }
    return ;
}


int main(){

int check[N*N+1];
int cuadrado[N][N];

int i;

for(i=1;i<=N*N;i++) check[i]=0;
//printf("%d\n",SUMA);
backtrack(0,0,check, cuadrado);
printf("El total de cuadrados magicos es %d\n",cont);

return 0;
}