Leetcode 51. N-Queens

Problem

Leetcode 51 - N-Queens

Example:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Input: n = 1
Output: [["Q"]]

Approach

Using DFS, and tracking all the visited coordinates, we can solve the question for valid Queens

Here is the Python code for the solution:

class Solution:       
    def solveNQueens(self, n: int) -> List[List[str]]:
        col = set()
        posDiag = set()
        negDiag = set()

        res = []
        board = [['.'] * n for i in range(n)]

        def dfs(i):
            if i == n:
                copy = [''.join(row) for row in board]
                res.append(copy)
                return
            
            for c in range(n):
                if c in col or (i+c) in posDiag or (i-c) in negDiag:
                    continue
                
                col.add(c)
                posDiag.add(i+c)
                negDiag.add(i-c)
                board[i][c] = "Q"

                dfs(i+1)

                col.remove(c)
                posDiag.remove(i+c)
                negDiag.remove(i-c)
                board[i][c] = '.'
        
        dfs(0)
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n!)$

Space Complexity: $O(n^2)$