八皇后问题c++位运算

八皇后问题是一个经典的回溯算法题目，通常用于展示递归和位运算技巧。位运算在这里可以帮助简化问题，通过设置每个棋格是否可以放置皇后的一个二进制位表示。C++中，我们使用每位代表一个行，0表示空，1表示已经有皇后。

以下是使用位运算解决八皇后问题的一种简单思路：

1. 初始化一个8位的整数，每一位对应一个棋盘的列。
2. 使用一个循环，从第一行开始，尝试将1（即皇后）放在当前位上。
3. 对于每一行，检查左移后的值（相当于上一行）是否有冲突（即有相同的位）。这一步通过按位与操作完成，如果结果为非零，则说明当前位置下方有之前的皇后，不合法。
4. 如果当前位置合法，继续向下一行；如果不合法，就回溯到上一行，尝试其他位置。
5. 当所有位置都检查完，如果找到了解决方案，记录这个状态并继续搜索；如果没有找到，返回上一行继续尝试。

#include <iostream>

bool isSafe(int mask, int row) {
    // 检查列是否有冲突
    return !(mask & (1 << row));
}

void solveNQueens(int N, int mask = 0, int row = 0) {
    if (row == N) { // 找到了一个解，记录并结束
        printSolution(mask);
        return;
    }

    for (int col = 0; col < N; ++col) {
        if (isSafe(mask, col)) {
            // 尝试放皇后
            mask |= 1 << col;
            solveNQueens(N, mask, row + 1); // 递归往下一层
            // 回溯，尝试下一个位置
            mask &= ~(1 << col);
        }
    }
}

void printSolution(int mask) {
    for (int i = 0; i < 8; ++i) {
        if (mask & (1 << i)) {
            std::cout << "Q ";
        } else {
            std::cout << ".";
        }
        std::cout << "\n";
    }
    std::cout << "-------------\n";
}

int main() {
    int N = 8;
    solveNQueens(N);
    return 0;
}