51.N-Queens(Hard).md

51. N-Queens (Hard)

Date and Time: Jul 28, 2024, 21:34 (EST)

Link: https://leetcode.com/problems/n-queens/

Question:

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 all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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

Example 1:

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Example 2:

Input: n = 1

Output: [["Q"]]

Constraints:

• 1 <= n <= 9

Walk-through:

We first create 3 sets "cols(), posDiag(), negDiag()" and initialize the board board = [['.'] * n for i in range(n)].

In backtrack(), the base case is if r == n, we do "".join(row) for row in board to append all the rows into the list in res.

In the for-loop, after we place 'Q' we will add this column c into cols(), posDiag(), negDiag() and change board[r][c] = "Q", then we call backtrack(r+1) to test current configuration.

If in the r+1th row, we couldn't place Q, we return back to the previous rth row and remove c from these three sets and change back board[r][c] = ".".

Next, we back in the rth row and we in the for loop to try the next c and call backtrack(r+1) again to test if this is the right placement...

About posDiag and negDiag:

[3, 0], [2, 1], [1, 2] are all in the positive diagonal (bottom-left -> top-right), because they all have the same (r + c) = 3 value.

[0, 0], [1, 1], [2, 2], [3, 3] all have the same (r - c) = 0 value, so they are all in the negative diagnoal (top-left -> bottom-right).

[['Q', '.', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['Q', '.', '.', '.'], ['.', '.', 'Q', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['Q', '.', '.', '.'], ['.', '.', '.', 'Q'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['Q', '.', '.', '.'], ['.', '.', '.', 'Q'], ['.', 'Q', '.', '.'], ['.', '.', '.', '.']]
[['.', 'Q', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['.', 'Q', '.', '.'], ['.', '.', '.', 'Q'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['.', 'Q', '.', '.'], ['.', '.', '.', 'Q'], ['Q', '.', '.', '.'], ['.', '.', '.', '.']]
[['.', 'Q', '.', '.'], ['.', '.', '.', 'Q'], ['Q', '.', '.', '.'], ['.', '.', 'Q', '.']]
[['.', '.', 'Q', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['.', '.', 'Q', '.'], ['Q', '.', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['.', '.', 'Q', '.'], ['Q', '.', '.', '.'], ['.', '.', '.', 'Q'], ['.', '.', '.', '.']]
[['.', '.', 'Q', '.'], ['Q', '.', '.', '.'], ['.', '.', '.', 'Q'], ['.', 'Q', '.', '.']]
[['.', '.', '.', 'Q'], ['.', '.', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['.', '.', '.', 'Q'], ['Q', '.', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]
[['.', '.', '.', 'Q'], ['Q', '.', '.', '.'], ['.', '.', 'Q', '.'], ['.', '.', '.', '.']]
[['.', '.', '.', 'Q'], ['.', 'Q', '.', '.'], ['.', '.', '.', '.'], ['.', '.', '.', '.']]

Python Solution:

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        cols = set()
        negDiag, posDiag = set(), set()
        res = []
        board = [['.'] * n for i in range(n)]
        def backtrack(r):
            if r == n:
                res.append(["".join(row) for row in board])
                return
            for c in range(n):
                if c in cols or (r+c) in posDiag or (r-c) in negDiag:
                    continue
                cols.add(c)
                negDiag.add(r-c)
                posDiag.add(r+c)
                board[r][c] = 'Q'
                backtrack(r+1)
                
                cols.remove(c)
                negDiag.remove(r-c)
                posDiag.remove(r+c)
                board[r][c] = '.'
        backtrack(0)
        return res

Time Complexity: $O(n * n)$
Space Complexity: $O(n * n)$, because we created a board by n * n.

Java Solution:

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        Set<Integer> cols = new HashSet<>();
        Set<Integer> posDiag = new HashSet<>();
        Set<Integer> negDiag = new HashSet<>();
        backtrack(0, board, cols, posDiag, negDiag, res);
        return res;
    }
    private void backtrack(int r, char[][] board, Set<Integer> cols, Set<Integer> posDiag, Set<Integer> negDiag, List<List<String>> res) {
        if (r == board.length) {
            List<String> path = new ArrayList<>();
            for (int i = 0; i < board.length; i++) {
                path.add(new String(board[i]));
            }
            res.add(path);
            return;
        }
        for (int c = 0; c < board[0].length; c++) {
            if (cols.contains(c) || posDiag.contains(r+c) || negDiag.contains(r-c)) {
                continue;
            }
            cols.add(c);
            posDiag.add(r+c);
            negDiag.add(r-c);
            board[r][c] = 'Q';
            backtrack(r+1, board, cols, posDiag, negDiag, res);
            cols.remove(c);
            posDiag.remove(r+c);
            negDiag.remove(r-c);
            board[r][c] = '.';
        }
    }
}

C++ Solution:

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        unordered_set<int> cols, posDiag, negDiag;
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));        
        backtrack(n, 0, board, cols, posDiag, negDiag, res);
        return res;
    }
    void backtrack(int n, int r, vector<string>& board, unordered_set<int>& cols, unordered_set<int>& posDiag, unordered_set<int>& negDiag, vector<vector<string>>& res) {
        if (n == r) {
            res.push_back(board);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (cols.count(c) || posDiag.count(r+c) || negDiag.count(r-c)) {
                continue;
            }
            cols.insert(c);
            posDiag.insert(r+c);
            negDiag.insert(r-c);
            board[r][c] = 'Q';
            backtrack(n, r+1, board, cols, posDiag, negDiag, res);
            cols.erase(c);
            posDiag.erase(r+c);
            negDiag.erase(r-c);
            board[r][c] = '.';
        }
    }
};

Runtime and Memory comparison

Language	Runtime	Memory
Python3	38 ms	16.9 MB
Java	4 ms	44.8 MB
C++	12 ms	12.6 MB