2.n-皇后问题 DFS

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 //像全排列那样搜
 4 //每一行都必须要放一个皇后也只能放一个皇后
 5 //先看第一行皇后可以放在哪一列
 6 const int N = 20;
 7 char ans[N][N];
 8 bool col[N], dg[N], udg[N];
 9 //同一列    正对角线   反对角线
10 int n;
11 void dfs(int u) {
12     if (u == n) {
13         for (int i = 0; i < n; i++) {
14             for (int j = 0; j < n; j++) {
15                 cout << ans[i][j];
16             }
17             cout << endl;
18         }
19         cout << endl;
20         return;
21     }
22     for (int i = 0; i < n; i++) { //枚举第u行，皇后应该放在哪一列
23         if (!col[i] && !dg[u + i] && !udg[u - i + n]) {
24             ans[u][i] = ‘Q‘;
25             col[i] = true;
26             dg[u + i] = true;
27             udg[u - i + n] = true;
28             dfs(u + 1);
29             ans[u][i] = ‘.‘;
30             col[i] = false;
31             dg[u + i] = false;
32             udg[u - i + n] = false;
33         }
34     }
35 }
36 int main() {
37     cin >> n;
38     for (int i = 0; i < n; i++) {
39         for (int j = 0; j < n; j++) {
40             ans[i][j] = ‘.‘;
41         }
42     }
43     dfs(0);
44     return 0;
45 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 //第二种搜索顺序
 4 //枚举每个格子放不放皇后
 5 //比第一种方法差一点
 6 const int N = 20;
 7 char g[N][N];
 8 bool row[N], col[N], dg[N], udg[N];
 9 //   行    列    正对角线   反对角线
10 int n;
11 void dfs(int x, int y, int s) { //x和y是坐标，s是已经放下的皇后数量
12     if (y == n) {
13         y = 0;
14         x++;
15     }
16     if (x == n) {
17         if (s == n) {
18             for (int i = 0; i < n; i++) {
19                 for (int j = 0; j < n; j++) {
20                     cout << g[i][j];
21                 }
22                 cout << endl;
23             }
24             cout << endl;
25         }
26         return;
27     }
28     //这个格子不放皇后
29     dfs(x, y + 1, s);
30     //这个格子放皇后
31     if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
32         g[x][y] = ‘Q‘;
33         row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
34         dfs(x, y + 1, s + 1);
35         //回溯
36         g[x][y] = ‘.‘;
37         row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
38     }
39 }
40 int main() {
41     cin >> n;
42     for (int i = 0; i < n; i++) {
43         for (int j = 0; j < n; j++) {
44             g[i][j] = ‘.‘;
45         }
46     }
47     dfs(0, 0, 0);
48     return 0;
49 }