N-Queens
Asked at Google
Problem
Place N queens on an N×N chessboard so that no two queens attack each other. Return all distinct solutions where each solution contains a distinct board configuration. The classic backtracking problem that tests constraint satisfaction and pruning techniques.
Asked At
| Company | Difficulty | |
|---|---|---|
| HARD | View all Google questions → |
How to Think About It
Try placing queens row by row, checking each column for validity
Use three sets to track occupied columns, positive diagonals, and negative diagonals
Prune early by checking if current partial placement is still valid
Backtrack immediately when a conflict is detected rather than continuing
Use Algorithm X with dancing links for optimal performance on large N
Optimal Approach
Use backtracking with three sets to track attacked positions. Place queens row by row. For each row, try every column. If a position is not attacked (not in same column, positive diagonal, or negative diagonal), place the queen and recurse to the next row. If placing a queen leads to a valid complete board, record the solution. Backtrack by removing the queen and trying the next column. The diagonal invariant is that all cells on the same positive diagonal share row+col, and all cells on the same negative diagonal share row-col.
What Trips People Up in Real Interviews
Clarify if you need to return all solutions or just count them
Mention the diagonal math: positive diagonal is row+col, negative is row-col
Explain the time complexity is O(N!) but pruning makes it much faster in practice
Discuss how the problem extends to the N-Queens counting variant
Show how to represent the board compactly as a 1D array of column positions
Solution Code
class Solution:
def solveNQueens(self, n: int) -> list[list[str]]:
result = []
cols = set()
pos_diag = set()
neg_diag = set()
board = [['.'] * n for _ in range(n)]
def backtrack(r):
if r == n:
result.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'
backtrack(r + 1)
cols.remove(c)
pos_diag.remove(r + c)
neg_diag.remove(r - c)
board[r][c] = '.'
backtrack(0)
return resultFrequently Asked Questions
What is the N-Queens problem?
Place N queens on an N×N chessboard so that no two queens attack each other. Return all distinct solutions where each solution contains a distinct board configuration. The classic backtracking problem that tests constraint satisfaction and pruning techniques.
How do you solve N-Queens?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask N-Queens?
N-Queens is asked at Google. It is a hard difficulty problem.
What are common mistakes on N-Queens?
- Clarify if you need to return all solutions or just count them
- Mention the diagonal math: positive diagonal is row+col, negative is row-col
- Explain the time complexity is O(N!) but pruning makes it much faster in practice
- Discuss how the problem extends to the N-Queens counting variant
- Show how to represent the board compactly as a 1D array of column positions