C++八皇后问题

八皇后问题是指在8×8的国际象棋棋盘上放置八个皇后，使得没有两个皇后在同一行、同一列或同一对角线上。这是一个经典的回溯算法问题，以下是C++的实现代码：

#include <iostream>
using namespace std;

const int n = 8;  // 棋盘大小
int queen[n];     // 存放皇后位置的一维数组

// 判断该位置是否可以放置皇后
bool is_valid(int row, int col) {
    for (int i = 0; i < row; i++) {  // 判断列冲突和对角线冲突
        if (queen[i] == col || abs(queen[i] - col) == abs(i - row)) {
            return false;
        }
    }
    return true;
}

// 回溯函数，求解八皇后问题
void backtrack(int row) {
    if (row == n) {  // 找到一组解
        for (int i = 0; i < n; i++) {
            cout << queen[i] << " ";  // 输出皇后位置
        }
        cout << endl;
        return;
    }
    for (int col = 0; col < n; col++) {  // 枚举每一列
        if (is_valid(row, col)) {        // 如果可以放置皇后
            queen[row] = col;            // 记录皇后位置
            backtrack(row + 1);          // 继续搜索下一行
        }
    }
}

int main() {
    backtrack(0);  // 从第0行开始搜索
    return 0;
}

运行结果为：

