8 Reinas

Diseñar un algoritmo que resuelva el problema de las ocho reinas.
Análisis del problema
El problema consiste en colocar las 8 damas dentro del tablero de ajedrez sin que se coman unas a otras, en general, se tratará de poner n damas en un tablero de n x n.
En vez de colocar las damas en un arreglo (se verá en la tercera parte de los apuntes) de n x n elementos, se utiliza un vector de nelementos. Cada elemento del vector representa la fila donde está la reina. El contenido representa la columna.
El vector damas se inicializa a 0. Para buscar la siguiente solución se comienza situando en damas [1] un 1 (la primera dama está en la primera fila, columna 1) La siguiente dama estará en la fila 2 y empezamos a buscar en la posición 1. No será una posición válida si damas[1] = damas[2](están en la misma columna); damas[1] + 1 = damas[2] + 2 (están en una diagonal) y damas[1] – 1 = damas[2] –2 (están en la otra diagonal). Si esto ocurre, incrementamos la columna de la nueva dama y se volverá a comprobar.
Diseño del algoritmo
algoritmo reinas
INICIO
const
n = 8.
tipo arreglo entero[1..n] listaDamas.
var
listaDamas damas.
entero i.
lógico solucion.
//Inicializar el arreglopara i = 1 hasta n hacer
damas[i] = 0.
ensaya(damas, 1, solucion).
si !solucion entonces
escribir(“No hay solución”).
sino
//Se deja al lector hacer la presentación del resultado.
FIN.
MIGUEL Á. TOLEDO MARTÍNEZ
ANEXO 1 1 - 51
lógico función posicionValida(E listaDamas damas; E entero i)
INICIO
var
entero j.
lógico valida.
valida = verdadero.
para j = 1 hasta i-1 hacer
Inicio
//Nose ataca en la columna
valida = valida y (damas[i] <> damas[j)].
//No se ataca en una diagonal
valida = valida y (damas[i] + i <> damas[j] + j).
//No se ataca en la otra diagonal
valida = valida y (damas[i] – i <> damas[j] - j).
Fin.
devolver(valida).
FIN.
procedimiento ensayar(E/S listaDamas damas; E entero i; S lógico solucion)
INICIO
si (i = n + 1) entoncessolucion = verdadero.
sino
Inicio
solucion = falso.
hacer
Inicio
damas[i] = damas[i] + 1.
si posicionValida(damas, i) entonces
ensayar(damas, i+1, solucion)
Fin.
mientras (¡solucion y (damas[i] = n)).
si !solucion entonces
damas[i] = 0.
Fin.
FIN.

Definición de una solución


Para el desarrollo del presente proyecto se seguirán los siguientes pasos:(1) Declarar la variable global *numero-de-reinas* que va a contener el número concreto de reinas.

(defvar *numero-de-reinas*)


(2) Representaremos un estado del problema, es decir, que haya k reinas colocadas en las últimas k columnas, como una lista (Pk ... P1) donde Pi indicala fila que ocupa la reina colocada en la i-ésima columna.

Usando esta representación, se definirán las siguientes funciones auxiliares:

-------------------------------------------------------------------

(es-estado-vacio ESTADO) que comprueba si no hay ninguna reina colocada.(defun es-estado-vacio (estado)
(null estado))




(coloca-reina FILA ESTADO) que devuelva el estado resultante de colocar la nueva reina, en la primera columna libre, en la fila i-ésima.

(defun coloca-reina (fila estado)(cons fila estado))



(quita-ultima ESTADO) que devuelva el estado resultante al quitar la última reina colocada.

(defun quita-ultima (estado)
(cdr estado))




(fila-ultima ESTADO) que...