52. N-Queens II

Description

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

 

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 9

 

Solutions

Solution: Backtracking

• Time complexity: O(n²)
• Space complexity: O(2n)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const totalNQueens = function (n) {
  const cols = new Array(n).fill(false);
  const diagonals = Array.from({length: n * 2}).fill(false);
  const inverseDiagonals = Array.from({length: n * 2}).fill(false);
  const placementQueen = row => {
    if (row === n) return 1;
    let result = 0;

    for (let col = 0; col < n; col++) {
      const diag1 = col - row + n;
      const diag2 = col + row;

      if (cols[col] || diagonals[diag1] || inverseDiagonals[diag2]) continue;
      cols[col] = diagonals[diag1] = inverseDiagonals[diag2] = true;
      result += placementQueen(row + 1);
      cols[col] = diagonals[diag1] = inverseDiagonals[diag2] = false;
    }
    return result;
  };

  return placementQueen(0);
};