介绍

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n 皇后摆放问题：这时棋盘的大小变为 n×n，而皇后个数也变成 n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

八个皇后在 8x8 棋盘上共有 4,426,165,368（64C8）种摆放方法，但只有 92 个可行（皇后間互不攻擊）的解。如果将旋转和对称的解归为一种的话，则一共有 12 个独立解。

实现

JavaScript

class NQueens {
  constructor (size) {
     if (size < 0) {
      throw RangeError('Invalid board size')
    }
    this.board = new Array(size).fill('.').map(() => new Array(size).fill('.'))
    this.size = size
    this.solutionCount = 0
  }

  isValid ([row, col]) {
    // function to check if the placement of the queen in the given location is valid

    // checking the left of the current row
    for (let i = 0; i < col; i++) {
      if (this.board[row][i] === 'Q') return false
    }

    // checking the upper left diagonal
    for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
      if (this.board[i][j] === 'Q') return false
    }

    // checking the lower left diagonal
    for (let i = row, j = col; j >= 0 && i < this.size; i++, j--) {
      if (this.board[i][j] === 'Q') return false
    }

    return true
  }

  placeQueen (row, col) {
    this.board[row][col] = 'Q'
  }

  removeQueen (row, col) {
    this.board[row][col] = '.'
  }

  solve (col = 0) {
    if (col >= this.size) {
      this.solutionCount++
      return true
    }

    for (let i = 0; i < this.size; i++) {
      if (this.isValid([i, col])) {
        this.placeQueen(i, col)
        this.solve(col + 1)
        this.removeQueen(i, col)
      }
    }

    return false
  }

  printBoard (output = value => console.log(value)) {
    if (!output._isMockFunction) {
      output('\n')
    }
    for (const row of this.board) {
      output(row)
    }
  }
}

• 注意，无论 resolve 成功还是失败，都需要回溯，继续回溯是为了找出下一个正确的解。
• isValid 只需要在左侧检查横向、斜向即可，因为右侧和竖向还没有放皇后不需要检测。

参考

• 八皇后问题 - Wikiwand (opens new window)