Problema de las cuatro reinas
| ||||
Problema de las cuatro Reinas
Idea del algoritmo
La idea del algoritmo consiste en colocar las fichas de manera sucesiva en las columnas. Cuando no sea posible colocar una ficha en una columna, retrocedemos y ajustamos la ficha de la columna anterior.
Algoritmo de solución mediante el retroceso o búsqueda en profundidad
Este algoritmo utiliza el retroceso para buscar un arreglo de cuatro fichas en una cuadricula de 4x4 de modo que no haya dos fichas en la misma fila, la misma columna, o en la diagonal.
Entrada: Un arreglo row de tamaño 4
Salida: true , si existe una solución o false, si no existe solución
procedure cuatro_reinas (row)
k:=1
row(1):=0
while k>0 do
begin
row(k):=row(k+1)
while row(k) <=4 and hay conflicto en la columna k, fila row(k) do
row(k)=row(k+1)
if row(k) <=4 then
if k=4 then
return (true)
else
begin
k:=k+1
row(k):=0
end
else
k:=k-1
end
return(false)
end cuatro_reinas
La siguiente gráfica muestra el árbol generado por el algoritmo anterior en la búsqueda de una solución al problema, donde la solución aparece en el vértice 8.
Este algoritmo funciona perfectamente para n reinas con n>=4 pues para n=2 o n=3 no existe solución.
El retroceso o búsqueda a profundidad es de particular interés en problemas como el de las n reinas, donde lo único que se quiere es una solución. Como la solución aparece en un vértice terminal, al pasar a los vértices terminales lo más pronto posible, en general evita la generación de muchos vértices innecesarios.
Fuentes
- Johnsonbaugh, Richard. Matemáticas Discretas. Volumen II,cuarta edición.Editorial Felix Varela, La Habana, 2006. Pág 396.
- Información ofrecida por MSc. José Ramón Ávila Cruz (JC Puerto Padre V)
