N-Queens Hard 0 attempts
LeetCode ↗

N-Queens

Hard BacktrackingRecursion LeetCode

Arrange n queens on an n x n chessboard so that none of them attack one another — meaning no two queens may share a row, a column, or a diagonal. Return every distinct board arrangement that satisfies this.

Each returned solution is an array of strings, where 'Q' denotes a square holding a queen and '.' denotes an empty one.

Input Format
Implement solveNQueens(n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

Input
n = 4
Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Example 2

Input
n = 1
Output
[["Q"]]
Constraints
  • 1 <= n <= 9
Test Cases (2)
Case 1
Args: [4] Expected: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Case 2
Args: [1] Expected: [["Q"]]
Topics
BacktrackingRecursion

Place queens one row at a time using backtracking. Track which columns and diagonals are already attacked using sets. A queen at (row, col) occupies the row - col diagonal and the row + col anti-diagonal.

javascript
function solveNQueens(n) {
  const result = [];
  const cols = new Set();
  const diag = new Set();
  const antiDiag = new Set();
  const board = Array.from({ length: n }, () => '.'.repeat(n));

  function backtrack(row) {
    if (row === n) {
      result.push([...board]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag.has(row - col) || antiDiag.has(row + col)) continue;

      cols.add(col);
      diag.add(row - col);
      antiDiag.add(row + col);
      board[row] = board[row].substring(0, col) + 'Q' + board[row].substring(col + 1);

      backtrack(row + 1);

      cols.delete(col);
      diag.delete(row - col);
      antiDiag.delete(row + col);
      board[row] = '.'.repeat(n);
    }
  }

  backtrack(0);
  return result;
}

Time: O(n² × n!) as a loose upper bound including candidate checks and board-string construction. Space: O(n²) for the current board strings, plus O(n) for sets and recursion, excluding returned boards.

Saved in this browser only. Private to you.

JavaScript