题目：
51.N皇后
题解： 本题是回溯算法的经典例题，回溯算法是一种思想，它通常用递归实现。通常我们的回溯通过dfs（递归）实现，但是请务必清楚一点，dfs只是实现回溯算法的一种方法，它通常伴随着剪枝等一系列优化方案（这个是很玄学的，不作过多讨论）。
回溯算法的时间复杂度通常是很高的，本题中的N皇后问题，节点总数为 n + n^2 + n^3 + ... + n^n，不超过 O(n^(n+1))。处理每个节点需要向上扫描棋盘以免皇后互相攻击，需要 O(n) 时间。所以 N 皇后问题总时间不超过 O(n^(n+2))。
代码如下：
class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<string> board(n,string(n,'.')); //建立棋盘 vector<vector<string>> result;//可行的n皇后 backtrack(0,board,result);//进行回溯 return result; } void backtrack(int row,vector<string>& board,vector<vector<string>>& result) { if(row==board.size())//选择列表已空，即完成一个皇后棋盘 result.push_back(board); else{ for(int col=0;col<board.size();col++)//每一列都是一个选择 { //如果选择的这个位置会被攻击，则跳过 if(!isVaild(board,row,col))continue; /*choose过程*/ //注意这里的选择列表变小了，因为要进入下一行选皇后 //同时这里的决策路径也做出了决策，也就是这个点作为皇后了 board[row][col]='Q'; /*进行下一行的选择*/ backtrack(row+1,board,result); /*unchoose过程*/ //把这个选择移除决策路径了，也就是把这个皇后还原成点 //当然这个选择也重新加入选择列表了，注意这个选择列表为列 board[row][col]='.'; } } } //判断board[row][col]是否可以放置Q bool isVaild(vector<string>& board,int row,int col) { //检查正上方 for(int i=0;i<row;++i) if(board[i][col]=='Q')return false; //检查右斜上方 for(int i=row-1,j=col+1;i>=0&&j<board.size();i--,j++) if(board[i][j]=='Q')return false; //检查左斜上方 for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--) if(board[i][j]=='Q')return false; //不用检查下方，因为下方还没放置皇后 return true; } };