如何使用C++中的八皇后問題演算法

如何使用C 中的八皇后問題演算法

八女王問題是一個經典的演算法問題，要求在8x8的棋盤上放置八個皇后，使得任意兩個皇后都不能互相攻擊，即任意兩個皇后不能處於同一行、同一列或同一對角線上。解決八皇后問題的演算法有很多，其中一個常見的方法是使用回溯演算法。本文將介紹如何使用C 語言實作八皇后問題的演算法，並提供具體的程式碼範例。

首先，我們要定義一個8x8的棋盤，用一個二維陣列來表示。陣列的每個元素可以表示一個棋盤格子，1表示該格子上有一個皇后，0表示沒有皇后。

接下來，我們定義一個遞歸函數來遍歷棋盤的每一行，並嘗試放置皇后。具體步驟如下：

1. 如果已經遍歷到了棋盤的最後一行，表示找到了一種解法，將當前的棋盤狀態保存下來，並返回。
2. 遍歷目前行的每一個格子，試著放置皇后。
3. 如果當前格子不滿足放置皇后的條件（即與已經放置的皇后存在衝突），則跳過當前格子，繼續遍歷下一個格子。
4. 如果目前格子滿足放置皇后的條件，將該格子上放置一個皇后，並標記該格子為已佔用。
5. 遞迴呼叫函數，遍歷下一行。
6. 如果遞迴呼叫的結果回傳true，表示找到了一種解法，則將該解法儲存下來，並傳回true。
7. 如果遞歸呼叫的結果傳回false，表示目前格子的放置方式不符合解法要求，則將該格子上的皇后移除，並回溯到上一步。

根據上述思路，我們可以實作以下程式碼：

#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;
}

運行該程序，將會輸出所有的解法。每個解法以棋盤的形式顯示，其中Q表示皇后，.表示空格。透過該演算法，我們可以找到八皇后問題的所有解法。

希望這篇文章對你理解如何使用C 中的八皇后問題演算法有所幫助。實現該演算法需要使用遞歸和回溯的思想，只要按照正確的步驟進行操作，就能夠找到八皇后問題的解法。

以上是如何使用C++中的八皇后問題演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！