51. N Queens

Problem Statement in English

You’ve to place n queens on an n x n chessboard such that no two queens attack each other.

Approach

This is a classic backtracking problem, and it’s more of an implementation problem.

We use backtracking for the actual placement paired with $O(1)$ checks to see if the placement is valid.

For the check we use three sets to keep track of the columns and diagonals that are already occupied by queens. For the positive diagonals shaped like / we use r + c, and for the negative diagonals shaped like \ we use r - c.

The reason we’re able to remove a queen from a diagonal with a set rather than a hashmap is that when we place a queen and recurse forward it’s guaranteed that there were no queens on that diagonal before, and when we backtrack we remove the queen from that diagonal, so it’s guaranteed that there are no queens on that diagonal after we remove it. Hence, a set suffices.

And we are done!

Solution in Python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        cols = set()
        pos_diag = set()  # r + c
        neg_diag = set()  # r - c

        board = [["."] * n for _ in range(n)]

        def dfs(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 pos_diag or (r - c) in neg_diag:
                    continue

                cols.add(c)
                pos_diag.add(r + c)
                neg_diag.add(r - c)
                board[r][c] = "Q"

                dfs(r + 1)

                cols.remove(c)
                pos_diag.remove(r + c)
                neg_diag.remove(r - c)
                board[r][c] = "."

        dfs(0)
        return res

Complexity

• Time: $O(n!)$
  Since we are trying to place the queens in all possible ways.

• Space: $O(n^2)$
  Since we are using a 2D array to store the board state.

And we are done.