Backtracking · 042Hard
N-Queens
Place n queens on an n x n chessboard so that no two attack each other. Return all distinct solutions, each as a list of strings where 'Q' is a queen and '.' is empty.
Constraints
- 1 <= n <= 9
Examples
solveNQueens(4) -> [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]] solveNQueens(1) -> [["Q"]] solveNQueens(3) -> [] // no solution exists solveNQueens(2) -> [] // no solution here either solveNQueens(5) -> 10 distinct solutions solveNQueens(8) -> 92 distinct solutions // the classic board
Edge cases
- n = 2 and n = 3 have no solutions.
- n = 1 has exactly one.
Show the target complexity (spoiler)
- Naive
- O(n^n) time — try every square for every queen and validate at the end.
- Target
- Backtracking with column and two diagonal sets, pruning invalid placements immediately — roughly O(n!) with heavy pruning.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/10-backtracking/042-n-queens.js ./practice c 042