N 皇后

题目链接：N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

方法一：回溯

class Solution {
public:
    vector<vector<string>> ans;
    int m[15][15];
    bool check(int x,int y,int n) {
        for (int i = 0;i < x;i++) {
            if (m[i][y]) return false;
        }
        for (int i = 0;i < y;i++) {
            if (m[x][i]) return false;
        }
        int num = min(x,y);
        // 左上
        for (int i = 1;i <= num;i++) {
            if (m[x-i][y-i]) return false;
        }
        num = min(x,n-y);
        //右上
        for (int i = 1;i <= num;i++) {
            if (m[x-i][y+i]) return false;
        }
        num = min(n-x,n-y);
        
        return true;
    }
    void f(int n,int x) {
        if (x >= n) {
            vector<string> t;
            for (int i = 0;i < n;i++) {
                string s = "";
                for (int j = 0;j < n;j++) {
                    if (m[i][j] == 1) {
                        s += "Q";
                    }else {
                        s += ".";
                    }
                }
                t.push_back(s);
            }
            ans.push_back(t);
            return ;
        }
        for (int i = 0;i < n;i++) {
            if (check(x,i,n)) {
                m[x][i] = 1;
                f(n,x+1);
                m[x][i] = 0;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        f(n,0);
        return ans;
    }
};