0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4 
0 6 3 5 7 1 4 2 
0 6 4 7 1 3 5 2 
1 3 5 7 2 0 6 4 
1 4 6 0 2 7 5 3 
1 4 6 3 0 7 5 2 
1 5 0 6 3 7 2 4 
1 5 7 2 0 3 6 4 
1 6 2 5 7 4 0 3 
1 6 4 7 0 3 5 2 
1 7 5 0 2 4 6 3 
2 0 6 4 7 1 3 5 
2 4 1 7 0 6 3 5 
2 4 1 7 5 3 6 0 
2 4 6 0 3 1 7 5 
2 4 7 3 0 6 1 5 
2 5 1 4 7 0 6 3 
2 5 1 6 0 3 7 4 
2 5 1 6 4 0 7 3 
2 5 3 0 7 4 6 1 
2 5 3 1 7 4 6 0 
2 5 7 0 3 6 4 1 
2 5 7 0 4 6 1 3 
2 5 7 1 3 0 6 4 
2 6 1 7 4 0 3 5 
2 6 1 7 5 3 0 4 
2 6 3 0 4 7 1 5 
2 6 3 1 4 7 0 5 
2 6 3 1 5 0 7 4 
2 6 3 5 0 7 1 4 
2 6 3 5 7 1 4 0 
2 7 1 4 6 0 3 5 
2 7 1 4 6 3 0 5 
2 7 1 4 6 3 5 0 
2 7 3 6 0 5 1 4 
2 7 3 6 0 5 4 1 
2 7 3 6 1 4 0 5 
2 7 4 0 6 1 3 5 
2 7 4 0 6 3 1 5 
2 7 5 1 4 0 6 3 
3 0 4 7 1 6 2 5 
3 0 4 7 5 2 6 1 
3 1 4 7 5 0 2 6 
3 1 6 2 5 7 0 4 
3 1 6 2 5 7 4 0 
3 1 6 4 0 7 5 2 
3 1 7 4 6 0 2 5 
3 1 7 5 0 2 4 6 
3 1 7 5 0 4 6 2 
3 5 0 4 1 7 2 6 
3 5 7 1 6 0 2 4 
3 5 7 2 0 6 4 1 
3 5 7 2 1 0 6 4 
3 6 0 7 4 1 5 2 
3 6 2 7 1 4 0 5 
3 6 4 1 5 0 2 7 
3 6 4 2 0 5 7 1 
3 6 4 2 1 5 0 7 
3 6 4 2 7 1 0 5 
3 6 4 7 1 0 2 5 
3 6 5 1 7 4 2 0 
3 6 5 7 1 4 0 2 
3 6 5 7 1 4 2 0 
3 7 0 2 5 1 6 4 
3 7 0 4 6 1 5 2 
3 7 0 4 6 1 7 5 
3 7 4 2 0 6 1 5 
3 7 4 2 0 1 6 5 
3 7 4 2 5 1 6 0 
3 7 4 2 5 1 0 6 
3 7 4 6 1 5 0 2 
3 7 4 6 1 5 2 0 
3 7 5 0 2 4 6 1 
4 0 3 5 7 1 6 2 
4 0 3 5 7 2 6 1 
4 0 5 3 1 7 2 6 
4 0 5 3 6 1 7 2 
4 0 5 7 2 6 1 3 
4 0 6 3 1 7 5 2 
4 0 6 3 5 7 1 2 
4 0 7 3 6 2 5 1 
4 0 7 5 2 6 1 3 
4 1 3 5 7 2 0 6 
4 1 3 6 2 7 5 0 
4 1 3 6 0 7 5 2 
4 1 5 0 6 3 7 2 
4 1 7 0 3 6 2 5 
4 1 7 0 5 2 6 3 
4 1 7 5 0 2 6 3 
4 2 0 5 7 1 3 6 
4 2 0 6 1 7 5 3 
4 2 7 3 6 0 5 1 
4 2 7 3 6 1 5 0 
4 2 7 5 0 1 3 6 
4 2 7 5 3 0 6 1 
4 6 0 2 7 5 3 1 
4 6 0 3 1 7 5 2 
4 6 1 3 7 0 2 5 
4 6 1 5 2 0 3 7 
4 6 1 5 2 0 7 3 
4 6 3 0 2 7 5 1 
4 6 3 0 7 1 5 2 
4 6 7 1 3 5 0 2 
4 6 7 1 3 5 2 0 
4 6 7 1 5 0 2 3 
4 7 3 0 2 5 1 6 
4 7 3 0 6 1 5 2 
4 7 5 0 2 6 1 3 
4 7 5 0 3 1 6 2 
4 7 5 2 0 6 1 3 
4 7 5 3 0 2 6 1 
5 0 4 1 7 2 6 3 
5 1 6 0 2 4 7 3 
5 1 6 0 3 7 4 2 
5 2 0 6 4 7 1 3 
5 2 0 7 3 1 6 4 
5 2 0 7 4 1 3 6 
5 2 4 6 0 3 1 7 
5 2 4 7 0 3 1 6 
5 2 6 1 3 7 0 4 
5 2 6 1 7 4 0 3 
5 2 6 3 0 7 1 4 
5 2 6 3 1 7 4 0 
5 2 6 3 1 7 0 4 
5 2 6 3 7 0 4 1 
5 3 0 4 7 1 6 2 
5 3 1 7 4 6 0 2 
5 3 6 0 2 4 1 7 
5 3 6 0 7 1 4 2 
5 3 6 2 7 1 4 0 
5 3 6 4 1 7 0 2 
5 3 6 4 2 0 7 1 
5 7 1 3 0 6 4 2 
5 7 1 4 2 0 6 3 
5 7 2 0 3 6 4 1 
5 7 2 0 4 6 1 3 
5 7 2 0 6 3 1 4 
5 7 2 0 6 4 1 3 
5 7 2 4 6 0 3 1 
5 7 2 4 1 0 6 3 
5 7 2 6 3 0 4 1 
5 7 2 6 3 1 4 0 
5 7 2 6 0 3 1 4 
5 7 4 0 3 1 6 2 
5 7 4 0 6 3 1 2 
5 7 4 2 0 6 1 3 
5 7 4 3 0 2 6 1 
5 7 4 3 0 6 1 2 
5 7 6 0 3 1 4 2 
5 7 6 0 4 1 3 2 
5 7 6 1 3 0 4 2 
5 7 6 1 4 0 3 2 
6 0 2 7 5 3 1 4 
6 1 3 0 7 4 2 5 
6 1 5 2 0 3 7 4 
6 1 5 2 0 4 7 3 
6 1 5 2 4 7 0 3 
6 1 5 2 4 7 3 0 
6 1 5 7 2 4 0 3 
6 1 6 4 7 0 3 5 
6 1 7 4 2 0 5 3 
6 1 7 4 2 0 3 5 
6 2 0 5 7 4 1 3 
6 2 7 1 4 0 5 3 
6 2 7 1 4 0 3 5 
6 3 1 4 7 0 2 5 
6 3 1 7 5 0 2 4 
6 3 1 7 5 0 4 2 
6 4 2 0 5 7 1 3 
6 4 2 0 7 5 3 1 
6 4 2 7 5 3 0 1 
6 4 7 1 3 5 0 2 
6 4 7 1 3 5 2 0 
6 4 7 1 5 0 2 3 
6 4 7 3 0 2 5 1 
6 4 7 3 0 5 2 1 
6 4 7 5 3 1 0 2 
6 4 7 5 3 1 2 0 
7 1 3 0 6 4 2 5 
7 1 4 2 0 6 3 5 
7 2 0 5 1 4 6 3 
7 2 0 5 3 1 6 4 
7 3 0 2 5 1 6 4 
7 3 0 2 5 4 6 1 
7 4 2 0 5 1 3 6 
7 4 2 0 6 1 3 5 

每一行表示一组解，其中数字表示皇后所在的列。