The problem
A chess queen attacks every square in its row, its column and both of its diagonals. Place n queens on an n × n board so that no two attack each other.
Return every such arrangement, each as n strings — one per row, Q for a queen and . for an empty square — in any order.
Examples
- Input
n = 4
- Output
[[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
- Input
n = 1
- Output
[["Q"]]
Constraints
- 1 ≤ n ≤ 9
The idea
No two queens can share a row, so there is exactly one per row. Place them row by row: in row r, try each column that is not attacked, place a queen, move on to row r + 1; if a row has no safe column, go back and move the previous queen.
Checking “is this square attacked?” is one step with three sets. Squares on the same “\” diagonal all have the same r − c; on the same “/” diagonal, the same r + c. So a square is attacked exactly when its column, its r − c or its r + c is already taken.
- Time
- O(n!) — at most n choices in the first row, fewer in each after
- Space
- O(n²) — the board
Solution · every language run against every case
class Solution: def solveNQueens(self, n: int) -> List[List[str]]: # A queen attacks along its column and both diagonals. On one "\" diagonal r - c # is the same; on one "/" diagonal r + c is. So three sets say what is attacked. cols, down, up = set(), set(), set() board = [["."] * n for _ in range(n)] out = [] def place(r): # rows above r each hold one queen if r == n: out.append(["".join(row) for row in board]) return for c in range(n): if c in cols or r - c in down or r + c in up: continue cols.add(c); down.add(r - c); up.add(r + c) board[r][c] = "Q" place(r + 1) board[r][c] = "." # take it back and try the next column cols.remove(c); down.remove(r - c); up.remove(r + c) place(0) return out