lintcode N皇后问题

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
样例
对于4皇后问题存在两种解决的方案：

[".Q..", // Solution 1

 "...Q",

 "Q...",

 "..Q."],

["..Q.", // Solution 2

 "Q...",

 "...Q",

 ".Q.."]

不能相互攻击指的是横的竖的和斜的一条线上只能有一个Q。
这道题我们使用回溯法，也就是深度优先搜索。
在一个点的四个方向上会有已经存在Q的可能，分别是同一行同一列以及该点的45度角和135角。我们在递归的过程中，是一行一行增加的，因此不需要考虑在同一行上存在Q的情况，那么现在还剩下三种情况。
对于一个n行n列的棋盘，一共有n列，2n-1个45度角，2n-1个135度角，当我们选中某一点[row][col]，需要比较的列是第col个，45度角是第row+col个，135度角是第n-1+col-row个（都是从0开始计数），下面是一个n=3的例子。

| | |                / / /             \ \ \
O O O               O O O               O O O
| | |              / / / /             \ \ \ \
O O O               O O O               O O O
| | |              / / / /             \ \ \ \
O O O               O O O               O O O
| | |              / / /                 \ \ \
3 列             5 个45° 角             5 个135° 角   n = 3

我们可以使用一个数组来记录有无Q的情况。我们需要的数组大小为n+(2n-1)+(2n-1)=5n-3，当我们选中某一点[row][col]时，标识列上是否有Q的数为数组的第col个数，45度角为第n+row+col个，135度角为第n+2n-1+n-1+col-row个。代码如下：

class Solution {
public:
    /**
     * Get all distinct N-Queen solutions
     * @param n: The number of queens
     * @return: All distinct solutions
     * For example, A string '...Q' shows a queen on forth position
     */
    vector<vector<string> > solveNQueens(int n) {
        // write your code here
        vector<vector<string> > result;
        vector<string> nQueens(n,string(n,'.'));
        vector<int> flag(5 * n - 2,1);
        solveNQueens(result,nQueens,flag,0,n);
        return result;
    }
    void solveNQueens(vector<vector<string> > &res,vector<string> &nQueens,vector<int> flag,int row,int n) {
        if (row == n) {
            res.push_back(nQueens);
            return;
        }
        for (int col = 0;col < n;col++) {
            if (flag[col] && flag[n + row + col] && flag[4 * n - 2 + col - row]) {
                flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 0;
                nQueens[row][col] = 'Q';
                solveNQueens(res,nQueens,flag,row + 1,n);
                nQueens[row][col] = '.';
                flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 1;
            }
        }
    }
};

对于第二题，返回所有可能的个数就不介绍了，因为第一题是返回所有可能的结果。。当然不要返回result.size(),那样相当于走了弯路。