XiYuJing|文章:n−皇后问题

[[ slide_text ]]

[[item.c]]

n−皇后问题

发布时间：2022年11月08日 作者：靖华来源：XiYuJing

算法 C++ dfs

### 题目
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

![1_597ec77c49-8-queens.png](https://cdn.acwing.com/media/article/image/2019/06/08/19_860e00c489-1_597ec77c49-8-queens.png)

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

#### 输入格式

共一行，包含整数 n。

#### 输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 `.` 表示某一个位置的方格状态为空，`Q` 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

**注意：行末不能有多余空格。**

输出方案的顺序任意，只要不重复且没有遗漏即可。

#### 数据范围

1 ≤ n ≤ 9

#### 输入样例：

```
4
```

#### 输出样例：

```
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..
```
> 题目来源于AcWing

###题解
#### 暴力（不动脑子的写法）
```
#include<iostream>
using namespace std;
const int N = 15;
int d[N][N],n;
char a[N][N];
void dfs(int idx)
{
    if(idx==n)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)cout<<a[i][j];
            cout<<endl;
        }
        cout<<endl;
        return ;
    }
    int i=idx+1;
    for(int j=1;j<=n;j++)
    {
        if(!d[i][j])
        {
            a[i][j]='Q';
            for(int x=i;x<=n;x++)d[x][j]++;
            for(int x=i;x>0;x--)d[x][j]++;
            for(int x=j;x>0;x--)d[i][x]++;
            for(int x=j;x<=n;x++)d[i][x]++;
            for(int x=i,y=j;x<=n&&y<=n;x++,y++)d[x][y]++;
            for(int x=i,y=j;x>0&&y>0;x--,y--)d[x][y]++;
            for(int x=i,y=j;x<=n&&y>0;x++,y--)d[x][y]++;
            for(int x=i,y=j;x>0&&y<=n;x--,y++)d[x][y]++;
            dfs(idx+1);
            a[i][j]='.';
            for(int x=i;x<=n;x++)d[x][j]--;
            for(int x=j;x<=n;x++)d[i][x]--;
            for(int x=i;x>0;x--)d[x][j]--;
            for(int x=j;x>0;x--)d[i][x]--;
            for(int x=i,y=j;x<=n&&y<=n;x++,y++)d[x][y]--;
            for(int x=i,y=j;x>0&&y>0;x--,y--)d[x][y]--;
            for(int x=i,y=j;x<=n&&y>0;x++,y--)d[x][y]--;
            for(int x=i,y=j;x>0&&y<=n;x--,y++)d[x][y]--;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)a[i][j]='.';
    dfs(0);
}
```
#### 利用数学知识
```c++
#include<iostream>
using namespace std;
const int N = 15;
int n;
bool shu[N],zd[N],fd[N];//横，竖，正对角线，反对角线
char a[N][N];
void dfs(int idx)
{
    if(idx==n)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)cout<<a[i][j];
            cout<<endl;
        }
        cout<<endl;
        return ;
    }
    int i=idx+1;
    for(int j=1;j<=n;j++)
    {
        if(!shu[j]&&!zd[j-i+n]&&!fd[j+i-1])
        {
            a[i][j]='Q';
            shu[j]=zd[j-i+n]=fd[j+i-1]=true;
            dfs(idx+1);
            a[i][j]='.';
            shu[j]=zd[j-i+n]=fd[j+i-1]=false;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)a[i][j]='.';
    dfs(0);
}
```

你觉得文章怎么样

已浏览 116 次，0 条评论