N-Queens — all solutions
Problem
Place n queens on an n × n board so that no two attack each other (same row, column or diagonal). Return every distinct board.
Example 1
Input: n = 4 Output: [".Q..","...Q","Q...","..Q."] and ["..Q.","Q...","...Q",".Q.."]
Also asked as: Printing all solutions in N-Queen Problem
Test cases
Case 1
Input: 4 Expected (any order): [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Case 2
Input: 1 Expected (any order): [["Q"]]
Case 3
Input: 3 Expected (any order): []
View solutionHide solution1 approach
1. Row-by-row with column & diagonal sets
Time O(N!)Space O(N)
Place one queen per row. A column is free if it is not in `cols`, and diagonals are tracked by r−c and r+c. Recurse, backtrack.
function solveNQueens(n) { const res = [], pos = []; const cols = new Set(), d1 = new Set(), d2 = new Set(); const bt = (r) => { if (r === n) { res.push(pos.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))); return; } for (let c = 0; c < n; c++) { if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue; cols.add(c); d1.add(r - c); d2.add(r + c); pos.push(c); bt(r + 1); cols.delete(c); d1.delete(r - c); d2.delete(r + c); pos.pop(); } }; bt(0); return res;}