[LeetCode] N-Queen II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

vector<vector<string> > out;

    int num;

    // main function

    int totalNQueens(int n) {

        if (n==0) return 0;

        vector<int> A(n, -1);   // Stores state for current solution, A[i]=j indicates row i, col j has a queen

        num = 0;

        placeQueen(A, 0, n);    // starts from row 0

        return num;

    }

 

    // iterate thru row

    void placeQueen(vector<int> A, int cur, int n){ // cur - current row #

        if (cur==n) num++;

        else {

            for (int i=0; i<n; i++){    // traverse thru each row, i-col

                A[cur]=i;

                if (isValid(A,cur)) {

                    placeQueen(A, cur+1, n);

                }

            }

        }

    }

 

    // To check if the current position is valid to place a queue

    bool isValid(vector<int> A, int row){

        for (int k=0; k<row; k++) { // row iteration

            if (A[k]==A[row] || (abs(A[k]-A[row])==(row-k))) {

                return false;

            }

        }

        return true;

    }

Read full article from Just Codings: [LeetCode] N-Queens I && II