52. N-Queens II

Description

The n-queens puzzle is the problem of placing n queens on an n×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.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode
• ProgramCreek

• YouTube

Examples

Example 1

Input: 4

Output: 2

Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.

[

// Solution 1

[ ".Q..", "...Q", "Q...", "..Q." ],

// Solution 2

[ "..Q.", "Q...", "...Q", ".Q.." ]

]

Solutions

Solution 1

/**
 * Time complexity : O(N!). There is N possibilities to put the first queen, 
 *    not more than N (N - 2) to put the second one, not more than N(N-2)(N-4) 
 *    for the third one etc. In total that results in O(N!) time complexity.
 * Space complexity : O(N) to keep an information about diagonals and rows.
 */

class Solution {
    public int totalNQueens(int n) {
        if(n < 2) return 1;
        if(n > 1 && n < 4) return 0;
        
        boolean[] cols = new boolean[n];
        boolean[] hills = new boolean[n*2 - 1];
        boolean[] dales = new boolean[n*2 - 1];
            
        return backtrack(cols, hills, dales, 0, n, 0);
    }
    
    private int backtrack(boolean[] cols, 
                            boolean[] hills, 
                            boolean[] dales, 
                            int row, 
                            int n, 
                            int count) {
        for(int col = 0; col < n; col++) {
            if(cols[col] || hills[row+col] || dales[row-col+n-1]) {
                continue;
            }
            cols[col] = true;
            hills[row+col] = true;
            dales[row-col+n-1] = true;

            if(row+1 == n) {
                count++;
            } else {
                count = backtrack(cols, hills, dales, row+1, n, count);
            }

            cols[col] = false;
            hills[row+col] = false;
            dales[row-col+n-1] = false;
        }
        return count;
    }
}

Follow up