Problema de las N Reinas y sus Heurísticas: Guía Completa
El problema de las N Reinas es un clásico en el mundo de la informática y las matemáticas. En este artículo, te explicamos qué es, cómo resolverlo usando heurísticas y su importancia en la inteligencia artificial. ¡Incluye ejemplos prácticos y algoritmos!
1. Introducción
El problema de las N Reinas es una generalización del problema clásico de las 8 reinas. Consiste en colocar N reinas en un tablero de ajedrez de N × N de tal manera que ninguna reina ataque a otra. Este problema es un ejemplo clásico de los desafíos que se abordan en la teoría de algoritmos y la inteligencia artificial.
El término heurística proviene del griego εὑρίσκειν (heuriskein), que significa "hallar" o "inventar". Las heurísticas son técnicas que permiten resolver problemas de manera eficiente, especialmente cuando no existe una solución directa o esta es demasiado costosa computacionalmente.
2. ¿Qué es el Problema de las N Reinas?
El problema consiste en colocar N reinas en un tablero de ajedrez de N × N sin que se ataquen entre sí. Dos reinas se atacan si están en la misma fila, columna o diagonal.
Ejemplo: Para N = 4, una solución válida sería:
0 1 2 3
---------
0 | | Q | | |
1 | | | | Q |
2 | Q | | | |
3 | | | Q | |
En este caso, ninguna reina está en la misma fila, columna o diagonal.
3. Heurísticas para Resolver el Problema
Las heurísticas son técnicas que permiten encontrar soluciones aproximadas o completas de manera eficiente. Algunas heurísticas comunes para resolver el problema de las N Reinas son:
a) Backtracking (Vuelta Atrás)
El backtracking es un método de búsqueda exhaustiva que prueba todas las posibles combinaciones hasta encontrar una solución válida. Si una combinación no funciona, el algoritmo retrocede y prueba otra.
Ejemplo en Python:
def es_seguro(tablero, fila, columna, n):
# Verifica la misma columna
for i in range(fila):
if tablero[i][columna] == 1:
return False
# Verifica la diagonal superior izquierda
for i, j in zip(range(fila, -1, -1), range(columna, -1, -1)):
if tablero[i][j] == 1:
return False
# Verifica la diagonal superior derecha
for i, j in zip(range(fila, -1, -1), range(columna, n)):
if tablero[i][j] == 1:
return False
return True
def resolver_n_reinas(tablero, fila, n):
if fila >= n:
return True
for columna in range(n):
if es_seguro(tablero, fila, columna, n):
tablero[fila][columna] = 1
if resolver_n_reinas(tablero, fila + 1, n):
return True
tablero[fila][columna] = 0
return False
b) Algoritmos Genéticos
Los algoritmos genéticos son una técnica de optimización inspirada en la evolución natural. Se generan soluciones candidatas (individuos) y se seleccionan las mejores para "reproducirse" y crear nuevas soluciones.
c) Búsqueda Local
La búsqueda local comienza con una solución inicial y realiza pequeños cambios para mejorar la solución. Un ejemplo es el algoritmo de Hill Climbing.
4. Aplicaciones del Problema de las N Reinas
El problema de las N Reinas no es solo un ejercicio teórico. Tiene aplicaciones prácticas en:
- Inteligencia Artificial: Se utiliza para probar algoritmos de búsqueda y optimización.
- Planificación de Recursos: Puede modelar problemas de asignación de recursos sin conflictos.
- Diseño de Circuitos: Se aplica en la disposición de componentes para evitar interferencias.
5. Ejemplo Práctico: Resolver el Problema de las 8 Reinas
Aquí tienes un ejemplo completo en Python para resolver el problema de las 8 reinas usando backtracking:
def imprimir_tablero(tablero, n):
for fila in range(n):
for columna in range(n):
print("Q" if tablero[fila][columna] == 1 else ".", end=" ")
print()
def resolver_n_reinas(n):
tablero = [[0] * n for _ in range(n)]
if not resolver_n_reinas(tablero, 0, n):
print("No existe solución")
else:
imprimir_tablero(tablero, n)
# Resolver el problema de las 8 reinas
resolver_n_reinas(8)
Salida:
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
6. Conclusión
El problema de las N Reinas es un desafío clásico que combina matemáticas, algoritmos y creatividad. Resolverlo no solo es un ejercicio intelectual, sino también una forma de entender técnicas fundamentales en la informática, como el backtracking y las heurísticas. ¡Practica con los ejemplos y lleva tus habilidades al siguiente nivel!
7. Recursos Adicionales
Si quieres profundizar en el tema, te recomendamos los siguientes recursos:
NREINAS Y SUS HEURÍSTICAS
Planteamiento del problema
Este problema
consiste en ubicar n reinas en un tablero de ajedrez de n x n. Tal que, entre
las reinas no se puedan atrapar. Para propósitos metódicos, ubicaremos las
reinas desde la primera fila, hasta completar en la última fila.
Proponer al menos 2
heurísticas adicionales interesantes (adicionales a los vistos en clase), para
resolver el problema de las nReinas. Ejecutar el algoritmo para n = 1, 2, 3, ….
Hasta n grande (hasta donde sea posible). Para cada valor de n, encontrar
la cantidad de vueltas según las heurísticas utilizadas. Graficar, comparar y
concluir.
Construccion de la clase de NReinas
public class NReinasC {
/**
* @param args the command line
arguments
*/
public static long c = 0;
public static void main(String[] args) {
// TODO code
application logic here
int n=20;
int m[][]=new int[n][n];
if
(nReinas(m,0)) {
System.out.println("Exsiste soluciones...!");
mostrar(m);
}else
System.out.println("No existe solciones...!");
System.out.println("cant vueltas: "+c);
}
//---------otros metodos
public static boolean nReinas(int m[][], int i){
if(i >= m.length) return true;
LinkedList<Regla> L1 =
RDama(m, i);
while(!L1.isEmpty()){
Regla R = elegirReglaD(L1); //************
m[R.fil][R.col] = i + 1;
if(nReinas(m, i + 1)) return true;
m[R.fil][R.col] = 0;
c++;
}
return false;
}
}
-------------------
Movimiento
de la Reina
|
1 2 3 4 5 6 7 |
public static LinkedList<Regla> RDama(int m[][], int i){ LinkedList<Regla> L1
= new LinkedList(); for(int j = 0; j < m[i].length; j++){ if(posValido(m, i, j)) L1.add(new Regla(i, j)); } return L1; } |
Metodo
que verifica las posiciones
|
1 2 3 4 5 |
public static boolean posValido(int m[][], int i, int j){ return filValido(m, i) &&
colValido(m, j) && diagSupIzq(m, i, j)
&& diagSupDer(m, i, j) && diagInfIzq(m, i, j)
&& diagInfDer(m, i, j); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public static boolean filValido(int m[][], int i){ int j=0; while (j<m[i].length) { if(m[i][j]!=0) return false; j++; } return true; } public static boolean colValido(int m[][], int j){ int i=0; while (i<m.length) { if(m[i][j]!=0) return false; i++; } return true; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public static boolean diagSupIzq(int m[][], int i1,int j1){ int i=i1,j=j1; while (i>=0 && j>=0) { if(m[i][j]!=0) return false; i--; j--; } return true; } public static boolean diagSupDer(int m[][], int i1,int j1){ int i=i1,j=j1; while (i>=0 && j<m[i].length) { if(m[i][j]!=0) return false; i--; j++; } return true; } |
Heuristicas 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public static Regla elegirReglaA(LinkedList<Regla>l1){ return l1.removeFirst(); } public static Regla elegirReglaB(LinkedList<Regla>
L1){ return L1.remove(L1.size() / 2); } public static Regla elegirReglaC(LinkedList<Regla>l1){ return l1.remove(l1.size()/4); } public static Regla elegirReglaD(LinkedList<Regla>l1){ if (l1.size()<14) return l1.remove(l1.size()/3); return l1.remove(l1.size()/2); } public static Regla elegirReglaR(LinkedList<Regla>l1){ return l1.remove((int)(Math.random()*l1.size())); } |
No hay comentarios:
Publicar un comentario