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

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private boolean[] cols;
    private boolean[] hills;
    private boolean[] dales;
    
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> resultList = new ArrayList<>();
        if(n == 0) resultList.add(new ArrayList<>());
        if(n == 1) resultList.add(List.of("Q"));
        if(n > 3) {
            cols = new boolean[n];
            hills = new boolean[n*2 - 1];
            dales = new boolean[n*2 - 1];
            char[][] board = new char[n][n];
            for(char[] arr: board) {
                Arrays.fill(arr, '.');
            }
            backtrack(resultList, board, 0, n);
        }
        return resultList;
    }
    
    private void backtrack(List<List<String>> resultList,
                           char[][] board,
                           int row,
                           int n) {
        if(row == n) {
            ArrayList<String> tempList = new ArrayList();
            for(char[] arr: board) {
                tempList.add(new String(arr));
            }
            resultList.add(tempList);
            return;
        }
        
        for(int col = 0; col < n; col++) {
            if(cols[col] || hills[row+col] || dales[row-col+n-1]) {
                continue;
            }

            board[row][col] = 'Q';
            cols[col] = true;
            hills[row+col] = true;
            dales[row-col+n-1] = true;

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

            board[row][col] = '.';
            cols[col] = false;
            hills[row+col] = false;
            dales[row-col+n-1] = false;
        }
    }
}

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