PPractick

The problem

A chess-puzzle app wants to show players every way to place n queens on an n × n board so that no two queens attack each other: no two share a row, a column, or a diagonal. Each row must contain exactly one queen, so the search places queens row by row. A column is allowed only if no earlier queen covers its column, its "" diagonal (constant row − col) or its "/" diagonal (constant row + col). Three boolean arrays make each check O(1).

Example: n = 4 → two boards, .Q.. / ...Q / Q... / ..Q. and ..Q. / Q... / ...Q / .Q...

Function signature

vector<vector<string>> solveNQueens(int n);  // each board: n strings of '.' and 'Q'

Test cases

Input n	Output	Explanation
4	[".Q..","...Q","Q...","..Q."] ["..Q.","Q...","...Q",".Q.."]	2 solutions
1	["Q"]
2	(none)
3	(none)
8	92 solutions	The classic eight-queens puzzle

(Confirm: 1 ≤ n ≤ 9; any order of boards is acceptable; this solution lists them in column order of the first row.)

How interviewers phrase it

• "Place n queens on an n x n chessboard so that no two attack each other; return all distinct solutions" (LeetCode 51).
• The counting version is LeetCode 52.

Clarifying questions to ask

1. Return the boards, or only the count?
2. How large can n be? (Up to about 9 for listing boards.)
3. What format should a board use? (Strings of '.' and 'Q'.)

Follow-ups to expect

1. "Why go row by row?"
2. "How do you check diagonals in O(1)?"
3. "What's the complexity?"
4. "Can you make it faster?"
5. "Does symmetry help?"

Related questions

• Letter Combinations of a Phone Number Hard
• Palindrome partitioning Hard
• Word Search Hard
• Rat in a Maze Hard
• M Coloring Problem Hard
• Sudoku Solver Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in