# TDA Practica 1 ejercicio 2
### MagiCuadrados
2. Un cuadrado mágico de orden $n$ es un cuadrado con los números $\{1 \ldots n^2\}$ tal que todas sus filas, columnas y las dos diagonales suman lo mismo (ver figura). El número que suma cada fila es llamado número mágico.
Existen muchos métodos para generar cuadrados mágicos. **El objetivo de este ejercicio es contar cuántos cuadrados mágicos de orden $n$ existen**.
a) ¿Cuántos cuadrados habría que generar para encontrar todos los cuadrados mágicos si se utiliza una solución de fuerza bruta?
b) Enunciar un algoritmo que use backtracking para resolver este problema que se base en las siguientes ideas:
- La solución parcial tiene los valores de las primeras $i - 1$ filas establecidos, al igual que los valores de las primeras $j$ columnas de la fila $i$.
- Para establecer el valor de la posición $(i, j+1)$ (o $(i+1, 1)$ si $j = n$ e $i \neq n$) se consideran todos los valores que aún no se encuentran en el cuadrado. Para cada valor posible, se establece dicho valor en la posición y se cuentan todos los cuadrados mágicos con esta nueva solución parcial.
- Mostrar los primeros dos niveles del árbol de backtracking para $n = 3$.
c) Demostrar que el árbol de backtracking tiene $O((n^2)!)$ nodos en peor caso.
d) Considere la siguiente poda al árbol de backtracking: al momento de elegir el valor de una nueva posición, verificar que la suma parcial de la fila no supere el número mágico. Verificar también que la suma parcial de los valores de las columnas no supere el número mágico. Introducir estas podas al algoritmo e implementarlo en la computadora. ¿Puede mejorar estas podas?
e) Demostrar que el número mágico de un cuadrado mágico de orden $n$ es siempre $\frac{n^3 + n}{2}$. Adaptar la poda del algoritmo del ítem anterior para que tenga en cuenta esta nueva información. Modificar la implementación y comparar los tiempos obtenidos para calcular la cantidad de cuadrados mágicos.
## Resolución
### a) - b)
- a) La cantidad de cuadrados que habría para encontrar todos los cuadrados mágicos posibles es de $n^2$! pues habría que ver todas las permutaciones posibles.
- b) Ahora para el algoritmo voy a dejar plasmada una idea y luego voy a dejar un código que no es mío, es de una amiga que cursa conmigo Micaela aka Ninetales en los grupos de telegram.
- Mi idea:
- Primero inicializo una matriz de $n \times n$ con ceros o con -1 (como para decir que ahí todavía no hay nada)
- Luego me fijo que si: al colocar un número, **las sumas parciales** de la fila, columna y diagonal son **menores o iguales** al número magico, entonces movete a la siguiente posición.
- Si al colocar el número la suma parcial **es mayor** al número magico, entonces movete a la siguiente posición.
- Si al colocar el número la suma parcial es mayor al número mágico, removerlo y avanzar.
- Si no quedan más números por probar y no se formó el cuadrado mágico, **hacer backtrack** a la posición anterior con el siguiente más pequeño.
- Repetir estos pasos hasta que se complete
```python=
def magiCuadrado(n):
# Esto es puramente con fines declarativos, podría directamente llamar a la función con los valores y listo
c= np.zeros((n, n))
N = [x + 1 for x in list(range(n**2))]
i= 0
j= 0
nm= 0
#suma= 0
return magiCuad(n, i, j, N, c, 0)
def fila_val(c, i):
return sum(c[i])== sum(c[0])
def col_val(c, j):
return sum(c[:, j])== sum(c[0])
def magiCuad(n, i, j, N, c, suma):
if i==(n-1) and j==(n-1): # si llego al último casillero
c_l = c.copy()
c_l[i][j] = N[0]
if (fila_val(c_l, i) and col_val(c_l, j)): # chequeo que tanto la última fila como columna de el número mágico
print("Success! :D")
print(c_l)
return 1 # es cuadrado mágico!
else:
print("F")
print(c_l)
return 0 # F
elif i==(n-1): # si estoy por llenar una nueva columna:
for l in range(len(N)):
n_l = N.copy()
c_l = c.copy()
c_l[i][j] = n_l[l]
n_l.pop(l)
if col_val(c_l, j): # si la suma de la columna me da, sigo
suma+= magiCuad(n, i, j+1, n_l, c_l, suma)
else:
return 0 # la suma de la columna no me dió, descarto
elif j==(n-1): # si estoy por llenar otra fila
for l in range(len(N)):
n_l = N.copy()
c_l = c.copy()
c_l[i][j] = n_l[l]
n_l.pop(l)
if i==0 or fila_val(c_l, i):
suma+= magiCuad(n, i+1, 0, n_l, c_l, suma) # puede ser solución parcial, sigo sumando en la siguiente fila
else:
return 0 # ya sé que no es solución parcial, descarto (o sea, no la sumo ni la sigo llenando)
else: # si no se completó nada, sigo no más
for l in range(len(N)):
n_l = N.copy()
c_l = c.copy()
c_l[i][j] = n_l[l]
n_l.pop(l)
suma+= magiCuad(n, i, j+1, n_l, c_l, suma)
return suma
```
También dejo mi versión del código:
```python
def es_valido(cuadro: list, n: int, numero_magico: int, i: int, j: int, num: int) -> bool:
# Verifica si el número ya está en el cuadrado
for fila in cuadro:
if num in fila:
return False
# Verifica las sumas de la fila y columna
suma_fila = sum(cuadro[i])
suma_columna = sum(cuadro[k][j] for k in range(n))
if suma_fila + num > numero_magico or suma_columna + num > numero_magico:
# Poda por suma excesiva
return False
# Verifica las diagonales si es necesario
if i == j:
suma_diagonal_principal = sum(cuadro[k][k] for k in range(n))
if suma_diagonal_principal + num > numero_magico:
# Poda por suma excesiva en diagonal principal
return False
if i + j == n - 1:
suma_diagonal_secundaria = sum(cuadro[k][n-1-k] for k in range(n))
if suma_diagonal_secundaria + num > numero_magico:
# Poda por suma excesiva en diagonal secundaria
return False
return True
def resolver_cuadrado(cuadro: list, n: int, numero_magico: int, soluciones: list, i: int = 0, j: int = 0):
if i == n:
solucion = [fila[:] for fila in cuadro] # Hace una copia profunda del cuadro actual
soluciones.append(solucion)
return
for num in range(1, n**2 + 1):
if es_valido(cuadro, n, numero_magico, i, j, num):
cuadro[i][j] = num
siguiente_i = i + (j + 1) // n
siguiente_j = (j + 1) % n
resolver_cuadrado(cuadro, n, numero_magico, soluciones, siguiente_i, siguiente_j)
cuadro[i][j] = 0 # Backtracking: remover el número si no lleva a una solución
n = 3
numero_magico = 15
cuadro = [[0 for _ in range(n)] for _ in range(n)]
soluciones = [] # Lista para almacenar las soluciones encontradas
resultado = resolver_cuadrado(cuadro, n, numero_magico, soluciones)
print( len(soluciones))
```
#### Arbol renderizado mediante herramienta de python, recomendado abrirlo en otra pestaña para verlo con claridad.
### c)
- Sabemos que la matriz es de $n \times n$
- Entonces $\therefore$ recorrer la totalidad de una matriz es de complejidad cuadratica.
- Nosotros sabemos por la consigna que cada elemento tiene desde {$1,...,n^2$} las celdas de la matriz.
- La primera celda tiene $n^2$ opciones, la 2da celda tiene $n^2-1$ y así sucesivamente.
- $\therefore \rightarrow O(n^2!)$
$\blacksquare$
### d)
- Algo ya mencioné en el inciso b), pero acá tengo otras podas:
- son al dope no molestarse en leer
- Calcular la suma parcial min y max para cada fila col y diag incompleta
- Calcular la suma min y max posible y si estas sumas no pueden igualar al número mágico, descartar rama
- Descartar sumas parciales imposibles. O sea si al colocar un número en una celda se hace imposible alcanar el número mágico en la col,fil,diag => descartarlo.
### e)
- idea 1 (cc manu f. wpp):
- La suma de los números del cuadrado de 1 hasta $n^2$
- Podemos decir que es una serie de gauss que $\frac{n(n+1)}{2} = \sum_{k=1}^n k$ Pero en este una suma $\sum_{k=1}^{n^2} k = \frac{n^2(n^2+1)}{2}$
- Como en un cuadrado mágico, todsa las filas/cols/diags suman lo mismo (él número mágico $M$)
- $\rightarrow$ $\sum_{k=1}^{n^2}$ = $n \times M$ $\iff$
- $\iff$ $\frac{n^2(n^2+1)}{2}$ = $n \times m$ $\iff$ $\frac{n^2(n^2+1)}{2n}$ = $M$ $\ \ \ \ \ \square$
- idea 2: inducción
- Salu2