回溯-dfs-n皇后问题
#include<iostream>
using namespace std;
const int N = 12;
char q[N][N];
int n;
int column[N], dia[N * 2], fandia[N * 2];
void dfs(int i) {
if (i > n) {
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) cout << q[i][j];
cout << endl;
}
cout << endl;
return;
}
for (int j = 1; j <= n; j ++ ) {
if (!column[j] && !dia[i + j] && !fandia[n - i + j]) {
q[i][j] = 'Q';
column[j] = 1;
dia[i + j] = 1;
fandia[n - i + j] = 1;
dfs(i + 1);
column[j] = 0;
dia[i + j] = 0;
fandia[n - i + j] = 0;
q[i][j] = '.';
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) q[i][j] = '.';
}
dfs(1);
return 0;
}