여덟 여왕 문제는 두 여왕이 서로 공격할 수 없도록 체스판의 각 행에 여왕을 배치하는 해결책을 찾는 것입니다. 재귀를 사용하여 문제를 해결할 수 있습니다. 본 절에서는 이 문제를 해결하기 위한 역추적이라는 일반적인 알고리즘 설계 기법을 소개합니다. 역추적 접근 방식은 후보 솔루션을 점진적으로 검색하고
가 결정되는 즉시 해당 옵션을 포기합니다. 후보는 유효한 솔루션이 될 수 없으며 새로운 후보를 찾습니다.

2차원 배열을 사용하여 체스판을 나타낼 수 있습니다. 그러나 각 행에는 하나의 퀸만 있을 수 있으므로 1차원 배열을 사용하여 행에서 퀸의 위치를 ​​나타내는 것으로 충분합니다. 따라서 queens 배열을 다음과 같이 정의할 수 있습니다:

int[] 퀸즈 = 새로운 int[8];

j를 queens[i]에 할당하여 퀸이 행 i와 열 j에 배치됨을 나타냅니다. 아래 그림 (a)는 아래 그림 (b)의 체스판에 대한 queens 배열의 내용을 보여줍니다.

검색은 k = 0인 첫 번째 행에서 시작됩니다. 여기서 k는 고려 중인 현재 행의 인덱스입니다. 알고리즘은 _j = 0, 1, ... , 7에 대한 행의 j_번째 열에 여왕이 이 순서대로 배치될 수 있는지 여부를 확인합니다. 검색은 다음과 같이 구현됩니다:

• 성공하면 다음 행에서 퀸을 위한 배치를 계속 검색합니다. 현재 행이 마지막 행인 경우 솔루션을 찾습니다.
• 성공하지 못한 경우 이전 행으로 돌아가 이전 행의 다음 열에서 새 게재위치를 계속 검색합니다.
• 알고리즘이 첫 번째 행으로 역추적하고 이 행에서 여왕에 대한 새로운 배치를 찾을 수 없는 경우 해결책을 찾을 수 없습니다.

아래 코드는 Eight Queens 문제에 대한 솔루션을 표시하는 프로그램을 제공합니다.

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) 메소드는 queen[k] 1부터 시작하여 k 행에 퀸을 배치할 수 있는 가능한 위치를 검색합니다(line 73). . 퀸이 start, start 1, 에 배치될 수 있는지 확인합니다. . . , 및 7를 이 순서대로 사용합니다(75-78행). 가능하다면 열 인덱스를 반환합니다(77행). 그렇지 않으면 -1를 반환합니다(라인 80).

isValid(행, 열) 메소드는 지정된 위치에 퀸을 배치하면 이전에 배치된 퀸과 충돌이 발생하는지 여부를 확인하기 위해 호출됩니다(라인 76). 아래 그림과 같이 동일한 열(86행), 왼쪽 위 대각선(87행) 또는 오른쪽 위 대각선(88행)에 퀸이 배치되지 않도록 합니다.