52. N-Queens II

52. N-Queens II (Hard)

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.

 

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 9

Companies:
Amazon, Zenefits

Related Topics:
Backtracking

Similar Questions:

• N-Queens (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/n-queens-ii/
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N)
class Solution {
    vector<bool> col, hill, dale;
    int n;
    int dfs(int i) {
        if (i == n) {
            return 1;
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            int h = i + j, d = i + n - 1 - j;
            if (col[j] || hill[h] || dale[d]) continue;
            col[j] = hill[h] = dale[d] = true;
            ans += dfs(i + 1);
            col[j] = hill[h] = dale[d] = false;
        }
        return ans;
    }
public:
    int totalNQueens(int n) {
        this->n = n;
        col.assign(n, false);
        hill.assign(2 * n - 1, false);
        dale.assign(2 * n - 1, false);
        return dfs(0);
    }
};