51. N-Queens

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 all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: 4

Output:

[

// Solution 1

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

// Solution 2

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

]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

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 {
    private Set<Integer> col = new HashSet<>();
    private Set<Integer> hill = new HashSet<>();
    private Set<Integer> dale = new HashSet<>();
    
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> resultList = new ArrayList<>();
        backtrack(resultList, new ArrayList<String>(), 0, n);
        return resultList;
    }
    
    private void backtrack(List<List<String>> resultList,
                           List<String> currList,
                           int row,
                           int n) {
        if(row == n) {
            resultList.add(new ArrayList(currList));
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(col.contains(i) || 
                hill.contains(row+i) || 
                dale.contains(row-i)) {
                continue;
            }

            char[] rowArr = new char[n];
            Arrays.fill(rowArr, '.');
            rowArr[i] = 'Q';
            String rowStr = new String(rowArr);

            currList.add(rowStr);
            col.add(i);
            hill.add(row+i);
            dale.add(row-i);

            backtrack(resultList, currList, row+1, n);

            currList.remove(currList.size()-1);
            col.remove(i);
            hill.remove(row+i);
            dale.remove(row-i);
        }
    }
}

Solution 2

Follow up

• Check if a Queen can attack a given cell on chessboard - GFG

• Check if the given chessboard is valid or not - GFG

• Job Sequencing Problem - GFG