6.3.2. Problema de las n reinas.
Solución con backtracking.
Características: Puede existir solución o no. No es un problema de optimización. Suponemos que buscamos todas las soluciones.
Representación.
- Array solución: s: array [1..8] of 0..8.
- s[i] = j. La reina de la fila i está en la columna j.
Recorrido con backtracking: En cada nivel i, probar las formas de colocar la reina de la fila i, desde la columna 1 hasta la 8.
La posición será válida (podemos avanzar de nivel) si la reina i no está en la misma columna o diagonal que alguna de las reinas anteriores.
Funciones:
- Generar (nivel, s). Probar primero la posición 1, luego la 2, ..., hasta la 8.
- MasHermanos (nivel, s). Cierto si s[nivel] es menor que 8.
- Criterio (nivel, s). Comprobar si la reina de la posición s[nivel] no se come a las anteriores (1, 2, ..., nivel-1).
- Solución (nivel, s). Cierto si el nodo es una hoja (nivel = n) y se cumple Criterio.
- Retroceder (nivel, s). Quitar la reina de la posición nivel. s[nivel]:= 0 (valor de inicialización).