n皇后问题穷举法c++

n皇后问题是经典的回溯算法问题，目标是在一个n×n的棋盘上放置n个皇后，使得任意两个皇后都不在同一行、同一列，也不在同一对角线上。在C++中，你可以使用穷举法通过递归的方式来解决这个问题。以下是简单的步骤：

1. 定义一个二维数组`board`表示棋盘，初始化所有元素为0。
2. 使用一个变量`col`记录当前列数，从1到n。
3. 函数`solveNQueens(int n, int board[n][n], int row)`作为主函数，递归地尝试将皇后放在每一列。
4. 在`row`位置放皇后之前，检查当前位置是否违反了规则（同一行、同一列或对角线）。如果满足条件，就继续下一行；如果不满足，则回溯并尝试下一个位置。
5. 如果所有皇后都成功摆放，打印结果或者计数加一。

#include <iostream>

// 检查当前位置是否合法
bool isValid(int row, int col, int board[n][n]) {
    // 同一行、同一列
    for (int i = 0; i < col; ++i)
        if (board[row][i] == 1)
            return false;
    
    // 对角线检查
    int dia1 = row + col - 1, dia2 = row - col;
    for (int i = 0; i < row; ++i) {
        if (board[i][dia1] == 1 || board[i][dia2] == 1)
            return false;
        dia1 -= 2; dia2 += 2;
    }
    
    return true;
}

void solveNQueens(int n, int board[n][n], int row) {
    if (row == n) { // 当前行已满，解决方案找到
        // 打印或统计解决方案
        // ...
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (isValid(row, col, board)) {
            board[row][col] = 1; // 放置皇后
            solveNQueens(n, board, row + 1); // 递归尝试下一行
            board[row][col] = 0; // 回溯，移除皇后
        }
    }
}

int main() {
    int n;
    std::cout << "Enter the size of the chessboard: ";
    std::cin >> n;

    int board[n][n];
    solveNQueens(n, board, 0);

    return 0;
}