Backtracking - Question 2

 Leetcode 52. N-Queens II

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Constraints:

1 <= n <= 9

Analysis:

The answer to the previous question can be used directly: just need to return the size of it.

For the coding part, we do not need to record the actual solution, so simplification of code can be done.

The idea is the same as the previous question: try to place a queen for each row. 

And we just removed the previous vectors to record the solution. Instead, we just count the number of solutions.

See the code below:

class Solution {
public:
    int totalNQueens(int n) {
        ps.resize(n);
        fill(ps.begin(), ps.end(), -1);
        bt(0, 0);
        return res;
    }
private:
    int res = 0;
    vector<int> ps;
    void bt(int r, int ct) {
        if(r == ps.size()) {
            if(ct == ps.size()) ++res;
            return;
        }
        for(int i=0; i<ps.size(); ++i) {
            if(isValid(r, i)) {
                ps[r] = i; // make a trial
                bt(r + 1, ct + 1);
                ps[r] = -1; // step back (or backtrack)
            }
        }
    }
    bool isValid(int id, int val) {
        for(int i=0; i<id; ++i) {
            if(ps[i] == -1) continue;
            if(ps[i] == val || abs(id - i) == abs(val - ps[i])) return false;
        }
        return true;
    }
};

 

Upper Layer