52. N皇后 II

原题链接：LeetCode 52. N皇后 II

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

**输入：**n = 4 **输出：**2 **解释：**如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

**输入：**n = 1 **输出：**1

提示：

- `1 <= n <= 9`

难度： Hard

题解代码

javascript

/**
 * @param {number} n
 * @return {number}
 */
let count = 0
var totalNQueens = function(n) {
  const init = Array(n).fill('.')
  const board = []   
  for (let i = 0; i < n; i++) {
      board.push([...init])
  }
  count = 0
  backTrack(board, 0)
  return count
};

function backTrack(board, row) {
  if (row === board.length) {
      return count++
  }
  const height = board[row].length
  for (let i = 0; i < height; i++) {
      if (!isValid(board, row, i)) continue
      board[row][i] = 'Q'
      backTrack(board, row + 1)
      board[row][i] = '.'
  }
}

function isValid(board, row, col) {
  const width = board[0].length
  const height = board.length
  // 当前列
  for (let i = 0; i < height; i++) {
      if (board[i][col] === 'Q') return false
  }
  // 右上
  for (let i = row - 1, j = col + 1; i >= 0 && j < width; i--, j++) {
      if (board[i][j] === 'Q') return false
  }
  // 左上
  for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false
  }
  return true
}

52. N皇后 II #

题目描述 #

题解代码 #

52. N皇后 II

题目描述

题解代码