#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

#ifdef MCHECK
#include <mcheck.h>
#endif

#ifndef N
#define N 3
#endif
#define DIMENSIONE N*N
#define COSTANTE_MAGICA N*(DIMENSIONE+1)/2

int crea(int *, int *, int);
int controlla_riga(const int *, int);
int somma_e_controlla(const int *, int, int, int);
int controlla_colonna(const int *, int);
int controlla_diagonali(const int *);
void stampa(const int *);
void debug(const char *, ...);

int main(int argc, char **argv)
{
   int *sacchetto, *quadrato, i;

#ifdef MCHECK
   mtrace();
#endif

   sacchetto = malloc(DIMENSIONE * sizeof(int));
   quadrato = malloc(DIMENSIONE * sizeof(int));

   for ( i = 0; i < DIMENSIONE; i++ )
      sacchetto[i] = i+1;

   crea(sacchetto, quadrato, 0);

   free(sacchetto);
   free(quadrato);

#ifdef MCHECK
   muntrace();
#endif

   return 0;
}

int crea(int *sacchetto, int *quadrato, int pos)
{
   int i, pescato;

   for ( i = 0; i < DIMENSIONE; sacchetto[i++] = pescato )
      {
         pescato = sacchetto[i];
         if ( pescato == 0 )
            continue;
         sacchetto[i] = 0;

         quadrato[pos] = pescato;

         if ( (pos+1) % DIMENSIONE == 0 && ! controlla_riga(quadrato, pos+1) )
            continue;

         if ( (pos+1) > DIMENSIONE - N && ! controlla_colonna(quadrato, pos+1) )
            continue;

         if ( (pos+1) == DIMENSIONE )
            if ( controlla_diagonali(quadrato) )
               {
                  stampa(quadrato);
                  return 1;
               }
            else
               {
                  sacchetto[i] = pescato;
                  return 0;
               }
         else
            if ( crea(sacchetto, quadrato, pos+1) )
               return 1;
      }

   return 0;
}

int controlla_riga(const int *quadrato, int num_elem)
{
   int riga = num_elem / N;

   debug("Controllo riga: ");
   return somma_e_controlla(quadrato, (riga-1) * N, riga * N, 1);
}

int controlla_colonna(const int *quadrato, int num_elem)
{
   int colonna = ( (num_elem) % N != 0 ) ? (num_elem) % N : N;

   debug("Controllo colonna: ");
   return somma_e_controlla(quadrato, colonna-1, DIMENSIONE + colonna - N, N);
}

int controlla_diagonali(const int *quadrato)
{
   debug("Controllo diagonale (principale): ");
   if ( somma_e_controlla(quadrato, 0, DIMENSIONE, N+1) )
      {
         debug("Controllo diagonale (secondaria): ");
         if ( somma_e_controlla(quadrato, N-1, N*(N-1)+1, N-1) )
            return 1;
      }
   return 0;
}

int somma_e_controlla(const int *quadrato, int inizio, int fine, int passo)
{
   int somma, i;

   for ( somma = 0, i = inizio; i < fine; i += passo )
      {
         debug("%d ", quadrato[i]);
         somma += quadrato[i];
      }
   debug("\n");

   if ( somma == COSTANTE_MAGICA )
      {
         debug("ok\n");
         return 1;
      }
   return 0;
}

void stampa(const int *quadrato)
{
   int i;

   for ( i = 0; i < DIMENSIONE; i++ )
      {
         if ( DIMENSIONE > 10 && quadrato[i] < 10 )
            printf(" ");

         printf("%d ", quadrato[i]);

         if ( (i+1)%DIMENSIONE == 0 )
            printf("\n");
      }
   printf("\n");
}

void debug(const char *format, ...)
{
 #ifdef DEBUG
   va_list argv;

   va_start(argv, format);
   vprintf(format, argv);
   va_end(argv);
#endif
}