El problema de las ocho reinas consiste en encontrar una solución para colocar una reina en cada fila de un tablero de ajedrez de modo que dos reinas no puedan atacarse entre sí. El problema se puede resolver mediante recursividad. En esta sección, presentaremos una técnica de diseño de algoritmo común llamada retroceso para resolver este problema. El enfoque de retroceso busca una solución candidata de forma incremental, abandonando esa opción tan pronto como determina que
El candidato no puede ser una solución válida y luego busca un nuevo candidato.

Puedes utilizar una matriz bidimensional para representar un tablero de ajedrez. Sin embargo, dado que cada fila sólo puede tener una reina, es suficiente utilizar una matriz unidimensional para indicar la posición de la reina en la fila. Por lo tanto, puede definir la matriz queens como:

int[] reinas = nuevo int[8];

Asigne j a reinas[i] para indicar que se coloca una reina en la fila i y en la columna j. La figura siguiente (a) muestra el contenido de la matriz reinas para el tablero de ajedrez en la figura siguiente (b).

La búsqueda comienza desde la primera fila con k = 0, donde k es el índice de la fila actual que se está considerando. El algoritmo comprueba si es posible colocar una reina en la j_ésima columna de la fila para _j = 0, 1, ..., 7, en este orden. La búsqueda se implementa de la siguiente manera:

• Si tiene éxito, continúa buscando una ubicación para una reina en la siguiente fila. Si la fila actual es la última fila, se encuentra una solución.
• Si no tiene éxito, retrocede a la fila anterior y continúa buscando una nueva ubicación en la siguiente columna de la fila anterior.
• Si el algoritmo retrocede a la primera fila y no puede encontrar una nueva ubicación para una reina en esta fila, no se puede encontrar ninguna solución.

El siguiente código proporciona el programa que muestra una solución para el problema de las ocho reinas.

package application;
import javafx.application.Application;
import javafx.geometry.Pos;
import javafx.stage.Stage;
import javafx.scene.Scene;
import javafx.scene.control.Label;
import javafx.scene.image.Image;
import javafx.scene.image.ImageView;
import javafx.scene.layout.GridPane;

public class EightQueens extends Application {
    public static final int SIZE = 8; // The size of the chess board
    // queens are placed at (i, queens[i])
    // -1 indicates that no queen is currently placed in the ith row
    // Initially, place a queen at (0, 0) in the 0th row
    private int[] queens = {-1, -1, -1, -1, -1, -1, -1, -1};

    @Override // Override the start method in the Application class
    public void start(Stage primaryStage) {
        search(); // Search for a solution

        // Display chess board
        GridPane chessBoard = new GridPane();
        chessBoard.setAlignment(Pos.CENTER);
        Label[][] labels = new Label[SIZE][SIZE];
        for(int i = 0; i = 0 && k 



El programa invoca search() (línea 20) para buscar una solución. Inicialmente, no se colocan reinas en ninguna fila (línea 16). La búsqueda ahora comienza desde la primera fila con k = 0 (línea 53) y encuentra un lugar para la reina (línea 56). Si tiene éxito, colóquelo en la fila (línea 61) y considere la siguiente fila (línea 62). Si no tiene éxito, retroceda a la fila anterior (líneas 58–59).

El método findPosition(k) busca una posible posición para colocar una reina en la fila k comenzando desde queen[k] 1 (línea 73) . Comprueba si se puede colocar una reina en inicio, inicio 1,. . . y 7, en este orden (líneas 75 a 78). Si es posible, devuelva el índice de la columna (línea 77); de lo contrario, devuelva -1 (línea 80).

Se llama al método isValid(fila, columna) para verificar si colocar una reina en la posición especificada causa un conflicto con las reinas colocadas anteriormente (línea 76). Garantiza que ninguna reina se coloque en la misma columna (línea 86), en la diagonal superior izquierda (línea 87) o en la diagonal superior derecha (línea 88), como se muestra en la Figura siguiente.