O problema das Oito Rainhas é encontrar uma solução para colocar uma rainha em cada linha de um tabuleiro de xadrez, de modo que duas rainhas não possam atacar uma à outra. O problema pode ser resolvido usando recursão. Nesta seção, apresentaremos uma técnica comum de design de algoritmo chamada backtracking para resolver este problema. A abordagem de retrocesso procura uma solução candidata de forma incremental, abandonando essa opção assim que determina que o
candidato não pode ser uma solução válida e então procura um novo candidato.

Você pode usar uma matriz bidimensional para representar um tabuleiro de xadrez. Entretanto, como cada linha pode ter apenas uma rainha, é suficiente usar um array unidimensional para denotar a posição da rainha na linha. Assim, você pode definir o array queens como:

int[] rainhas = novo int[8];

Atribua j a rainhas[i] para denotar que uma rainha é colocada na linha i e na coluna j. A figura abaixo (a) mostra o conteúdo do array queens para o tabuleiro de xadrez na figura abaixo (b).

A pesquisa começa na primeira linha com k = 0, onde k é o índice da linha atual que está sendo considerada. O algoritmo verifica se uma rainha pode ser colocada na j_ésima coluna da linha para _j = 0, 1, ..., 7, nesta ordem. A pesquisa é implementada da seguinte forma:

• Se for bem-sucedido, ele continua a procurar uma colocação para uma rainha na próxima linha. Se a linha atual for a última linha, uma solução será encontrada.
• Se não for bem-sucedido, ele volta para a linha anterior e continua procurando um novo canal na próxima coluna da linha anterior.
• Se o algoritmo voltar para a primeira linha e não conseguir encontrar uma nova colocação para uma rainha nesta linha, nenhuma solução poderá ser encontrada.

O código abaixo fornece o programa que exibe uma solução para o problema das Oito Rainhas.

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 



O programa invoca search() (linha 20) para procurar uma solução. Inicialmente, nenhuma rainha é colocada em nenhuma linha (linha 16). A busca agora começa na primeira linha com k = 0 (linha 53) e encontra um lugar para a rainha (linha 56). Se tiver sucesso, coloque-o na linha (linha 61) e considere a próxima linha (linha 62). Se não tiver sucesso, volte para a linha anterior (linhas 58–59).

O método findPosition(k) procura uma possível posição para colocar uma rainha na linha k começando em queen[k] 1 (linha 73) . Ele verifica se uma rainha pode ser colocada em start, start 1, . . . e 7, nesta ordem (linhas 75–78). Se possível, retorne o índice da coluna (linha 77); caso contrário, retorne -1 (linha 80).

O método isValid(row, column) é chamado para verificar se colocar uma rainha na posição especificada causa um conflito com as rainhas colocadas anteriormente (linha 76). Garante que nenhuma rainha seja colocada na mesma coluna (linha 86), na diagonal superior esquerda (linha 87) ou na diagonal superior direita (linha 88), conforme mostrado na Figura abaixo.