N Queens

Back to problems

Leetcode

Medium

Backtracking

Recursion

Arrays

Matrices

Google

Given an integer $n$ , place $n$ queens on an $n \times n$ chessboard so that no two queens can attack each other.

A queen attacks horizontally, vertically, and diagonally. Return every distinct valid board configuration.

Each configuration should be represented as an array of strings, where each string describes one row of the board using . for an empty square and Q for a queen.

Input Format

A single integer n representing the size of the board and the number of queens to place.

Output Format

Return a list of all valid board configurations.
Each configuration is an array of n strings of length n.
Use Q for a queen and . for an empty cell.

Constraints

$1 \le n \le 9$
Return all distinct valid solutions.
The number of solutions may be large for bigger n, but fits in memory for the given bounds.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 4

Output

[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation

There are two valid ways to place 4 queens on a 4x4 board without any attacks. Each row contains exactly one queen, and no two queens share a column or diagonal.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress