「LeetCode51」N皇后｜刷题打卡

这是力扣第 51 题：

所谓皇后彼此不能相互攻击的意思是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。例如下面的排列：

之前有讲过如何应用回溯思路来解决全排列问题的，本题其实就是二维空间的全排列问题。解题框架是固定的：

• 定义结果集 result 和路径集 routes
• 遍历节点，把不在路径内的新节点放入路径集
• 递归遍历
• 删除递归前放入的新节点

按照这个思路，我们先要定义路径，此题的路径是 n*n 的二维矩阵，皇后可以放在矩阵的任意一格，但是多个皇后之间不能冲突，我们先写判断冲突的逻辑，即当前的皇后能不能放在矩阵的第 row 行第 col 列：

function isValid(matrix, row, col) {
  const n = matrix.length
  // 行是否存在皇后
  for (let i = 0; i < n; i++) {
    if (matrix[row][i] === 'Q' && col !== i) return false
  }
  // 列是否存在皇后
  for (let i = 0; i < n; i++) {
    if (matrix[i][col] === 'Q' && row !== i) return false
  }
  // 左上右下是否存在皇后
  for (let i = 1; i < n; i++) {
    if (matrix[row - i] && matrix[row - i][col - i] === 'Q') return false
    if (matrix[row + i] && matrix[row + i][col + i] === 'Q') return false
  }
  // 右上左下是否存在皇后
  for (let i = 0; i < n; i++) {
    if (matrix[row - i] && matrix[row - i][col + i] === 'Q') return false
    if (matrix[row + i] && matrix[row + i][col - i] === 'Q') return false
  }
  return true
}

虽然代码行数比较多，但是整体逻辑还是比较清晰的，就是行、列、左上右下、右上左下四个方位的判断。然后就是回溯遍历的问题了：

function nQueue(n) {
  const result = []
  const matrix = []
  for (let i = 0; i < n; i++) matrix[i] = new Array(n).fill('')
  traverse(0, n)
  return result
  function traverse(row, n) {
    if (row === n) return result.push(matrix.map(it => it.join('.')))
    for (let col = 0; col < n; col++) {
      if (!isValid(matrix, row, col)) continue
      matrix[row][col] = 'Q'
      traverse(row + 1, n)
      matrix[row][col] = ''
    }
  }
}

可以看到，依然是套模板，二维的遍历无非是从第 0 行开始，遍历列，如果当前行和列所在的位置能放，就设置为 Q，然后遍历下一行，遍历之后再把该位置置空。例如 nQueue(4) 的结果是：

[
  [
    [ '', 'Q', '', '' ],
    [ '', '', '', 'Q' ],
    [ 'Q', '', '', '' ],
    [ '', '', 'Q', '' ]
  ],
  [
    [ '', '', 'Q', '' ],
    [ 'Q', '', '', '' ],
    [ '', '', '', 'Q' ],
    [ '', 'Q', '', '' ]
  ]
]

本文正在参与「掘金 3 月闯关活动」，点击查看活动详情。