Sto facendo dei temi d'esame, e ho questo sul quadrato magico.
Per chi non lo sapesse, è un quadrato di dimensione N che contiene tutti i numeri da 1 a N^2
Con la particolarità che la somma di ogni riga, ogni colonna e ogni diagonale è N*(N^2 + 1)/2
Sto provando a farla ricorsivamente, ma sto impazzendo, davvero.
Codice: Seleziona tutto
#include <stdio.h>
#include <stdlib.h>
int **alloc2d(int n);
int *alloc1d(int n);
int createSquare(int ***square, int **used, int n, int x);
int check(int **square, int n);
void print(int **square, int n);
void freeAll(int **square, int *used, int n);
int main()
{
int **square, *used;
int n;
printf("Inserisci numero:");
scanf("%d", &n);
square = alloc2d(n);
used = alloc1d(n);
if (createSquare(&square, &used, n, 0) == 1)
print(square, n);
freeAll(square, used, n);
return 0;
}
int **alloc2d(int n) {
int **sq, i, j;
if( (sq = (int **) malloc (sizeof(int *)*n)) == NULL ) {
fprintf(stderr, "Errore allocazione memoria");
exit(1);
}
for (i=0;i<n;i++) {
if( (sq[i] = (int *) malloc (sizeof(int)*n)) == NULL ) {
fprintf(stderr, "Errore allocazione memoria");
exit(1);
}
}
for (i=0;i<n;i++)
for (j=0;j<n;j++)
sq[i][j] = 0;
return sq;
}
int *alloc1d(int n) {
int *us, i;
if( (us = (int *) malloc (sizeof(int)*(n*n))) == NULL ) {
fprintf(stderr, "Errore allocazione memoria");
exit(1);
}
for (i=0;i<(n*n);i++) {
us[i] = 0;
}
return us;
}
int createSquare(int ***square, int **used, int n, int x) {
int i;
if ( x == (n*n) ) {
return check ((*square), n);
}
for (i=1;i<(n*n);i++) {
if (!(*used)[i-1]) {
(*used)[i-1] = 1;
(*square)[x/n][x%n] = i;
if (createSquare(square, used, n, x+1))
return 1;
(*used)[i-1] = 0;
}
}
return 0;
}
int check(int **square, int n) {
int i, j;
int sum = n*(n*n +1) / 2;
int tmp = 0;
//prima diagonale
for (i=0;i<n;i++) {
tmp += square[i][i];
}
if (tmp == sum) {
tmp = 0;
}
else {
return 0;
}
//seconda diagonale
for (i=n-1;i>=0;i--) {
tmp += square[i][i];
}
if (tmp == sum) {
tmp = 0;
}
else {
return 0;
}
//righe
for (i=0;i<n;i++) {
for (j=0;j<n;j++) {
tmp += square[i][j];
}
if (tmp == sum) {
tmp = 0;
}
else {
return 0;
}
}
for (i=0;i<n;i++) {
for (j=0;j<n;j++) {
tmp += square[j][i];
}
if (tmp == sum) {
tmp = 0;
}
else {
return 0;
}
}
return 1;
}
void print(int **square, int n) {
int i, j;
for (i=0;i<n;i++) {
for (j=0;j<n;j++)
printf("%2d", square[i][j]);
printf("\n");
}
}
void freeAll(int **square, int *used, int n) {
int i;
for (i=0;i<n;i++) {
free(square[i]);
}
free(square);
free(used);
}