n 皇后

先来看问题，其实问题不难理解：

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

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：

输入: 4

输出: 

[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解释: 4 皇后问题存在两个不同的解法。

提示：

皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。

当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自百度百科 - 皇后）

伪代码

定义一个函数，参数名为 n，类型为 number，代表一个 n×n 的棋盘。

函数内部：

定义一个变量 res，类型为 Array<string>，作为最终的结果返回值。

定义一个变量 columns，表示列数组，类型为 Array<boolean>，如果某一位元素为 true，说明该列存在皇后。每个元素索引分别对应不同的列。

定义一个变量 dia1，表示正对角线（从右上到左下方向）数组，类型为 Array<boolean>，如果某一位元素为 true，说明该条正对角线存在皇后。每个元素索引分别对应第几条正对角线。

定义一个变量 dia2，表示反对角线（从左上到右下方向）数组，类型为 Array<boolean>，如果某一位元素为 true，说明该条反对角线存在皇后。每个元素索引分别对应第几条反对角线。

定义一个函数 searchFor，意为寻找以自身为中心点在列、正对角线、反对角线上存在皇后的情况。 searchFor 函数接受第参数 rowIndex、preRes，类型分别为 number、Array<number>，含义分别是第几行、当前行积累的可行摆法数组。

searchFor 中，如果 rowIndex === n，说明当前遍历行索引等于行数，也就是说实际遍历的行数超过了行数。也说明达到了题目的每行皇后该如何摆放的条件，然后还会先根据 preRes 计算出符合格式的数组，再然后才将符合格式的数组推入到会作为最终返回结果的变量 res 中。然后下一行，return。

否则，从 0 到 n 挨个遍历每一列。在每一轮循环中，可以拿到当前位置的行索引，列索引。

正对角线索引通过 rowIndex + columnIndex 计算得出（y + x，0 - 2n）。

反对角线索引通过 rowIndex - columnIndex 计算得出（y - x，-n - n）。

然后用索引去取数组中的值，有值就说明该条线上有皇后。如果三条线上都没有皇后，那么就可以把皇后安放在当前位置。

然后调用 flagExist 函数，标记当前位置已存在皇后。

然后递归调用 searchFor，传入 rowIndex + 1，preRes.concat(columnIndex)，继续往下一行走。

然后调用 flagExist 函数，把当前存在皇后的标记清除掉。

最后，这是一个深度优先递归遍历。在第一行时，第一个位置肯定可以，然后就又递归调用 searchFor，然后发现第一、二个都不行，第三个可以，然后又递归调用 searchFor ...

代码

function solveNQueens (n: number) {
  const res = [] as Array<Array<string>>
  const columns = [] as Array<boolean>
  const dia1 = [] as Array<boolean>
  const dia2 = [] as Array<boolean>

  function searchFor (rowIndex: number, preRes: number[]) {
    if(rowIndex === n) {
      res.push(format(preRes))
      return
    }

    for(let columnIndex = 0; columnIndex < n; columnIndex ++) {
      const isColumnExist = columns[columnIndex]
      const isDia1Exist = dia1[rowIndex + columnIndex]
      const isDia2Exist = dia2[rowIndex - columnIndex]
      if(!isColumnExist && !isDia1Exist && !isDia2Exist) {
        flagExist(columnIndex, rowIndex + columnIndex, rowIndex - columnIndex, true)
        searchFor(rowIndex + 1, preRes.concat(columnIndex))
        flagExist(columnIndex, rowIndex + columnIndex, rowIndex - columnIndex, false)
      }
    }
  }

  searchFor(0, [])

  function flagExist (columnIndex: number, dia1Index: number, dia2Index: number, flag: boolean) {
    columns[columnIndex] = flag
    dia1[dia1Index] = flag
    dia2[dia2Index] = flag
  }

  function format (arr: number[]) {
    const res = [] as Array<string>
    for(let rowIndex = 0; rowIndex < arr.length; rowIndex ++) {
      let str = ''
      for(let columnIndex = 0; columnIndex < arr.length; columnIndex ++) {
        if(columnIndex === arr[rowIndex]) {
          str += 'Q'
        } else {
          str += '.'
        }
      }
      res.push(str)
    }
    return res
  }
  return res
}

// in-source test suites
if (import.meta.vitest) {
  const { it, expect } = import.meta.vitest
  
  it('test', () => {
    const res = [
      ['.Q..',  // 解法 1
        '...Q',
        'Q...',
        '..Q.'],
      ['..Q.',  // 解法 2
        'Q...',
        '...Q',
        '.Q..']
    ]
    expect(solveNQueens(4)).toEqual(res)
  })
}

其它题解

https://juejin.cn/post/6844903824235167751

LeetCode 链接

https://leetcode.cn/problems/n-queens/

n 皇后 ​

伪代码 ​

代码 ​

其它题解 ​

LeetCode 链接 ​

n 皇后

伪代码

代码

其它题解

LeetCode 链接