Backtracking
LC #51Hard
N-Queens
Backtracking
AmazonGoogleMetaBloombergProblem
Place n queens on an n×n chessboard such that no two queens attack each other. Return all valid arrangements.
backtrackingmatrix
Constraints
- ›1 ≤ n ≤ 9
- ›No two queens can share the same row, column, or diagonal
Example
Input
n = 4Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]Why
Two distinct ways to place 4 queens on a 4×4 board with no conflicts