opcion1 = function(){
reinas = as.integer(readline("Número de reinas: "))Problema de las n - reinas
R
Heurística
Búsqueda
Problema de búsqueda de soluciones
El problema de las reinas de ajedrez o mejor conocido como el de las \(n\) - reinas, consiste en poner \(n\) reinas en un tablero de ajedrez de dimensión \(n\times n\) casillas (un grilla o matriz cuadrada) de tal manera que ninguna reina pueda “capturar” a otra (una reina puede capturar a otra si se encuentra en su misma fila, columna o diagonal). Por ende, la finalidad de problema es encontrar la (s) distribución (es) de las \(n\) reinas en el tablero.
Se aborda el problema bajo la perspectiva de búsqueda con un enfoque desinformado, es decir, no conocemos característica alguna de la solución (estado final). Esto implica, que debemos usar las condiciones descritas en problema para poder evaluar si una solución a proponer es factible.
A continuación se da a conocer dos opciones posibles para solucionar este problema. Sin embargo,
Opción 1
Este enfoque evalúa los caminos uno a uno, hasta determinar si constituyen una posible solución. En primer lugar, se declara la función para definir la cantidad de reinas que se desean colocar en el tablero.
A continuación, se define una función que evalúa si una reina dada las condiciones de “captura”. En los parámetros de la función se pide el tablero aux.square (con las reinas ya colocadas), la fila i, la columna j en donde se desea colocar una reina, y el valor de la reina (se considera 1 como el valor que representan a una reina en la casilla \(i,j\), por defecto las casillas el tablero son 0).
possible = function(aux.square,i,j,valor){Luego, se asigna a la casilla candidata de posible posición el valor de 1 (no hay otra opción), además se crean las variables de aux.col y aux.row, las cuales determinan si el aux.square cumple con el requisito de que las reinas no se capturen en las filas y columnas. Este requisito se determina calculando la suma de de las filas y columnas, ya que al estar compuesto por ceros y unos, un valor superior a 1 indica que el criterio no se cumple.
aux.square[i,j] = valor
aux.col = apply(aux.square, 2, FUN = function(colum){
if(sum(colum) <= 1) return(TRUE)
else return(FALSE)
})
aux.col = ifelse(sum(!aux.col) == 0, TRUE, FALSE)
aux.row = apply(aux.square, 1, FUN = function(rows){
if(sum(rows) <= 1) return(TRUE)
else return(FALSE)
})
aux.row = ifelse(sum(!aux.row) == 0, TRUE, FALSE)Del mismo modo, se desea determinar las sumas en las diagonales del tablero (no es necesario considerar una diagonal de 1 casilla, pero de todas formas no afecta el procedimiento del script). La variable diag.principales guarda el valor de verdadero o falso respecto a la suma de las casillas de las diagonales principales (al igual que las filas y columnas, estas no deben sumar más de 1).
diag.principales = c(0,0)
for (i in 1:queens) {
diag.principales[1] = sum(diag.principales[1],aux.square[i,i])
diag.principales[2] = sum(diag.principales[2],aux.square[i,(queens - i + 1)])
}
diag.principales = ifelse(diag.principales <= 1, TRUE, FALSE)
diag.principales = ifelse(sum(diag.principales) == 2, TRUE, FALSE)Para las “diagonales secundarias” (corresponden a todas las diagonales que se pueda formar y que no sean las principales) es posible determinarlas a partir de casillas de la primer fila de la matriz, sin considerar los extremos, ya que como se comentó, no es necesario considerar las diagonales compuestas por una casillas (esquinas).
Los casillas de la primera fila que permite determinar todas las diagonales secundarias se guardará en la variable key.points.
key.points = matrix(c(rep(1,(queens - 2)), seq(2,(queens - 1))),
ncol = 2, nrow = (queens - 2))La función diags() que determina las diagonales secundarias y verifica las sumas de estas mediante la función suma.diag(). La función suma.diag() recibe como argumento las diagonales secundarias y retorna si es verdadero o falso que la suma de las casillas de las componen es menor o igual a 1.
Por otro lado, la variable report.diag guarda los valores de las diagonales que se generan a partir de los key.points. La relación de como se determinan estás casillas, está expresada en las variables first.diag, second.diag, third.diag y fourth.diag.
Luego la variable aux.sumas guarda los los resultados de la función suma.diag() ya mencionada, cuando recibe de argumento la variable report.diag.
diags = function(aux.key.points){
suma.diag = function(M){
x = M[1,]; y = M[2,]
# Puntos entre los extremos de las diagonales,
# se obtiene restando las coordenadas de fila y sumando (1,1)
n = abs(y[1] - x[1]) - 1
suma = aux.square[x[1],x[2]] + aux.square[y[1],y[2]]
if(n >0){
for (i in 1:n) {
if(x[1] < y[1] & x[2] > y[2]) suma = suma + aux.square[(x[1]+i),(x[2]-i)]
if(x[1] < y[1] & x[2] < y[2]) suma = suma + aux.square[(x[1]+i),(x[2]+i)]
if(x[1] > y[1] & x[2] < y[2]) suma = suma + aux.square[(x[1]-i),(x[2]+i)]
if(x[1] > y[1] & x[2] > y[2]) suma = suma + aux.square[(x[1]-i),(x[2]-i)]
}
}
if(suma <= 1) return(TRUE)
else return(FALSE)
}
report.diag = list()
# Se recorre la matriz de puntos claves, por cada uno
# se busca las diagonales que se generan
for (i in 1:dim(aux.key.points)[1]) {
first.diag = rbind(aux.key.points[i,],c(aux.key.points[i,2],aux.key.points[i,1]))
second.diag = rbind(first.diag[2,], first.diag[2,] + c(1,1)*(queens - aux.key.points[i,2]))
third.diag = rbind(second.diag[2,], c(second.diag[2,2],second.diag[2,1]))
fourth.diag = rbind(third.diag[2,], first.diag[1,])
aux.diags = list(first.diag, second.diag,third.diag, fourth.diag)
aux.sumas = lapply(aux.diags, function(x){
return(suma.diag(x))
})
report.diag[[i]] = unlist(aux.sumas)
}
return(report.diag)
}El resultado de la función diags() se guarda en la variable diag.secundarias, que finalmente contiene la suma de cada diagonal secundaria, para luego verificar que en cada una de ellas se cumple el criterio de que no sea mayor a 1, es decir que las reinas no se captura entre si.
diag.secundarias = diags(key.points)
diag.secundarias = ifelse(sum(!unlist(diag.secundarias)) == 0, TRUE, FALSE)Los criterios sobre las diagonales son unificados como una único resultado en la variable diagonales. En este punto finaliza la función possible(), retornando un valor de verdadero o falso sobre el cumplimiento de los criterios (filas, columnas y diagonales).
diagonales = ifelse(diag.principales == TRUE & diag.secundarias == TRUE, TRUE, FALSE)
# Verificación en conjunto
if(aux.col == TRUE & aux.row == TRUE & diagonales == TRUE) return(TRUE)
else return(FALSE)
}Para finalizar, se declara la función solve() (recursiva), la cual evalúa en orden las casillas del tablero (por fila de izquierda a derecha) determinando si son posiciones admisibles para una solución. De este modo, la función sigue en proceso hasta verificar que la cantidad de reinas en el tablero es \(n\). Además, no se detiene al encontrar una única solución, sino que determina todas las soluciones posibles y las guarda en las variable soluciones.
solve = function(board){
for (i in 1:queens) {
for (j in 1:queens) {
if(board[i,j] == 0){
if(possible(board,i,j,1)){ # Posición admisible
board[i,j] = 1
if(sum(board) == queens){ # Criterio de solución
solutions[[length(soluciones)+1]] <<- board
break()
}
solve(board) # Criterio recursivo
board[i,j] = 0
}
}
}
# Criterio de no admisibilidad
if(sum(board[i,]) == 0) return()
}
}
soluciones = list()
square = matrix(0,ncol = queens, nrow = queens)
solve(square)
print(paste("All solutions: ",length(soluciones)))
return(soluciones)
}Al inicio comentamos que la búsqueda es en profundidad, esto se debe a que la función solve() evalúa las posiciones de las reinas, según se recorren los ciclos for, de este modo, las posibles soluciones finales se recorren 1 a 1 en cada iteración.
Para ejemplificar, evaluemos el problema con 5 reinas.
# Omití el argumento interactivo (readLine), para efectos del ejemplo
r1 = opcion1(5) # Imprime el total de soluciones encontradas
## [1] "Cantidad de soluciones: 10"
r1[1] # La primera solución obtenida
## [[1]]
## [,1] [,2] [,3] [,4] [,5]
## [1,] 1 0 0 0 0
## [2,] 0 0 1 0 0
## [3,] 0 0 0 0 1
## [4,] 0 1 0 0 0
## [5,] 0 0 0 1 0Como se puede aprecia, la solución muestra la distribución de las reinas en el tablero, en la cual, el 1 indica la presencia de una reina y el 0 la ausencia.
Opción 2
En primer lugar, se declara la función para definir la cantidad de reinas que se desean colocar en el tablero.
option2 = function(){
n = as.integer(readline("Número de reinas?: "))
solutions = list()Luego, a diferencia de la opción 1 se tiene una única función (Reinas()), más breve, que determina las posiciones de las reinas. Para ello, se trabaja con la siguiente propiedad: “se considera como solución un vector que contenga la posición de cada reina en una determinada columna, siendo la posición en el vector la fila que le corresponde a dicha reina”.
El argumento que nos permite deducir esto lo puedes encontrar en estos apuntes. En el fondo, se recurre al hecho de que las soluciones pueden ordenarse convenientemente en un vector, esto permite que sea más fácil evaluar los distintas posibles soluciones.
Volviendo a la función Reinas(), la variable diags guarda las casillas correspondientes a la proyección de las diagonales desde una fila a otra (ejemplo: desde la fila 1 y 2, a la fila 3), esto “genera” casillas que están fuera de la matriz, pero las cuales son eliminadas en la variable posibles.columnas que guarda las casillas en donde es admisible la posición de una reina. Esto permite resumir el problema a una “proyección de diagonales”, eliminando los criterios de filas y columnas (genial!).
Finalmente se hace uso de la recursividad mediante la función apply(). El resto de código imprime la cantidad total de soluciones y guarda las soluciones en forma matricial.
Reinas = function(posiciones) {
# Imprime la solución al momento de obtener 8 posiciones
# que cumplen las condiciones
if (length(posiciones) == n) {
soluciones[[length(soluciones)+1]] <<- posiciones
}
# Se definen las columnas posibles en donde puede ir una reina
posibles.columnas = setdiff(1:n, posiciones)
# Se definen las diagonales matriciales en donde no puede ir una reina
out.diags = seq(length(posiciones), 1)
diags = c(posiciones + out.diags, posiciones - out.diags)
diags = diags[diags >= 1 & diags <= n]
# Se eliminan las casillas diagonales, de las casillas posibles
# en donde ubicar a una reina
posibles.columnas = setdiff(posibles.columnas, diags)
# Para cada posibilidad se evalúa nuevamente la función
if(length(posibles.columnas > 0)){
apply(matrix(posibles.columnas), 1, FUN = function(p){
Reinas(c(posiciones,p)) # Se añaden las opciones
# posibles a cada iteración
})
}
}
Reinas(c())
# Se imprime la cantidad de soluciones posibles
print(paste("Cantidad de soluciones: ",length(soluciones)))
# Se transforman las soluciones en matrices
soluciones = lapply(soluciones, function(sol){
M = matrix(0, ncol = n, nrow = n)
for (i in 1:n) {
M[i,sol[i]] = 1
}
return(M)
})
# Se retornan las matrices solución
return(soluciones)
}Comparemos lo obtenido con la opción 1.
r2 = opcion2(5)
## [1] "All solutions: 10"
r2[1]
## [[1]]
## [,1] [,2] [,3] [,4] [,5]
## [1,] 1 0 0 0 0
## [2,] 0 0 1 0 0
## [3,] 0 0 0 0 1
## [4,] 0 1 0 0 0
## [5,] 0 0 0 1 0Como se puede apreciar, el resultado dado por la opción 1. Esto se debe a que los caminos se recorren en “orden”, a esto se le llama solución lexicográfica.
Comentarios
Los códigos son simplemente ejemplos, ya que para la primera opción es posible ocupar los mismos criterios que en la segunda. Es por esto, que la idea es proporcionar distintas alternativas, de tal manera que puedan aplicar y entender sus propias propuestas.