The problem. Place n queens on an n × n chessboard so that no two attack each other — no two share a row, a column or a diagonal. Return every distinct solution, each as a list of strings where "Q" is a queen and "." an empty square.
n = 4 -> [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]
n = 1 -> [["Q"]]
n = 2 or 3 -> [] (no solution)Every row holds exactly one queen, so the choices are simple: in row r, which column gets the queen? Try each column that isn't attacked, place the queen, move on to row r + 1, then remove it and try the next column. The attack check is the pruning, and it's what makes this fast: a queen is attacked if its column, its \ diagonal (cells with the same row − col) or its / diagonal (the same row + col) already has a queen. Keeping those three in sets makes each check O(1).
function solveNQueens(n) { const queens = []; // queens[r] = the column of the queen in row r const result = []; const safe = (r, c) => queens.every((qc, qr) => qc !== c && Math.abs(qc - c) !== r - qr); const place = (r) => { if (r === n) { result.push(queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1))); return; } for (let c = 0; c < n; c++) { if (!safe(r, c)) continue; // same column or diagonal as an earlier queen queens.push(c); place(r + 1); queens.pop(); } }; place(0); return result;}Time O(n! · n): at most n choices in row 0, n − 1 in row 1, …, each checked in O(n). Space O(n).
A queen goes in each row where its column and both diagonals are free; when a row has no safe square, the last queen moves.
function solveNQueens(n) { const cols = new Set(), diag = new Set(), anti = new Set(); // attacked columns and diagonals const queens = []; const result = []; const place = (r) => { if (r === n) { // a queen in every row result.push(queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1))); return; } for (let c = 0; c < n; c++) { if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue; // attacked: prune cols.add(c); diag.add(r - c); anti.add(r + c); // place the queen queens.push(c); place(r + 1); queens.pop(); // remove it again cols.delete(c); diag.delete(r - c); anti.delete(r + c); } }; place(0); return result;}Time O(n!), with O(1) checks, and in practice far less: for n = 8 the search visits about 2,000 positions to find all 92 solutions, out of 16 million ways to put one queen in each row. Space O(n). The diagonal index r − c can be negative; arrays shift it by n.
[].