N Queens II

Description

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

Example  
For n=4, there are 2 distinct solutions.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * Calculate the total number of distinct N-Queen solutions.
     * @param n: The number of queens.
     * @return: The total number of distinct solutions.
     */
    int totalNQueens(int n) {
        // write your code here
        if (n < 1) {
            return 0;
        }
        int result = 0;
        vector<int> row(n, 0);
        helper(result, row, n, 0);
        return result;
    }
    void helper(int& result, vector<int>& row, int n, int rownum) {
        if (rownum == n) {
            result++;
            return;
        }
        for (int i = 0; i < n; ++i) {
            // pruning
            if (!isValid(row, i, rownum)) {
                continue;
            }
            row[rownum] = i;
            helper(result, row, n, rownum + 1);
            row[rownum] = 0;
        }
        return;
    }
    bool isValid(vector<int>& row, int colnum, int rownum) {
        for (int i = 0; i< rownum; ++i) {
            // col conflict
            if (row[i] == colnum) {
                return false;
            }
            // cross conflict
            // diff of row, diff of col
            if (abs(i - rownum) == abs(row[i] - colnum)) {
                return false;
            }
        }
        return true;
    }
};

Similar problems

x

Tags

x