Q: Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.

A: 经典的8皇后问题。DFS

#include <iostream>
#include <string>
#include <vector>
using namespace std;void dfs(vector<int> &colum, vector<int> &main_diag, vector<int> &anti_diag, int row, vector<vector<string> > &res, vector<int> &path) {const int N = path.size();if (row == N) {vector<string> cur;for (int i = 0; i < N; i++) {string s(N,'.');s[path[i]] = 'Q';cur.push_back(s);cout<<s<<endl;}cout<<endl;res.push_back(cur);return ;		}for (int i = 0; i < N; i++) {bool ok = colum[i] == 0 && main_diag[row+i] == 0 && anti_diag[row+N-i] == 0;if (!ok) continue;path[row] = i;colum[i] = main_diag[row+i] = anti_diag[row+N-i] = 1;dfs(colum, main_diag, anti_diag, row+1, res, path);colum[i] = main_diag[row+i] = anti_diag[row+N-i] = 0;}
}vector<vector<string> > n_queen(const int n) {vector<int> colum(n, 0);vector<int> main_diag(2*n, 0);vector<int> anti_diag(2*n, 0);vector<vector<string> > res;vector<int> path(n, 0);dfs(colum, main_diag, anti_diag, 0, res, path);return res;
}int main() {n_queen(8);return 0;
}