So verwenden Sie den Eight Queens Problem-Algorithmus in C++

So verwenden Sie den Acht-Damen-Problemalgorithmus in C++

Das Acht-Damen-Problem ist ein klassisches Algorithmusproblem, bei dem acht Königinnen auf einem 8x8-Schachbrett platziert werden müssen, sodass sich keine zwei Königinnen gegenseitig angreifen können, d. h. zwei beliebige Königinnen darf nicht in derselben Zeile, Spalte oder Diagonale liegen. Es gibt viele Algorithmen zur Lösung des Acht-Damen-Problems. Eine der häufigsten Methoden ist die Verwendung des Backtracking-Algorithmus. In diesem Artikel wird erläutert, wie die Sprache C++ zum Implementieren des Algorithmus des Acht-Damen-Problems verwendet wird, und es werden spezifische Codebeispiele bereitgestellt.

Zuerst müssen wir ein 8x8-Schachbrett definieren, das durch ein zweidimensionales Array dargestellt wird. Jedes Element des Arrays kann ein Schachbrettgitter darstellen. 1 bedeutet, dass es eine Königin auf dem Gitter gibt, 0 bedeutet, dass es keine Königin gibt.

Als nächstes definieren wir eine rekursive Funktion, um jede Reihe des Bretts zu durchlaufen und zu versuchen, die Königin zu platzieren. Die spezifischen Schritte sind wie folgt:

1. Wenn Sie zur letzten Reihe des Schachbretts gelangt sind, bedeutet dies, dass Sie eine Lösung gefunden haben, den aktuellen Schachbrettstatus speichern und zurückkehren.
2. Durchquere jedes Gitter in der aktuellen Reihe und versuche, die Königin zu platzieren.
3. Wenn das aktuelle Gitter die Bedingungen für die Platzierung der Königin nicht erfüllt (d. h. es steht im Konflikt mit der bereits platzierten Königin), wird das aktuelle Gitter übersprungen und das nächste Gitter weiter durchquert.
4. Wenn das aktuelle Gitter die Bedingungen für die Platzierung einer Königin erfüllt, platzieren Sie eine Königin auf dem Gitter und markieren Sie das Gitter als besetzt.
5. Rufen Sie die Funktion rekursiv auf und durchlaufen Sie die nächste Zeile.
6. Wenn das Ergebnis des rekursiven Aufrufs „true“ zurückgibt, bedeutet dies, dass eine Lösung gefunden wurde, dann wird die Lösung gespeichert und „true“ zurückgegeben.
7. Wenn das Ergebnis des rekursiven Aufrufs „Falsch“ zurückgibt, bedeutet dies, dass die Platzierung des aktuellen Gitters nicht den Lösungsanforderungen entspricht. Entfernen Sie dann die Königin aus dem Gitter und kehren Sie zum vorherigen Schritt zurück.

Basierend auf den oben genannten Ideen können wir den folgenden Code implementieren:

#include <iostream>
#include <vector>

using namespace std;

const int n = 8;  // 棋盘大小

// 棋盘
int chessboard[n][n];

// 保存解法的容器
vector<vector<int>> solutions;

// 检查当前格子上是否可以放置皇后
bool isValid(int row, int col) {
    // 检查同一列上是否有皇后
    for (int i = 0; i < row; i++) {
        if (chessboard[i][col] == 1)
            return false;
    }
    
    // 检查左上对角线上是否有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 1)
            return false;
    }
    
    // 检查右上对角线上是否有皇后
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 1)
            return false;
    }
    
    return true;
}

// 解决八皇后问题的递归函数
bool solveNQueens(int row) {
    // 如果已经遍历到最后一行，表示找到了一种解法，将当前棋盘状态保存下来
    if (row == n) {
        vector<int> solution;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (chessboard[i][j] == 1)
                    solution.push_back(j);
            }
        }
        solutions.push_back(solution);
        return true;
    }

    // 遍历当前行的每一个格子，尝试放置皇后
    for (int col = 0; col < n; col++) {
        // 如果当前格子满足放置皇后的条件，标记该格子为已占用
        if (isValid(row, col)) {
            chessboard[row][col] = 1;

            // 递归调用函数，遍历下一行
            solveNQueens(row + 1);

            // 如果递归调用的结果返回false，表示当前格子的放置方式不满足解法要求，回溯到上一步
            chessboard[row][col] = 0;
        }
    }

    return false;
}

// 打印解法
void printSolutions() {
    for (auto solution : solutions) {
        cout << "Solution:" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == solution[i])
                    cout << "Q ";
                else
                    cout << ". ";
            }
            cout << endl;
        }
        cout << endl;
    }
}

int main() {
    solveNQueens(0);
    printSolutions();
    return 0;
}

Führen Sie dieses Programm aus und alle Lösungen werden ausgegeben. Jede Lösung wird in Form eines Schachbretts angezeigt, wobei Q die Dame und das Feld darstellt. Mit diesem Algorithmus können wir alle Lösungen des Acht-Damen-Problems finden.

Ich hoffe, dieser Artikel hilft Ihnen zu verstehen, wie Sie den Eight Queens Problem-Algorithmus in C++ verwenden. Die Implementierung dieses Algorithmus erfordert die Verwendung von Rekursions- und Backtracking-Ideen. Solange Sie die richtigen Schritte befolgen, können Sie die Lösung für das Acht-Damen-Problem finden.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Eight Queens Problem-Algorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!