52

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 {
public:
    int totalNQueens(int n) {
        vector<bool> col(n), hill(2 * n - 1), dale(2 * n - 1);
        function<int(int)> dfs = [&](int i) { // for each i-th row
            if (i == n) return 1;
            int ans = 0;
            for (int j = 0; j < n; ++j) { // try putting on the j-th column
                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;
        };
        return dfs(0);
    }
};