N-Queens (backtracking)

Hard TimeO(n!) worst case SpaceO(n) board + stack

A queen attacks along its row, its column and both diagonals. Place n of them on an n × n board so that no two share a row, a column or a diagonal, and return one entry per solution giving the column chosen for each row. Exactly n queens are placed, one per row, and every solution is wanted rather than just the first.

Examples

Example 1

Input
n = 4
Output
[[1,3,0,2],[2,0,3,1]]
Two solutions on a 4 × 4 board, each the mirror image of the other.

Example 2

Input
n = 3
Output
[]
Three queens cannot be placed on a 3 × 3 board at all, so there is no solution to return.

The Code

function isSafe(cols, row, col) {
  for (let r = 0; r < row; r++) {
    if (cols[r] === col || Math.abs(cols[r] - col) === row - r) return false;
  }
  return true;
}
function place(cols, row, n, solutions) {
  if (row === n) {
    solutions.push(cols.slice());
    return;
  }
  for (let col = 0; col < n; col++) {
    if (isSafe(cols, row, col)) {
      cols.push(col);
      place(cols, row + 1, n, solutions);
      cols.pop();
    }
  }
}
function solveNQueens(n) {
  const solutions = [];
  place([], 0, n, solutions);
  return solutions;
}
solveNQueens(4);
Done

The first 42 calls, of 293. This one does not fit on a page.

Step through solveNQueens(4) call by call

More like this

All backtracking examples (10) →