La Reina N es el problema de colocar N reinas de ajedrez en un tablero de ajedrez N × N para que no haya dos reinas que se ataquen entre sí.
Por ejemplo, la siguiente es una solución para el problema de las 8 reinas.
Entrada: N = 4
Salida:
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
Explicación:
Las posiciones de las reinas son:
1 – {1, 2}
2 – {2, 4}
3 – {3, 1}
4 – {4, 3}
Como podemos ver, hemos colocado las 4 reinas
de manera que no haya dos reinas atacándose entre sí.
Entonces, la salida es correcta.
Entrada: N = 8
Salida:
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0
Enfoque: La idea es utilizar el Algoritmo de Escalada de Colinas .
- Si bien existen algoritmos como Backtracking para resolver el problema de N Queen , adoptemos un enfoque de IA para resolver el problema.
- Es obvio que AI no garantiza una solución globalmente correcta todo el tiempo, pero tiene una tasa de éxito bastante buena de alrededor del 97%, lo cual no está mal.
- Se dará una descripción de las nociones de todas las terminologías utilizadas en el problema y son las siguientes:
- Noción de un estado : un estado aquí en este contexto es cualquier configuración de las N reinas en el tablero NXN. Además, para reducir el espacio de búsqueda, agreguemos una restricción adicional de que solo puede haber una sola reina en una columna en particular. Un estado en el programa se implementa utilizando una array de longitud N, de modo que si state[i]=j , entonces hay una reina en el índice de columna i y en el índice de fila j .
- Noción de vecinos : los vecinos de un estado son otros estados con una configuración de tablero que difiere de la configuración del tablero del estado actual con respecto a la posición de una sola reina. Esta reina que difiere un estado de su vecina puede ser desplazada en cualquier lugar de la misma columna.
- Función de optimización o función de objetivo : sabemos que la búsqueda local es un algoritmo de optimización que busca en el espacio local para optimizar una función que toma el estado como entrada y da algún valor como salida. El valor de la función objetivo de un estado aquí en este contexto es el número de parejas de reinas que se atacan entre sí. Nuestro objetivo aquí es encontrar un estado con el valor objetivo mínimo. Esta función tiene un valor máximo de NC2 y un valor mínimo de 0.
Algoritmo:
- Comience con un estado aleatorio (es decir, una configuración aleatoria del tablero).
- Explore todos los vecinos posibles del estado actual y salte al vecino con el valor de objetivo más alto, si encuentra alguno. Si no existe un vecino, con un objetivo estrictamente superior al estado actual pero existe uno igual, entonces salte a cualquier vecino aleatorio (escape de hombro y/u óptimo local).
- Repita el paso 2, hasta que se encuentre un estado cuyo objetivo sea estrictamente más alto que todos los objetivos de sus vecinos, y luego vaya al paso 4.
- El estado así encontrado después de la búsqueda local es el óptimo local o el óptimo global. No hay forma de escapar de los óptimos locales, pero agregar un vecino aleatorio o un reinicio aleatorio cada vez que se encuentra un óptimo local aumenta las posibilidades de lograr un óptimo global (la solución a nuestro problema).
- Muestra el estado y regresa.
- Es fácilmente visible que el óptimo global en nuestro caso es 0 ya que es el número mínimo de parejas de reinas que pueden atacarse entre sí. Además, el reinicio aleatorio tiene una mayor probabilidad de lograr un óptimo global, pero aún usamos el vecino aleatorio porque nuestro problema de N reinas no tiene una gran cantidad de óptimos locales y el vecino aleatorio es más rápido que el reinicio aleatorio.
- Conclusión:
- Random Neighbor escapa de los hombros pero solo tiene una pequeña posibilidad de escapar de los óptimos locales.
- El reinicio aleatorio se escapa de los hombros y tiene una alta probabilidad de escapar de los óptimos locales.
A continuación se muestra la implementación del algoritmo Hill-Climbing:
CPP
// C++ implementation of the
// above approach
#include <iostream>
#include <math.h>
#define N 8
using namespace std;
// A utility function that configures
// the 2D array "board" and
// array "state" randomly to provide
// a starting point for the algorithm.
void configureRandomly(int board[][N],
int* state)
{
// Seed for the random function
srand(time(0));
// Iterating through the
// column indices
for (int i = 0; i < N; i++) {
// Getting a random row index
state[i] = rand() % N;
// Placing a queen on the
// obtained place in
// chessboard.
board[state[i]][i] = 1;
}
}
// A utility function that prints
// the 2D array "board".
void printBoard(int board[][N])
{
for (int i = 0; i < N; i++) {
cout << " ";
for (int j = 0; j < N; j++) {
cout << board[i][j] << " ";
}
cout << "\n";
}
}
// A utility function that prints
// the array "state".
void printState(int* state)
{
for (int i = 0; i < N; i++) {
cout << " " << state[i] << " ";
}
cout << endl;
}
// A utility function that compares
// two arrays, state1 and state2 and
// returns true if equal
// and false otherwise.
bool compareStates(int* state1,
int* state2)
{
for (int i = 0; i < N; i++) {
if (state1[i] != state2[i]) {
return false;
}
}
return true;
}
// A utility function that fills
// the 2D array "board" with
// values "value"
void fill(int board[][N], int value)
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = value;
}
}
}
// This function calculates the
// objective value of the
// state(queens attacking each other)
// using the board by the
// following logic.
int calculateObjective(int board[][N],
int* state)
{
// For each queen in a column, we check
// for other queens falling in the line
// of our current queen and if found,
// any, then we increment the variable
// attacking count.
// Number of queens attacking each other,
// initially zero.
int attacking = 0;
// Variables to index a particular
// row and column on board.
int row, col;
for (int i = 0; i < N; i++) {
// At each column 'i', the queen is
// placed at row 'state[i]', by the
// definition of our state.
// To the left of same row
// (row remains constant
// and col decreases)
row = state[i], col = i - 1;
while (col >= 0
&& board[row][col] != 1) {
col--;
}
if (col >= 0
&& board[row][col] == 1) {
attacking++;
}
// To the right of same row
// (row remains constant
// and col increases)
row = state[i], col = i + 1;
while (col < N
&& board[row][col] != 1) {
col++;
}
if (col < N
&& board[row][col] == 1) {
attacking++;
}
// Diagonally to the left up
// (row and col simultaneously
// decrease)
row = state[i] - 1, col = i - 1;
while (col >= 0 && row >= 0
&& board[row][col] != 1) {
col--;
row--;
}
if (col >= 0 && row >= 0
&& board[row][col] == 1) {
attacking++;
}
// Diagonally to the right down
// (row and col simultaneously
// increase)
row = state[i] + 1, col = i + 1;
while (col < N && row < N
&& board[row][col] != 1) {
col++;
row++;
}
if (col < N && row < N
&& board[row][col] == 1) {
attacking++;
}
// Diagonally to the left down
// (col decreases and row
// increases)
row = state[i] + 1, col = i - 1;
while (col >= 0 && row < N
&& board[row][col] != 1) {
col--;
row++;
}
if (col >= 0 && row < N
&& board[row][col] == 1) {
attacking++;
}
// Diagonally to the right up
// (col increases and row
// decreases)
row = state[i] - 1, col = i + 1;
while (col < N && row >= 0
&& board[row][col] != 1) {
col++;
row--;
}
if (col < N && row >= 0
&& board[row][col] == 1) {
attacking++;
}
}
// Return pairs.
return (int)(attacking / 2);
}
// A utility function that
// generates a board configuration
// given the state.
void generateBoard(int board[][N],
int* state)
{
fill(board, 0);
for (int i = 0; i < N; i++) {
board[state[i]][i] = 1;
}
}
// A utility function that copies
// contents of state2 to state1.
void copyState(int* state1, int* state2)
{
for (int i = 0; i < N; i++) {
state1[i] = state2[i];
}
}
// This function gets the neighbour
// of the current state having
// the least objective value
// amongst all neighbours as
// well as the current state.
void getNeighbour(int board[][N],
int* state)
{
// Declaring and initializing the
// optimal board and state with
// the current board and the state
// as the starting point.
int opBoard[N][N];
int opState[N];
copyState(opState,
state);
generateBoard(opBoard,
opState);
// Initializing the optimal
// objective value
int opObjective
= calculateObjective(opBoard,
opState);
// Declaring and initializing
// the temporary board and
// state for the purpose
// of computation.
int NeighbourBoard[N][N];
int NeighbourState[N];
copyState(NeighbourState,
state);
generateBoard(NeighbourBoard,
NeighbourState);
// Iterating through all
// possible neighbours
// of the board.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// Condition for skipping the
// current state
if (j != state[i]) {
// Initializing temporary
// neighbour with the
// current neighbour.
NeighbourState[i] = j;
NeighbourBoard[NeighbourState[i]][i]
= 1;
NeighbourBoard[state[i]][i]
= 0;
// Calculating the objective
// value of the neighbour.
int temp
= calculateObjective(
NeighbourBoard,
NeighbourState);
// Comparing temporary and optimal
// neighbour objectives and if
// temporary is less than optimal
// then updating accordingly.
if (temp <= opObjective) {
opObjective = temp;
copyState(opState,
NeighbourState);
generateBoard(opBoard,
opState);
}
// Going back to the original
// configuration for the next
// iteration.
NeighbourBoard[NeighbourState[i]][i]
= 0;
NeighbourState[i] = state[i];
NeighbourBoard[state[i]][i] = 1;
}
}
}
// Copying the optimal board and
// state thus found to the current
// board and, state since c++ doesn't
// allow returning multiple values.
copyState(state, opState);
fill(board, 0);
generateBoard(board, state);
}
void hillClimbing(int board[][N],
int* state)
{
// Declaring and initializing the
// neighbour board and state with
// the current board and the state
// as the starting point.
int neighbourBoard[N][N] = {};
int neighbourState[N];
copyState(neighbourState, state);
generateBoard(neighbourBoard,
neighbourState);
do {
// Copying the neighbour board and
// state to the current board and
// state, since a neighbour
// becomes current after the jump.
copyState(state, neighbourState);
generateBoard(board, state);
// Getting the optimal neighbour
getNeighbour(neighbourBoard,
neighbourState);
if (compareStates(state,
neighbourState)) {
// If neighbour and current are
// equal then no optimal neighbour
// exists and therefore output the
// result and break the loop.
printBoard(board);
break;
}
else if (calculateObjective(board,
state)
== calculateObjective(
neighbourBoard,
neighbourState)) {
// If neighbour and current are
// not equal but their objectives
// are equal then we are either
// approaching a shoulder or a
// local optimum, in any case,
// jump to a random neighbour
// to escape it.
// Random neighbour
neighbourState[rand() % N]
= rand() % N;
generateBoard(neighbourBoard,
neighbourState);
}
} while (true);
}
// Driver code
int main()
{
int state[N] = {};
int board[N][N] = {};
// Getting a starting point by
// randomly configuring the board
configureRandomly(board, state);
// Do hill climbing on the
// board obtained
hillClimbing(board, state);
return 0;
}
Producción:
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
Análisis de Complejidad
- La complejidad temporal de este algoritmo se puede dividir en tres partes:
- Cálculo del objetivo : el cálculo del objetivo implica iterar a través de todas las reinas a bordo y verificar el número. de atacar a las reinas, lo cual se hace con nuestra función de calcularObjetivo en tiempo O(N 2 ) .
- Selección de vecinos y número de vecinos : la descripción de vecinos en nuestro problema da un total de N (N-1) vecinos para el estado actual. El procedimiento de selección es el que mejor se ajusta y, por lo tanto, requiere iterar a través de todos los vecinos, que nuevamente es O(N 2 ) .
- Espacio de búsqueda: el espacio de búsqueda de nuestro problema consiste en un total de N N estados, correspondientes a todas las configuraciones posibles de las N Reinas a bordo. Tenga en cuenta que esto es después de tener en cuenta la restricción adicional de una reina por columna.
- Cálculo del objetivo : el cálculo del objetivo implica iterar a través de todas las reinas a bordo y verificar el número. de atacar a las reinas, lo cual se hace con nuestra función de calcularObjetivo en tiempo O(N 2 ) .
- Por lo tanto, la complejidad temporal del peor de los casos de nuestro algoritmo es O(N N ) . Pero, este peor de los casos rara vez ocurre en la práctica y, por lo tanto, podemos considerarlo tan bueno como cualquier otro algoritmo para el problema de N Queen. Por tanto, la complejidad temporal efectiva consiste únicamente en calcular el objetivo para todos los vecinos hasta una cierta profundidad (nº de saltos que realiza la búsqueda), que no depende de N. Por tanto, si la profundidad de búsqueda es d entonces la complejidad temporal es O(N 2 * N 2 * d) , que es O(d*N 4 ).
Publicación traducida automáticamente
Artículo escrito por prasantkpatel y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA