DFS经典问题 N皇后

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，要求：任何两个皇后不同行，不同列也不在同一条斜线上， 求给一个整数 n ，返回 n 皇后的摆法数。

数据范围: 1 ≤ n ≤ 9

例如当输入4时，对应的返回值为2，对应的两种四皇后摆位如下图所示：

不攻击检查

即需要判断：

1. 是否处于同一列中

2. 是否在左斜线上：（行 + 列）的值不可相等

3. 是否在右斜线上：（列 - 行）的值不可相等

4. 这里，每行肯定只有1个皇后，是很显然的，因此不必特别判断，左右斜线的判断可以用一个绝对值公式abs(board[i] - col) == abs(i - row)判断，这样就不需要写两个公式。

#include<bits/stdc++.h>

using namespace std;

int board[110];
int n,ans=0;
bool check(int x,int y){
    for(int i=1;i<x;i++){
        if(board[i]==y ||(abs(board[i]-y)==abs(i-x))){
            return false;
        }
    }
    return true;
}

void queen(int step){
    if(step==n+1){
        ans++;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j!=board[i]){
                    cout<<"O";
                }else{
                    cout<<"X";
                }
            }cout<<endl;

        }cout<<endl<<"-----"<<endl;

        return ;
    }
    for(int i=1;i<=n;i++){
        if(check(step,i)){
            board[step]=i;
            queen(step+1);
            board[step]=0;
        }
    }
}

int main() {
    cin>>n;
    queen(1);
    cout<<ans;
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com