Recursion and Backtracking Searching with constraints
331. N-Queens
You are given an integer n. Place n queens on an n × n chessboard so that no two queens attack each
other, and return every board that does this.
A queen attacks every square in its row, in its column and on both of its diagonals, however far away. So on a valid board, no two queens share a row, a column or a diagonal.
Draw each board as n strings, one per row from top to bottom. In each string, Q is a queen and . is
an empty square. The boards can come back in any order, and any order is accepted. The examples sort the
boards, comparing them row by row.
Example 1
Input: n = 4
[["..Q.","Q...","...Q",".Q.."],
[".Q..","...Q","Q...","..Q."]]Explanation: Two boards work. In the first, the queens stand in columns 2, 0, 3 and 1, from the top row down. The second is its mirror image, and it counts as a different board.
Example 2
Input: n = 1
[["Q"]]Explanation: A single queen on a 1 × 1 board has no other queen to attack.
Example 3
Input: n = 2
[]Explanation: Any two squares of a 2 × 2 board share a row, a column or a diagonal. No board works, so the answer is an empty list.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ n ≤ 10
Clarifying questions
What you would ask an interviewer before writing any code.