What is the brute force approach and complexity for N-Queens?

Try all n! column orders, then check the diagonals of each one with time complexity O(n! · n²) and space complexity O(n).

What is the optimal approach and complexity for N-Queens?

The same row-by-row search, but three bool arrays answer each check in O(1) with optimal time complexity O(n!) and space complexity O(n).

How do you identify the pattern for N-Queens?

Look for key signals in the prompt: "no two queens attack each other" indicates A rule on pairs of queens: they may not share a column or a diagonal.; "place n queens on an n × n board" indicates One queen per row. The search places one item per row and only chooses its column.; "return every board" indicates We need all valid placements, so the search must keep going after the first answer..

N-Queens

Hard·LeetCode #51 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given a whole number n. Place n queens on an n × n chessboard so that no two queens attack each other. A queen attacks every square in its row, its column, and both diagonals.

Return every valid placement. Draw each one as a board of n strings of length n: Q is a queen and . is an empty square. The order of the boards does not matter.

Input

An integer n.

Output

A list of every valid board. Each board is a list of n strings, each of length n.

Example 1

Input: n = 4

Output: [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]

There are two solutions. Each one has exactly one queen per row and per column, and no two queens share a diagonal.

Example 2

Input: n = 1

Output: [["Q"]]

A single queen on a 1 × 1 board is a valid placement.

Constraints

• 1 ≤ n ≤ 9

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“no two queens attack each other”

→ A rule on pairs of queens: they may not share a column or a diagonal.

“place n queens on an n × n board”

→ One queen per row. The search places one item per row and only chooses its column.

“return every board”

→ We need all valid placements, so the search must keep going after the first answer.

Approach Complexity Ladder

Brute Force — try every column order, check diagonals lastO(n! · n²)O(n)

Try all n! column orders, then check the diagonals of each one

Better — row by row, scan the board for each new queenO(n! · n)O(n²)

Place one queen per row; before placing, scan its column and both diagonals above it

Optimal — three bool arrays for O(1) checksO(n!)O(n)

The same row-by-row search, but three bool arrays answer each check in O(1)

Brute Force Intuition

Put one queen in each row, and make the columns different. Those are exactly the n! orders of the columns 0 to n − 1. A column order already gives one queen per row and per column, so only the diagonals are left to check. Keep the orders that pass.

Recognition rule for this sub-pattern:

Place items one by one, checking the rules before each placement. Prune as early as possible.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture