Backtracking
N-Queens
DESCRIPTION (inspired by Leetcode.com)
You're arranging a chess tournament and need to set up n queens on an n × n chessboard for a special demonstration. The challenge is to place all queens such that no two queens threaten each other.
In chess, a queen can attack any piece on the same row, column, or diagonal. Find all distinct arrangements where all n queens can coexist peacefully.
Constraints:
- 1 <= n <= 9
Example 1:
Input:
n = 4
Output:
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There are two distinct arrangements for 4 queens on a 4×4 board where no queen attacks another.
Example 2:
Input:
n = 1
Output:
[["Q"]]
Building Intuition
The Approach
See it in action
How It Works
Checking Validity
The Complete Algorithm
Walkthrough
Phase 1: Initial Exploration
Phase 2: First Backtrack (Row 2 → Row 1)
Phase 3: Deep Backtrack (Row 3 → Row 2 → Row 1 → Row 0)
Phase 4: Finding the First Solution
Phase 5: Continuing to Find All Solutions
Solution
Optimization: Use Sets for O(1) Conflict Check
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium
Unlock Premium Coding Content
On This Page
Building Intuition
The Approach
See it in action
How It Works
Checking Validity
The Complete Algorithm
Walkthrough
Phase 1: Initial Exploration
Phase 2: First Backtrack (Row 2 → Row 1)
Phase 3: Deep Backtrack (Row `3` → Row `2` → Row `1` → Row `0`)
Phase 4: Finding the First Solution
Phase 5: Continuing to Find All Solutions
Solution
Optimization: Use Sets for O(1) Conflict Check