7.3.3. Problema de las n reinas.
Problema: Dado un tablero de ajedrez de tamaño nxn, encontrar una forma de colocar n reinas, sin que ninguna de ellas se coma a otra.
No es un problema de optimización, pero podemos usar ramificación y poda para mejorar la búsqueda.
Estimación del beneficio: se usará para indicar qué ramas son las más prometedoras. Tendremos alguna estrategia LC.
Cota inferior y superior: no se usan, se supondrán con valor -? e +?, respectivamente. ? No se realizará ninguna poda.
Se acabará el proceso al encontrar una solución.
La medida de lo prometedora que es una situación del tablero es una medida heurística.
Ejemplo: Una configuración será mejor cuantas más casillas hayan no alcanzables por las reinas colocadas en el mismo.
Beneficio de un tablero = Nº de casillas libres en el tablero