The N-Queens problem asks you to place N queens on an N x N chessboard so that no two queens threaten each other. Queens attack along rows, columns, and both diagonals.
For example, one valid solution for N = 4 places queens at positions (0,1), (1,3), (2,0), (3,2).
Explain your approach to solving this problem. How do you efficiently check whether placing a queen is safe? What is the time complexity?
How to approach it
- Hint 1
Place queens one row at a time -- since each row must have exactly one queen, you only need to decide the column for each row.
- Hint 2
To check safety efficiently, maintain sets for occupied columns, occupied main diagonals (row - col), and occupied anti-diagonals (row + col).
- Hint 3
When a placement fails, backtrack: remove the queen and try the next column in the same row.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.