回溯法,以行为基准进行回溯,如果当前行列摆放皇后与之前的冲突,则不继续回溯,否则,继续下一行的回溯。

代码如下:

//
// Created by jt on 2020/9/29.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int totalNQueens(int n) {
        // write code here
        int res = 0;
        vector<int> vec;
        backtrack(vec, res, n);
        return res;
    }

    void backtrack(vector<int> &vec, int &res, int n) {
        if (vec.size() == n) { ++res; return; }
        for (int col = 0; col < n; ++col) {
            vec.push_back(col);
            if(!detectConflict(vec)) backtrack(vec, res, n);
            vec.pop_back();
        }
    }

    bool detectConflict(vector<int> &vec) {
        int curRow = vec.size() - 1, curCol = vec[curRow];
        for (int row = 0; row < curRow; ++row) {
            if (curCol == vec[row]) return true;
            if (curRow - row == abs(curCol - vec[row])) return true;
        }
        return false;
    }
};