The N-Queens puzzle is the classic backtracking benchmark. Brute force over all placements is hopeless; backtracking with pruning (abandon a partial board as soon as two queens attack) makes it easy.
Given an integer n, return the number of distinct ways to place n queens on an n x n chessboard so that no two queens attack each other (no two share a row, column or diagonal).
Examples
Input: n = 4
Output: 2
Input: n = 1
Output: 1
Input: n = 3
Output: 0
Constraints
1 <= n <= 8- Target: backtracking with O(1) attack checks; n = 8 should take well under a second
Goals
- Place one queen per row and backtrack over the column choices
- Track attacked columns and diagonals with sets so each check is O(1)
- Prune the search early instead of validating complete boards