题解 | #N皇后问题#

由题意可知，每行有且只有一个皇后， 那么问题就变成先对第一行放一个皇后，之后再第二行中找一个位置放置皇后，一直放到最后一行，如果最后一行有位置放，那么直接answer++，否则返回到上一级，继续试下一个点。

int Nqueen(int n) {
    int answer = 0;
    // 按顺序从第一行开始记录皇后所在的列
    vector<int> queenColunms(n, -1);
    check(queenColunms, 0, n, answer);
    return answer;
}

void check(vector<int>& queenColumns, int line, int& maxLine, int& answer) {
    // 这一行中皇后可下的位置
    vector<int> put(maxLine, 0);
    // 把之前行的皇后对这一行的影响记录下来，标记为1
    for(int i = 0; i < line; i++) {
        int pos = queenColumns[i];
        put[pos] = 1;
        if ((pos - (line - i)) >= 0) {
            put[pos - (line - i)] = 1;
        }
        if ((pos + (line - i)) < maxLine) {
            put[pos + (line - i)] = 1;
        }
    }
    // 找出剩余未被之前行皇后影响的格子，挨个放入皇后试验
    for (int i = 0; i < maxLine; i++) {
        if (put[i] == 0) {
            if (line == maxLine - 1) {
                answer ++;
                return;
            } else {
                queenColumns[line] = i;
                check(queenColumns, line + 1, maxLine, answer);
                queenColumns[line] = -1;
            }
        }
    }
}