18图灵班作业14：N-Queens问题

思路

总体的思路是深度优先搜索，枚举棋子摆放的位置。问题的难点就是如何剪枝，让解答树尽可能的少。
1. 以行为单位，而不是以(x,y)为单位进行枚举。emmm..肯定的啦，每行只能放一个。
2. 通过一个数组来记录某一列是否被放有棋子，如果放有则不再放置。
3. 建立一个数学关系，让在同一斜行（对角线？）的点的横纵坐标经过该数学关系运算后为一个定值。这个关系有两种。

• 一种是两点斜率为-1，这时有(x1-y1)=(x2-y2),又因为差值可能为负，所以再+n映射到一个恒正范围内。
• 另一种是两斜率为1，这时保持两点的x不变，y'=n+1-y(相当与x轴不变，翻转y轴使得两点斜率变为1),然后再用第一种情况的公式映射成一个具体的数值。
  最后建立两个数组，即可记录正负对角线上是否有冲突。

代码

class Solution {
public:
    bool isOccupiedy[20];
    bool isDiagonalA[20];
    bool isDiagonalB[20];
    int ansX[16];
    vector<vector<string>> ans;
    void dfs(int nowy,int n){
        if(nowy==n+1){
            vector<string> tmpAns;
            for(int i=1;i<=n;i++){
                string tmpStrAns="";
                for(int j=1;j<=n;j++){
                    if(ansX[i]==j) tmpStrAns+="Q";
                    else tmpStrAns+=".";
                }
                tmpAns.push_back(tmpStrAns);
            }
            ans.push_back(tmpAns);
            return;
        }
        for(int nowx=1;nowx<=n;nowx++){
            int DiagonalA=nowx-nowy+n;
            int DiagonalB=nowx-(n+1-nowy)+n;
            // !isOccupiedy[DiagonalA]&&!isOccupiedy[DiagonalB]
            if(!isOccupiedy[nowx]&&!isDiagonalA[DiagonalA]&&!isDiagonalB[DiagonalB]){
                ansX[nowy]=nowx;
                isOccupiedy[nowx]=true;
                isDiagonalA[DiagonalA]=true;
                isDiagonalB[DiagonalB]=true;
                dfs(nowy+1,n);
                isOccupiedy[nowx]=false;
                isDiagonalA[DiagonalA]=false;
                isDiagonalB[DiagonalB]=false;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        dfs(1,n);
        return ans;
    }
};