Para estos efectos consideramos que dos cuadrados mágicos son idénticos si su suma es la misma.
Que dos cuadrados mágicos sean idénticos significa que se puede pasar de uno a otro intercambiando columnas, filas o rotando todo el cuadrado.
Entonces, estos ocho cuadrados mágicos son idénticos, y mi solución imprimira solo uno de ellos:
A efectos de simplificar la discusión, trabajare sobre datos fijos:
#define N 9
#define LIMITE 26
int num[LIMITE];
int sumas[LIMITE * 3];
El arreglo num
contiene todos los digitos desde 1 a LIMITE. Los primeros 9 valores corresponde a los 9 casilleros del cuadrado magico.
El arreglo sumas
se usa para registrar los valores ya calculados. Si sumas[x] == x
, significa que ya se encontró un cuadrado mágico con suma x
.
El procedimiento recursivo hacer_magia
recibe como parámetro el indice 0-8 del casillero que debemos ajustar, y prueba todos los cuadrados producidos al intercambiar el casillero en cuestión con cada uno de los valores que siguen, hasta el último elemento de la lista (que en este caso tiene 26 elementos).
Para probar los cuadrados, el procedimiento se llama a si mismo pasando el indice del siguiente casillero.
Cuando la recursión alcanza al último casillero, se evalúa el cuadrado y se imprime si es mágico:
/*
* Crea un cuadrado magico de 3x3
*
* int idx_num: Indice entre 0-8 que da el casillero desde el
* cual llenar la matriz.
*
*/
void hacer_magia(int idx_num) {
// Hack para acortar la busqueda: si la primera fila da un valor
// ya calculado, desechamos la matriz, pues es mera reflexion/rotacion
// de una matriz previa.
if (idx_num > 2) {
int s0 = suma_fila(0);
if (ya_calculada(s0)) {
// Desechamos la matriz.
return;
}
else if (idx_num < 6) {
// Otro hack. Si las dos primeras filas no coinciden (estando completas)
// no tiene caso seguir. Si la segunda fila es mayor que la primera,
// tampoco.
int s1 = suma_fila(1);
if ((idx_num == 3 && s1 > s0) ||
(idx_num == 5 && s0 != s1)) {
return;
}
}
}
// Estamos ante un potencial cuadrado magico.
if (idx_num == N) {
// Completamos nueve casilleros, evaluar el resultado.
if (es_magico()) {
print(num, N);
}
} else {
// Revisar los casilleros que siguen, por si alguno forma
// un cuadrado magico
hacer_magia(idx_num + 1);
// Intercambiar el casillero actual con cada uno de los casilleros
// siguientes, y evaluar en cada caso si hay cuadrados magicos.
for (int idx_nvo = idx_num + 1; idx_nvo < LIMITE; idx_nvo++) {
intercambiar(idx_num, idx_nvo);
hacer_magia(idx_num + 1);
intercambiar(idx_num, idx_nvo);
}
}
}
int main() {
for (int i = 0; i < LIMITE; i++)
num[i] = i + 1;
hacer_magia(0);
return 0;
}
Nota: El código completo está en Try it online!.
Aqui ocupamos varias funciones cortas, que no incluyo para no alargar la historia, pero que son simples de implementar:
ya_calculada(suma)
. Retorna 1 si ya hay un cuadrado con esa suma.
suma_fila(fila)
. Retorna la suma para la fila 0-2.
es_magico()
. Retorna 1 si es un cuadrado mágico.
print(num,N)
. Imprime la matriz.
intercambiar(i1,i2)
. Intercambia los valores num[i1]
con num[i2]
.
Comprobación
Cuadrado 1
2 4 9 (15)
6 8 1 (15)
7 3 5 (15)
---------------
15 15 15 (15)
Cuadrado 2
2 4 10 (16)
6 9 1 (16)
8 3 5 (16)
---------------
16 16 16 (16)
Cuadrado 3
2 4 11 (17)
6 10 1 (17)
9 3 5 (17)
---------------
17 17 17 (17)
Cuadrado 4
2 4 12 (18)
6 11 1 (18)
10 3 5 (18)
---------------
18 18 18 (18)
....
Cuadrado 41
8 21 26 (55)
25 24 6 (55)
22 10 23 (55)
---------------
55 55 55 (55)
RUN FINISHED; exit value 0; real time: 1m 28s; user: 0ms; system: 1m 28s