Given a chessboard of size n×n, determine how many ways n queens can be placed on the board, such that no two queens attack each other.

1-n-queens.js

// to check diagonals,
// row - col for neg diag,
// row + col for pos diag,
// those values will remain constant along the whole diagonal
function canPlace(row, col, result) {
  for (let boardRow = 0; boardRow < row; ++boardRow) {
    const boardCol = result[boardRow];
    if (col === boardCol) {
      // col is taken
      return false;
    }
    const posDiag = row + col;
    const negDiag = row - col;
    if (posDiag === boardRow + boardCol || negDiag === boardRow - boardCol) {
      // diagonal is taken
      return false;
    }
  }
  return true;
}

export function solveNQueens(n) {
  return solve(n);
}

function solve(n) {
  const results = [];
  // kickstart our search by trying every position for the first queen in the first row
  // since our board is NxN, and we have N queens, we must have one queen at each row
  for (let col = 0; col < n; ++col) {
    solveRec(results, [col], n);
  }
  return results.length;
}

// result is an array whose indexes denote rows, and values denote columns
// so an array of [2,0,1] means an array of queen positions, 0,2 1,0 2,1
function solveRec(results, result, n) {
  if (result.length === n) {
    // our result contains n values, meaning n queens have been placed
    // this can only happen if all placements are valid
    // so add this result to the results array
    results.push(result);
    return;
  }
  // the next row to consider (since indexes in result are rows)
  const row = result.length;
  for (let col = 0; col < n; ++col) {
    if (canPlace(row, col, result)) {
      result.push(col);
      // place the queen and proceed further
      solveRec(results, result, n);
      // backtrack
      result.pop();
    }
    // if we cannot place the queen anywhere in this row,
    // we don't proceed further, eliminating the whole subset of invalid solutions
  }
}

// canPlace is O(n)
// canPlace is called in a loop, so it's O(n^2)
// height of the recursion tree is n
// so in total we have O(n!)

2-README.md