Lösung des Acht-Damen-Problems mithilfe von Backtracking

Das Acht-Damen-Problem besteht darin, eine Lösung zu finden, um in jeder Reihe auf einem Schachbrett eine Dame so zu platzieren, dass sich keine zwei Damen gegenseitig angreifen können. Das Problem kann durch Rekursion gelöst werden. In diesem Abschnitt stellen wir eine gängige Algorithmusentwurfstechnik namens Backtracking zur Lösung dieses Problems vor. Der Backtracking-Ansatz sucht schrittweise nach einer Kandidatenlösung und verwirft diese Option, sobald festgestellt wird, dass die
Der Kandidat kann unmöglich eine gültige Lösung sein und sucht dann nach einem neuen Kandidaten.

Sie können ein zweidimensionales Array verwenden, um ein Schachbrett darzustellen. Da jede Reihe jedoch nur eine Königin haben kann, reicht es aus, ein eindimensionales Array zu verwenden, um die Position der Königin in der Reihe anzugeben. Daher können Sie das Array queens wie folgt definieren:

int[] queens = new int[8];

Weisen Sie j queens[i] zu, um anzugeben, dass eine Königin in Zeile i und Spalte j platziert wird. Abbildung unten (a) zeigt den Inhalt des Arrays Damen für das Schachbrett in Abbildung unten (b).

Die Suche beginnt in der ersten Zeile mit k = 0, wobei k der Index der aktuell berücksichtigten Zeile ist. Der Algorithmus prüft, ob möglicherweise eine Königin in der j_ten Spalte in der Zeile für _j = 0, 1, ... , 7 in dieser Reihenfolge platziert werden kann. Die Suche wird wie folgt implementiert:

• Bei Erfolg wird weiterhin nach einem Platz für eine Königin in der nächsten Reihe gesucht. Wenn die aktuelle Zeile die letzte Zeile ist, wird eine Lösung gefunden.
• Wenn dies nicht erfolgreich ist, wird zur vorherigen Zeile zurückgekehrt und die Suche nach einer neuen Platzierung in der nächsten Spalte der vorherigen Zeile fortgesetzt.
• Wenn der Algorithmus zur ersten Reihe zurückkehrt und in dieser Reihe keine neue Platzierung für eine Königin finden kann, kann keine Lösung gefunden werden.

Der folgende Code gibt das Programm an, das eine Lösung für das Eight Queens-Problem anzeigt.

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 < SIZE; i++)
            for(int j = 0; j < SIZE; j++) {
                chessBoard.add(labels[i][j] = new Label(), i, j);
                labels[i][j].setStyle("-fx-border-color: black");
                labels[i][j].setPrefSize(55, 55);
            }

        // Display queens
        Image image = new Image("file:C:/Users/Paul/development/MyJavaFX/src/application/image/lo.jpg");
        for(int i = 0; i < SIZE; i++)
            labels[i][queens[i]].setGraphic(new ImageView(image));

        // Create a scene and place it in the stage
        Scene scene = new Scene(chessBoard, 55 * SIZE, 55 * SIZE);
        primaryStage.setTitle("EightQueens"); // Set the stage title
        primaryStage.setScene(scene); // Place the scene in the stage
        primaryStage.show(); // Display the stage
    }

    public static void main(String[] args) {
        Application.launch(args);
    }

    /** Search for a solution */
    private boolean search() {
        // k - 1 indicates the number of queens placed so far
        // We are looking for a position in the kth row to place a queen
        int k = 0;
        while(k >= 0 && k < SIZE) {
            // Find a position to place a queen in the kth row
            int j = findPosition(k);
            if(j < 0) {
                queens[k] = -1;
                k--; // back track to the previous row
            } else {
                queens[k] = j;
                k++;
            }
        }

        if(k == -1)
            return false; // No solution
        else
            return true; // A solution is found
    }

    public int findPosition(int k) {
        int start = queens[k] + 1; // Search for a new placement

        for(int j =start; j < SIZE; j++) {
            if(isValid(k, j))
                return j; // (k, j) is the place to put the queen now
        }

        return -1;
    }

    /** Return true is a queen can be placed at (row, column) */
    public boolean isValid(int row, int column) {
        for(int i = 1; i <= row; i++)
            if(queens[row - i] == column // Check column
            || queens[row - i] == column - i // Check upleft diagonal
            || queens[row - i] == column + i) // Check upright diagonal
                return false; // There is a conflict
        return true; // No conflict
    }

}

Das Programm ruft search() (Zeile 20) auf, um nach einer Lösung zu suchen. Zunächst werden in keiner Reihe Damen platziert (Zeile 16). Die Suche beginnt nun in der ersten Zeile mit k = 0 (Zeile 53) und findet einen Platz für die Königin (Zeile 56). Wenn es erfolgreich ist, platzieren Sie es in der Zeile (Zeile 61) und betrachten Sie die nächste Zeile (Zeile 62). Wenn dies nicht gelingt, kehren Sie zur vorherigen Zeile zurück (Zeilen 58–59).

Die Methode findPosition(k) sucht nach einer möglichen Position, um eine Königin in Reihe k zu platzieren, beginnend mit queen[k] + 1 (Zeile 73). ). Es wird geprüft, ob eine Königin bei Start, Start + 1, platziert werden kann. . . , und 7, in dieser Reihenfolge (Zeilen 75–78). Wenn möglich, geben Sie den Spaltenindex zurück (Zeile 77); Andernfalls geben Sie -1 (Zeile 80) zurück.

Die Methode isValid(row, Column) wird aufgerufen, um zu prüfen, ob das Platzieren einer Königin an der angegebenen Position einen Konflikt mit den zuvor platzierten Königinnen verursacht (Zeile 76). Dadurch wird sichergestellt, dass keine Königin in derselben Spalte (Zeile 86), in der oberen linken Diagonale (Zeile 87) oder in der oberen rechten Diagonale (Zeile 88) platziert wird, wie in der Abbildung unten gezeigt.

Das obige ist der detaillierte Inhalt vonLösung des Acht-Damen-Problems mithilfe von Backtracking. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!