N-Queens II Solutions in C++

// Source : https://oj.leetcode.com/problems/n-queens-ii/
// Author : Hao Chen
// Date   : 2014-08-22



#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int totalNQueens(int n); 
void solveNQueensRecursive(int n, int currentRow, vector<int>& solution, int& result); 
bool isValid(int attemptedColumn, int attemptedRow, vector<int> &queenInColumn); 


int totalNQueens(int n) {
    int result=0;
    vector<int> solution(n);

    solveNQueensRecursive(n, 0, solution, result);

    return result;    
}

// the solution is same as the "N Queens" problem.
void solveNQueensRecursive(int n, int currentRow, vector<int>& solution, int& result) {

    for (int i = 0; i < n; i++) {
        if (isValid(i, currentRow, solution) ) {
            if (currentRow+1 == n){
                result++;
                continue;
            }
            solution[currentRow] = i;
            solveNQueensRecursive(n, currentRow+1, solution, result);
        }
    } 
}


bool isValid(int attemptedColumn, int attemptedRow, vector<int> &queenInColumn) {

    for(int i=0; i<attemptedRow; i++) {
        if (attemptedColumn == queenInColumn[i]  || 
            abs(attemptedColumn - queenInColumn[i]) == abs(attemptedRow - i)) {
            return false;
        } 
    }
    return true;
}



int main(int argc, char** argv)
{
    int n = 8;
    if (argc>1){
        n = atoi(argv[1]);
    }
    
    int result = totalNQueens(n);
    
    cout << n << " Queens, total = " << result << endl;
    
    return 0;
}

#include <functional>

class Solution {
public:
    int totalNQueens(int n) {
        int upperlim = (1 << n) - 1, sum = 0;
        std::function<void(int, int, int)> dfs = [&](int row, int l, int r)
        {
            if (row == upperlim) { ++sum; return; }
            for (int cur = upperlim & (~(row|l|r)), pos = 0; cur; dfs(row+pos, (l+pos)<<1, (r+pos)>>1))
            {
                pos = cur & (-cur);
                cur -= pos;
            }
        };
        dfs(0, 0, 0);
        return sum;
    }
};

/// Source : https://leetcode.com/problems/n-queens-ii/
/// Author : liuyubobobo
/// Time   : 2018-01-07

#include <iostream>
#include <vector>

using namespace std;


/// Basic Recursive
/// Time Complexity: O(n^n)
/// Space Complexity: O(n)
class Solution {
public:
    int totalNQueens(int n) {

        vector<int> row;
        vector<bool> col(n, false), dia1(2 * n - 1, false), dia2(2 * n - 1, false);

        return dfs(n, 0, row, col, dia1, dia2);
    }

private:
    int dfs(int n, int index, vector<int>& row,
            vector<bool>& col, vector<bool>& dia1, vector<bool>& dia2){

        if(index == n)
            return 1;

        int res = 0;
        for(int i = 0; i < n; i ++)
            if(!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]){
                row.push_back(i);
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;

                res += dfs(n, index + 1, row, col, dia1, dia2);

                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
                row.pop_back();
            }
        return res;
    }
};


int main() {

    return 0;
}