51. N-Queens

How to solve N-Queens (LeetCode 51): the approach in brief

The problem

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Pattern

N-Queens is a Backtracking Patterns problem, in the N-Queens / Constraint Satisfaction subpattern. The pattern covers subsets, permutations, combinations, N-Queens, and word search

Solve N-Queens and Sudoku using backtracking with constraint propagation.

Approach outline

1. Consider using backtracking to explore all possible placements of queens row by row, ensuring at each step that the current placement doesn't violate the constraints.
2. To efficiently check if a queen can be placed, track columns and diagonals that are already occupied by previously placed queens instead of scanning the entire board every time.
3. Remember that the diagonals can be identified by the sums and differences of row and column indices, which allows constant-time checks for conflicts.

Complexity

The reference solution runs in O(N!) time and O(N^2) space.

Asked at

N-Queens has been reported in interviews at Facebook, Microsoft, Amazon, ByteDance, Apple, Adobe.