n-皇后问题
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 n。
输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q..
算法思路：
- 函数名：void dfs(int r): 深度优先遍历函数。参数r：从第r行开始放棋子，处理第r行。
- 递归结束判定：见代码，当 r == n的时候，说明应该处理第 n行了，也代表第 0~n-1行放好棋子，也就是整个棋盘放好了棋子，也就是得到了一种解，也就是递归结束。
- 第r行，第i列能不能放棋子：用数组dg udg row col 分别表示：点对应的两个斜线以及行列上是否有皇后。
dg[i + r] 表示 r行i列处，所在的对角线上有没有棋子，udg[n - i + r]表示 r行i列处，所在的反对角线上有没有棋子，col[i]表示第i列上有没有棋子。如果 r行i列的对角线，反对角线上都没有棋子，即!row[i]&&!col[i] && !dg[i + r] && !udg[n - i + r]为真，则代表 r行i列处可以放棋子。
C++
#include<iostream> using namespace std; const int N = 20; int n; char g[N][N]; bool row[N], col[N], dg[N], udg[N]; void dfs(int u) { if (u == n) { for (int i = 0; i < n; ++ i) puts(g[i]); puts(""); return; } for (int i = 0; i < n; ++ i) // 一列一列的枚举 { if (!row[u] && !col[i] && !dg[u + i] && !udg[n - u + i]) // 这里的这个dg和udg是最难理解的 // u + i = c1 这个c1可以确定正斜线上面的一个点, -u + i = c2,这个c2可以确定反斜线上面的以一个点 // 这里c2可能为负数 所以要加一个偏移量n { g[u][i] = 'Q'; row[u] = col[i] = dg[u + i] = udg[n - u + i] = true; dfs (u + 1); row[u] = 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; }
Java
import java.util.*; public class Main { static Scanner in = new Scanner(System.in); static int N = 20; static boolean[] col = new boolean[N], dg = new boolean[N], udg = new boolean[N]; static int n = 0; static char[][] chs = new char[N][N]; static void dfs (int u) { if (u > n) { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { System.out.print(chs[i][j]); } System.out.println(); } System.out.println(); return; } for (int i = 1; i <= n; ++ i) { if (!col[i] && !dg[i - u + n] && !udg[i + u]) { chs[u][i] = 'Q'; col[i] = dg[i - u + n] = udg[i + u] = true; dfs(u + 1); col[i] = dg[i - u + n] = udg[i + u] = false; chs[u][i] = '.'; } } } public static void main(String[] args) { n = in.nextInt(); for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) chs[i][j] = '.'; } dfs(1); } }
