52.N皇后II

链接：52.N皇后II
难度：Hard
标签：回溯
简介：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

题解 1 - javascript

• 编辑时间：2020-04-27
• 执行用时：64ms
• 内存消耗：34.1MB
• 编程语言：javascript
• 解法介绍：回溯算法，遍历后剪枝。

/**
 * @param {number} n
 * @return {string[][]}
 */
var totalNQueens = function (n) {
  const cols = new Array(n);
  let res = 0;
  queues(0);
  function queues(row) {
    if (row === n) {
      res++;
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        cols[row] = col;
        queues(row + 1);
      }
    }
  }
  function isValid(row, col) {
    for (let i = 0; i < row; i++) {
      if (cols[i] === col) return false;
      if (row - i === Math.abs(cols[i] - col)) return false;
    }
    return true;
  }
  return res;
};

题解 2 - typescript

• 编辑时间：2020-10-17
• 执行用时：96ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：回溯。

function totalNQueens(n: number): number {
  const cols = new Array(n);
  let ans = 0;
  find(0);
  return ans;
  function find(row: number) {
    if (row === n) {
      ans++;
      return;
    }
    for (let i = 0; i < n; i++) {
      if (check(row, i)) {
        cols[row] = i;
        find(row + 1);
      }
    }
  }
  function check(row: number, col: number): boolean {
    for (let i = 0; i < row; i++) {
      if (cols[i] === col) return false;
      if (row - i === Math.abs(cols[i] - col)) return false;
    }
    return true;
  }
}