N皇后问题（附带JavaScript源代码）

什么是N-皇后问题?

说到这个N-皇后问题，就不得不先提一下这个历史上著名的8皇后问题啦。

八皇后问题，是一个古老而著名的问题.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法?

那么，我们将8皇后问题推广一下，就可以得到我们的N皇后问题了。N皇后问题是一个经典的问题，在一个NxN的棋盘上放置N个皇后，使其不能互相攻击 (同一行、同一列、同一斜线上的皇后都会自动攻击) 那么问，有多少种摆法？

源代码

// 存储最后的结果
let res = []
// 标识列
let col = []
// 标识主对角线
let dia1 = []
// 标识副对角线
let dia2 = []

// 根据结果生成棋盘
let generateBoard = (n, row) => {
  // 生成一个n*n的全部为.的数组
  let board = []
  for (let i = 0; i < n; i++) {
    board.push(Array(n).fill(' .'))
  }
  // 将对应位置放入皇后
  for (let i = 0; i < n; i++) {
    board[i][row[i]] = ' Q'
  }
  return board
}

// 尝试在一个n皇后问题中，摆放第index行皇后位置
let putQueen = (n, index, row) => {
  // 如果行数为n说明得到了n皇后的一个解，将解放入结果数组中
  if (index == n) {
    res.push(generateBoard(n, row))
  }
  // 遍历列
  for (let i = 0; i < n; i++) {
    // 尝试在第index行的皇后摆放在第i列
    // 主对角线用index + i作为下标
    // 副对角线使用index - i + n - 1作为下标
    if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
      // 将当前位置放置皇后
      row.push(i)
      col[i] = true
      dia1[index + i] = true
      dia2[index - i + n - 1] = true
      // 解决更小规模问题
      putQueen(n, index + 1, row)
      // 进行回滚
      col[i] = false
      dia1[index + i] = false
      dia2[index - i + n - 1] = false
      row.pop(i)
    }
  }
}

// 解决n皇后
let solveNQueens = n => {
  // 初始化
  res = []
  // n个列
  col = Array(n).fill(false)
  // 2 * n - 1个主对角线与副对角线
  dia1 = Array(2 * n - 1).fill(false)
  dia2 = Array(2 * n - 1).fill(false)
  
  let row = []
  putQueen(n, 0, row)
}

测试

// 定义规模
const n = 4

// 执行n皇后
solveNQueens(n)

// 打印结果
res.forEach(item => {
  item.forEach(row => {
    let cols = ''
    row.forEach(col => {
      cols += col
    })
    // 打印一行
    console.log(cols)
  })

  // 换行
  console.log()
})

测试结果

 . Q . .
 . . . Q
 Q . . .
 . . Q .

 . . Q .
 Q . . .
 . . . Q
 . Q . .