El problema de las N reinas es un problema que se basa en colocar N reinas de ajedrez en un tablero de ajedrez de medidas N × N para que no se ataquen dos reinas.
Un ejemplo de esto es la siguiente imagen.
Solución con Backtracking
Podemos utilizar una solución basada en la técnica del retroceso debido a que a diferencia de técnicas como programación voraz no podemos generar una secuencia de pasos triviales que generen una respuesta, por lo tanto, debemos generar múltiples soluciones, en caso de que una secuencia de pasos no lleve a una solución podemos retroceder a un punto donde la respuesta estaba incompleta pero parcialmente correcta.
Podríamos definir un código, en este caso vamos a utilizar C# para que nos ayude a entender más a profundidad este problema, identificando cada componente de este mismo incluyendo nuestras variables de decisión
Dominio del algoritmo
Este algoritmo estaría definido para una matriz de enteros restringidos a 1 y 0 de medidas N por N, por lo tanto, solo nos podríamos mover dentro de esta misma con los índices de fila y columna, esta matriz simboliza el tablero.
Entradas del algoritmo
Este algoritmo recibe una matriz de enteros restringidos a 1 y 0 de medidas N por N y un entero que indica en qué columna debemos empezar, esta matriz simboliza el tablero.
Podríamos definir los parámetros del algoritmo como en la siguiente imaginen.
Salidas del algoritmo
El algoritmo devuelve un Booleano que indica si el algoritmo encontró una solución al problema, esta respuesta se dará bajo 2 condiciones, si el iterador de las columnas alcanza su máximo esto indica que el algoritmo encontró una solución.
El otro escenario sería que el algoritmo no encuentre una solución, esto se daría a que el algoritmo estando ubicado en la primera columna de la matriz llegó a la última fila y no encontró una solución por ende devolvería falso.
Proceso resolutivo del algoritmo
Necesitamos un ciclo que nos pueda hacer navegar entre los posibles inicios de las posibles soluciones, esto se haría navegando las filas de matriz, específicamente este ciclo terminaría cuando ya no quedan más filas por analizar en la primera columna.
Al inicio de este ciclo necesitamos saber si la casilla en la que estamos poniendo la reina es una casilla válida para esto necesitamos una función que valide que no se incumple la idea del problema, la cual es que ninguna reina se ataque, esta función recibe el tablero, la fila y la columna actuales, en esta función se revisan las diagonales y las filas en la que está la reina actual para determinar si se puede poner en esa casilla o no.
El valor booleano que devuelve esta función determina si debemos probar en una fila diferente, esta variable es una variable de decisión.
Dentro de este if si la posición fuese valida ponemos la reina en esa casilla, poniendo un 1 en esa posición de la matriz
Luego de asignar la reina a esa determinada ocupamos utilizar de nuevo Resolver para utilizarla como variable de decisión, esto debido a que necesitamos ir generando soluciones parciales hasta tener una respuesta, si no se encuentra una solución se regresa a la columna anterior y se prueba otra fila.
El algoritmo completo se vería de esta manera:
a:
Referencias
-
N Queen Problem Implementation in C#. Recuperado 24 junio 2020, de https://www.programmingalgorithms.com/algorithm/n-queen-problem/
-
N Queen Problem Recuperado 24 junio 2020, de https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/