Backtracking
N-Queens
hard
Count: 10
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