Place n queens on an n x n chessboard so that no two queens attack each other (no two share a row, a column or a diagonal). Return every distinct arrangement. Each arrangement is a list of n strings, one per row, where Q is a queen and . is an empty square. The arrangements may be returned in any order.
- 1 <= n <= 9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every way to put n queens on n^2 squares is astronomically slow, and even trying every permutation of columns is O(n! * n) if we only check at the end. Since each row must hold exactly one queen, we place queens row by row and check safety immediately, abandoning a branch as soon as a queen is attacked. Squares on the same diagonal share the value r - c, and squares on the same anti-diagonal share r + c, so three sets answer "is this square attacked?" in constant time.
Algorithm
- Start with an empty board and three empty sets:
cols,diag(r - c) andanti(r + c). - Define
backtrack(r). Ifr == n, convert the board to strings and record it. - For each column
c, skip it ifc,r - corr + cis already used. - Otherwise place the queen, add to the three sets, recurse with
r + 1, then remove the queen and the set entries.
O(n!) roughly, since each row has fewer safe columns than the lastSpace: O(n^2) for the board, O(n) for the sets and recursionclass Solution: def solveNQueens(self, n: int) -> List[List[str]]: board = [["."] * n for _ in range(n)] cols, diag, anti = set(), set(), set() res = []Β 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 diag or (r + c) in anti: continue # square is attacked board[r][c] = "Q" cols.add(c); diag.add(r - c); anti.add(r + c) backtrack(r + 1) cols.remove(c); diag.remove(r - c); anti.remove(r + c) board[r][c] = "."Β backtrack(0) return res