Задача о восьми ферзях состоит в том, чтобы найти решение, позволяющее разместить по ферзю в каждом ряду шахматной доски так, чтобы никакие два ферзя не могли атаковать друг друга. Проблему можно решить с помощью рекурсии. В этом разделе мы познакомим вас с общим методом разработки алгоритмов, называемым обратным отслеживанием для решения этой проблемы. Подход с возвратом ищет решение-кандидат постепенно, отказываясь от этого варианта, как только он определяет, что
кандидат не может быть действительным решением, а затем ищет нового кандидата.

Двумерный массив можно использовать для представления шахматной доски. Однако, поскольку в каждой строке может быть только один ферзь, для обозначения положения ферзя в строке достаточно использовать одномерный массив. Таким образом, вы можете определить массив queens как:

int[] ферзи = новое int[8];

Назначьте j для queens[i] для обозначения того, что ферзь помещен в строку i и столбец j. На рисунке ниже (a) показано содержимое массива ферзей для шахматной доски, показанного на рисунке ниже (b).

Поиск начинается с первой строки с k = 0, где k — индекс текущей рассматриваемой строки. Алгоритм проверяет, может ли ферзь быть помещен в j_th столбец в строке для _j = 0, 1, ... , 7, в этом порядке. Поиск реализован следующим образом:

• В случае успеха он продолжает поиск места для ферзя в следующем ряду. Если текущая строка является последней, решение найдено.
• В случае неудачи происходит возврат к предыдущей строке и продолжение поиска нового места размещения в следующем столбце предыдущей строки.
• Если алгоритм возвращается к первой строке и не может найти новое место для ферзя в этой строке, решение не может быть найдено.

Приведенный ниже код представляет программу, которая отображает решение задачи о восьми ферзях.

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 



Программа вызывает search() (строка 20) для поиска решения. Изначально ни в одном ряду не ставятся ферзи (строка 16). Теперь поиск начинается с первой строки с k = 0 (строка 53) и находит место для ферзя (строка 56). В случае успеха поместите его в строку (строка 61) и рассмотрите следующую строку (строка 62). В случае неудачи вернитесь к предыдущей строке (строки 58–59).

Метод findPosition(k) ищет возможную позицию для размещения ферзя в строке k, начиная с queen[k] 1 (строка 73) . Он проверяет, можно ли поставить ферзя на start, start 1, . . . , и 7 в этом порядке (строки 75–78). Если возможно, верните индекс столбца (строка 77); в противном случае верните -1 (строка 80).

Метод isValid(row, columns) вызывается, чтобы проверить, не вызывает ли размещение ферзя в указанной позиции конфликт с ферзями, размещенными ранее (строка 76). Это гарантирует, что ни один ферзь не будет помещен в тот же столбец (строка 86), в верхнюю левую диагональ (строка 87) или в верхнюю правую диагональ (строка 88), как показано на рисунке ниже.