Skip to main content

25. N-Queens

hardAsked at Autodesk

Place n queens on an n x n board so that no two attack each other; return every distinct configuration.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

The n-queens puzzle asks for the placement of n queens on an n x n chessboard such that no two queens attack each other (no shared row, column, or diagonal). Return all distinct solutions; each solution is a board layout using 'Q' and '.'.

Constraints

  • 1 <= n <= 9

Examples

Example 1

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

Example 2

Input
n=1
Output
[["Q"]]

Approaches

1. Try every permutation

Generate all n! permutations of column positions and filter those with no diagonal conflict.

Time
O(n! * n)
Space
O(n)
for each permutation perm of [0..n-1]: if no diagonal conflict, push board.

Tradeoff:

2. Backtracking with diagonal sets

Place a queen row-by-row, tracking used columns and two diagonal sets (row+col and row-col). Backtrack on conflict.

Time
O(n!)
Space
O(n)
function solveNQueens(n) {
  const res = [];
  const cols = new Set(), d1 = new Set(), d2 = new Set();
  const placement = new Array(n).fill(-1);
  function backtrack(r) {
    if (r === n) {
      res.push(placement.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); placement[r] = c;
      backtrack(r + 1);
      cols.delete(c); d1.delete(r + c); d2.delete(r - c);
    }
  }
  backtrack(0);
  return res;
}

Tradeoff:

Autodesk-specific tips

Constraint-propagation backtracking parallels Autodesk's parametric constraint solvers in Inventor and Fusion 360 sketch modes.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill N-Queens and other Autodesk interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →