N Queens

Hard · Backtracking

You are given an integer n. Place n chess queens on an n by n board so that no two queens attack each other, meaning no two share a row, a column, or a diagonal. Return all distinct complete placements, where each placement is represented as a list of n strings (one per row), using 'Q' for a queen and '.' for an empty cell. The order of the placements in the result does not matter.

Examples

Input:  n = 1
Output: [["Q"]]
Why:    A single queen on the only cell is trivially safe.

Input:  n = 2
Output: []
Why:    On a 2x2 board any two queens would share a row, column, or diagonal, so no arrangement works.

Input:  n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Why:    These are the only two ways to place 4 non-attacking queens on a 4x4 board.

Constraints

1 <= n <= 9

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise N Queens

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of N Queens. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.