八皇后（N皇后）

· · 个人记录 

#include <bits/stdc++.h> 
using namespace std;

int n;  // n皇后
int cnt = 0; 
vector<string> queen;  // 皇后位置，"."：表示可放置，"Q"：表示皇后位置 
vector<vector<int> > attack;  // 是否可放皇后，"0"：表示可以放，"1"：表示不能放

// 放置皇后 
void put_queen(int x, int y) {
    // 方向数组 
    int dx[]={-1, -1, -1, 0, 1, 1, 1, 0};
    int dy[]={-1, 0, 1, 1, 1, 0, -1, -1};
    // 修改attack二维数组 
    attack[x][y] = 1;  // 皇后放置的位置 
    // 修改皇后攻击到的位置
    for (int i = 1; i < n; i++) {  // i：皇后攻击距离（1~n-1） 
        for (int j = 0; j < 8; j++) {  // 遍历8个方向 
            // nx、ny：修改的坐标， 
            int nx = x + i * dx[j];
            int ny = y + i * dy[j];
            // 判断修改的位置在棋盘内 
            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                attack[nx][ny] = 1;
            }
        }
    } 
}

// 回溯递归函数
// k：当前处理行， 
void backtrack(int k) {
    if (k == n) {  // 找到一组解 
        cnt++;
        cout << "解法" << cnt << "：" << endl;
        for (int i = 0; i < queen.size(); i++) {
            cout << queen[i] << endl;
        } 
        return;
    }
    // 遍历0~n-1列，试探皇后可放置位置
    for (int i = 0; i < n; i++) {
        if (attack[k][i] == 0) {
            vector<vector<int> > temp = attack;  // 备份attack数组
            queen[k][i] = 'Q';  // 修改queen数组
            put_queen(k, i);  // 更新attack数组 
            backtrack(k + 1);  // 递归试探k+1行 
            attack = temp;  // 恢复attack数组 
            queen[k][i] = '.';  // 恢复queen数组 
        }
    } 
}

int main() {
    cin >> n; 
    // 初始化queen和attack二维数组
    for (int i = 0; i < n; i++) {
        attack.push_back(vector<int>());
        string s;
        for (int j = 0; j < n; j++) {
            attack[i].push_back(0);
            s += ".";
        }
        queen.push_back(s);
    }
    // 递归搜索 
    backtrack(0);

    return 0;
}
#include <bits/stdc++.h> 
using namespace std;

int n;  // n皇后
int cnt = 0;  // 记录解法个数
char queen[10][10];  // 皇后位置，"."：表示可放置，"Q"：表示皇后位置 
int attack[10][10];  // 是否可放皇后，"0"：表示可以放，"1"：表示不能放

// 放置皇后 
void put_queen(int x, int y, int n) {
    // 方向数组 
    int dx[]={-1, -1, -1, 0, 1, 1, 1, 0};
    int dy[]={-1, 0, 1, 1, 1, 0, -1, -1};
    // 修改attack二维数组 
    attack[x][y] = 1;  // 皇后放置的位置 
    // 修改皇后攻击到的位置
    for (int i = 1; i < n; i++) {  // i：皇后攻击距离（1~n-1） 
        for (int j = 0; j < 8; j++) {  // 遍历8个方向 
            // nx、ny：修改的坐标， 
            int nx = x + i * dx[j];
            int ny = y + i * dy[j];
            // 判断修改的位置在棋盘内 
            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                attack[nx][ny] = 1;
            }
        }
    } 
}

// 备份数组(a拷贝给b)
void copy(int a[10][10], int b[10][10], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            b[i][j] = a[i][j];
        }
    }
} 

// 回溯递归函数
// k：当前处理行， 
void backtrack(int k, int n) {
    if (k == n) {  // 找到一组解 
        cnt++;
        cout << "解法" << cnt << "：" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << queen[i][j];
            }
            cout << endl;
        } 
        return;
    }
    // 遍历0~n-1列，试探皇后可放置位置
    for (int i = 0; i < n; i++) {
        if (attack[k][i] == 0) {
            int tem[10][10];  // 备份数组 
            copy(attack, tem, n);  // 备份attack数组
            queen[k][i] = 'Q';  // 修改queen数组
            put_queen(k, i, n);  // 更新attack数组 
            backtrack(k + 1, n);  // 递归试探k+1行 
            copy(tem, attack, n);  // 恢复attack数组 
            queen[k][i] = '.';  // 恢复queen数组 
        }
    } 
}

int main() {
    cin >> n; 
    // 初始化queen和attack二维数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            queen[i][j] = '.';
            attack[i][j] = 0;
        }
    }
    // 递归搜索 
    backtrack(0, n);

    return 0;
}