LeetCode 52 - N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

 

private int[] col4Row;
private int total;
public int totalNQueens(int n) {
    col4Row = new int[n];
    total = 0;
    placeQueen(0, n);
    return total;
}

public void placeQueen(int row, int n) {
    if(row == n) {
        total++;
        return;
    }
    for(int i=0; i<n; i++) {
        col4Row[row] = i;
        if(check(row)) {
            placeQueen(row+1, n);
        }
    }
}

public boolean check(int row) {
    for(int i=0; i<row; i++) {
        int diff = Math.abs(col4Row[i] - col4Row[row]);
        if(diff == 0 || diff == row - i) return false;
    }
    return true;
}

 

C++的版本：

int totalNQueens(int n) {
    int sum = 0;
    vector<int> cols(n);
    auto check = [&](int row) {
        for(int i=0; i<row; i++) {
            int diff = abs(cols[i] - cols[row]);
            if(!diff || diff == row-i) return false;
        }    
        return true;
    };
    function<void(int)> solve = [&](int row) {
        if(row == n) {
            sum++; return;
        }
        for(int i=0; i<n; i++) {
            cols[row] = i;
            if(check(row))
                solve(row+1);
        }
    };
    solve(0);
    return sum;
}