Peaceful Queens

Hard

Place size queens on a size × size chessboard so that none of them can capture another: no two queens may share a row, a column or a diagonal. Return every such arrangement. An arrangement is a list of size strings of length size, one string per board row from top to bottom; a square with a queen is marked 'Q' and an empty square is marked '.'. If there are no arrangements, return an empty list. The arrangements may be returned in any order.

Example 1

size=4 → [['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

A 4 × 4 board has exactly two arrangements in which no two queens attack each other.

Example 2

size=3 → []

On a 3 × 3 board some two of the three queens always attack each other, so there are no arrangements.

Example 3

size=1 → [['Q']]

Constraints

1 ≤ size ≤ 9

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Backtracking

Similar problems

Complete the Sudoku Hard Every Way to Space the Words Hard Words Hidden in a Letter Grid Hard Shortest Unambiguous Shorthand Hard Mirror Word Blocks Hard

Input

size=4

Expected

[['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

Run checks the first 3 tests in your browser. Submit checks all 11 tests on the server, hidden ones included.