用回溯法求解4皇后问题 【问题描述】在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。如下图所示是4皇后问题的一个解。 q[1..4]={2，4，1，3}编写C++代码解决上述问题

以下是用回溯法求解4皇后问题的C++代码：

#include <iostream>
using namespace std;

int n = 4; // 皇后数
int q[10] = {0}; // 存放皇后的列号，下标表示行号

bool check(int row, int col) { // 判断是否可以在该位置放置皇后
    for(int i = 1; i < row; i++) { // 遍历之前所有的行
        if(q[i] == col || abs(i-row) == abs(q[i]-col)) { // 与当前位置同列或同对角线
            return false;
        }
    }
    return true;
}

void backtrack(int row) { // 回溯函数
    if(row > n) { // 找到一组解
        for(int i = 1; i <= n; i++) {
            cout << q[i] << " ";
        }
        cout << endl;
    } else {
        for(int col = 1; col <= n; col++) { // 枚举该行所有可能的列
            if(check(row, col)) { // 如果可以在该位置放置皇后
                q[row] = col; // 记录皇后的位置
                backtrack(row+1); // 继续搜索下一行
                q[row] = 0; // 回溯操作，恢复该位置
            }
        }
    }
}

int main() {
    backtrack(1);
    return 0;
}

输出结果为：

2 4 1 3
3 1 4 2