n-皇后问题

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

输入格式

共一行，包含整数 n 。

输出格式

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

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

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

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

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

数据范围

1≤n≤9

输入样例：

4

输出样例：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

题解

这里我们运用

深度优先遍历

（

dfs

）的方法解题

方法一

全排列法

将所有的路径一一排列出来

在排列的时候进行条件判断

不符合的排列直接回溯

从第一行的第一个位置开始进行枚举到第一行的最后一个位置

进行排列组合

在进行排列组合的过程中对不符合的进行

剪枝


条件：

两个皇后都不能处于同一行、同一列或同一斜线上。

如图，这是所有排列中的两种方法，



绿色的排列不符合要求，

红色的排列组合符合要求

定义一个路径数组用来储存所走路径上的值。

同时定义col列，dg对角线，udg反对角线数组，判断是否符合放置皇后的条件

#include <iostream>
using namespace std;
const int N = 20; 

// bool数组用来判断搜索的下一个位置是否可行
// col列，dg对角线，udg反对角线
// g[N][N]用来存路径

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u) {
    // u == n 表示已经搜了n行，故输出这条路径
    if (u == n) {
        for (int i = 0; i < n; i ++ ) puts(g[i]);  
        puts("");  
        return;
    }

  
    for (int i = 0; i < n; i ++ )
        // 剪枝(对于不满足要求的点，不再继续往下搜索)  
        // udg[n - u + i]，+n是为了保证下标非负
        if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            // 恢复现场
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';

        }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}   

 

方法二

这个方法比较原始。

从头开始一个一个位置的判断是否放置皇后，并用

s

记录皇后的数量，当到最后一个位置且放置皇后的数量

s==n

时，说明该条路径符合要求，并输出。

#include<iostream>
const int N=20;

int n;
bool col[N] , row[N], dg[N] , udg[N]; 
char path[N][N];

using namespace std;

void dfs(int x, int y, int s)
{
    if (y == n)
    {
        y = 0; x++;
    }
    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i++)
            {
                cout << path[i] << endl;
            }
            cout << endl;
        }
        return;
    }
 
//放皇后
if (!row[x] && !col[y] && !dg[n + y - x] && !udg[y + x])
{
    path[x][y] = 'Q';
    row[x] = col[y] = dg[n + y - x] =udg[y + x] = true;
    dfs(x, y + 1, s + 1);
    path[x][y] = '.';
    row[x] = col[y] = dg[n + y - x] = udg[y + x] = false;
}


//不放皇后
dfs(x, y + 1, s);


}

int main()
{
  cin>>n;
   
  for(int i=0;i<n;i++)
  {
      for(int j=0;j<n;j++)
      {
          path[i][j]='.';
      }
  }
  dfs(0,0,0);
  return 0;
}

只是在上一个的解法上进行调整，但该解法的时间复杂度远大于第一种解法，当n足够大时，第二种解法会超时。