Example 1
ready- Input
n = 4- Expected
[ [ ".Q..", "...Q", "Q...", "..Q." ], [ "..Q.", "Q...", "...Q", ".Q.." ] ]- Why
- four queens have exactly two non-attacking arrangements
N-Queens
50 min · solveNQueens()One queen controls an entire row, column, and both diagonals. Placing n of them without
overlap turns a small board into a sharp search problem.
For an integer n, arrange n queens on an n × n board so no pair can attack each
other. Return every distinct arrangement. Represent one arrangement as n row strings
from top to bottom:
Qmarks a queen..marks an empty square.
The arrangements may come back in any order, but the rows inside each arrangement must
stay in top-to-bottom order. Some sizes have no solution; return [] for those sizes.
Constraints
1 <= n <= 9- Every returned board has exactly
nrows and one queen in each row. - No input produces more than 352 boards.
Hints
Rows and columns first
Place exactly one queen in each row. If you also forbid reused columns, row and column attacks disappear automatically.
Name each diagonal
Squares on one diagonal share row - column; squares on the other share
row + column. Two sets can tell whether either diagonal is occupied.
Choose, record, undo
For the current row, try each safe column. Record its column and two diagonal keys, search the next row, then remove all three records before trying the next column.
Follow-up
Mirror-image boards arrive in pairs. Could symmetry reduce the search while still returning every distinct board?
Visible cases
Examples
Example 2
ready- Input
n = 1- Expected
[ [ "Q" ] ]- Why
- the lone square holds the lone queen
Example 3
ready- Input
n = 2- Expected
[]- Why
- every placement of two queens creates an attack
Interview signal
Asked at
AmazonGoogleMeta
Enumerate column permutations
A permutation is an ordering that uses every item exactly once. Let position row
store the queen's column. Every permutation of columns already gives one queen per row
and per column; only diagonal conflicts remain to be filtered.
from itertools import permutations
def solve_n_queens(n: int) -> list[list[str]]:
result: list[list[str]] = []
for columns in permutations(range(n)):
down = {row - col for row, col in enumerate(columns)}
up = {row + col for row, col in enumerate(columns)}
if len(down) != n or len(up) != n:
continue
board = [
"." * col + "Q" + "." * (n - col - 1)
for col in columns
]
result.append(board)
return resultThere are n! permutations, and checking one touches n queens.
Time O(n! · n), space O(n) auxiliary, excluding returned boards.
Conflict-set backtracking
This is the backtracking pattern: place one queen, explore the remaining rows, then
remove that queen before trying its neighbor. Three sets make each safety check O(1):
occupied columns, row - column diagonals, and row + column diagonals.
def solve_n_queens(n: int) -> list[list[str]]:
result: list[list[str]] = []
columns: set[int] = set()
down_diagonals: set[int] = set()
up_diagonals: set[int] = set()
placement: list[int] = []
def search(row: int) -> None:
if row == n:
result.append([
"." * col + "Q" + "." * (n - col - 1)
for col in placement
])
return
for col in range(n):
down = row - col
up = row + col
if col in columns or down in down_diagonals or up in up_diagonals:
continue
placement.append(col)
columns.add(col)
down_diagonals.add(down)
up_diagonals.add(up)
search(row + 1)
placement.pop()
columns.remove(col)
down_diagonals.remove(down)
up_diagonals.remove(up)
search(0)
return resultThe search never explores a placement that already attacks a queen. Its conventional worst-case bound is time O(n!). Space O(n) auxiliary for the placement, sets, and call stack, excluding returned boards.
Every completed path has one queen in each row, and the three sets guarantee distinct
columns and diagonals. Those facts are also why n = 2 and n = 3 naturally finish
with no boards rather than needing special cases.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[
[
".Q..",
"...Q",
"Q...",
"..Q."
],
[
"..Q.",
"Q...",
"...Q",
".Q.."
]
]Run: visible + custom · Submit: full suite