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足够大时，第二种解法会超时。
