N-Queens
Problem
Place n queens on an n x n chessboard so that no two share a row, a column, or a diagonal. Return every distinct board arrangement, drawing queens as "Q" and empty squares as ".".
Examples
Constraints
- • 1 <= n <= 9
Hints & approach
Hint 1
Every row holds exactly one queen, so place them one row at a time.
Hint 2
Keep sets of occupied columns and diagonals so each safety check is O(1).
Hint 3
Squares on the same diagonal share row - col; on the same anti-diagonal they share row + col.
Approachtry the hints first
Recurse row by row. For the current row, try each column that is not in the used-columns set, the row - col set, or the row + col set. Place the queen by adding to all three sets, recurse on the next row, then remove it. When every row has a queen, render the column choices as strings and save the board. The set checks prune most of the n^n placements, leaving roughly n! work.
Time O(n!) · Space O(n)