回溯法

八皇后问题

现在有一个 n x n 的跳棋棋盘，有n个棋子被放置在棋盘上，使得每行，每列，每条对角线（包括两条主对角线的所有对角线）上都至多有一个棋子。

javascript

class QueenPosition {
  constructor(rowIndex, columnIndex) {
    this.rowIndex = rowIndex
    this.columnIndex = columnIndex
  }
  get leftDiagonal () {
    return this.rowIndex - this.columnIndex
  }
  get rightDiagonal () {
    return this.rowIndex + this.columnIndex
  }
  get description () {
    return `${this.rowIndex},${this.columnIndex}`
  }
}

const isSafe = (queensPositions, currentPosition) => {
  // 遍历已有的queue
  for (let queenIndex = 0; queenIndex < queensPositions.length; queenIndex++) {
    const prevPosition = queensPositions[queenIndex]
    // 是否是横列/纵列/斜列
    if (prevPosition && (prevPosition.rowIndex === currentPosition.rowIndex 
      || prevPosition.columnIndex  === currentPosition.columnIndex 
      || prevPosition.leftDiagonal === currentPosition.leftDiagonal 
      || prevPosition.rightDiagonal === currentPosition.rightDiagonal)) {
      // console.log(prevPosition, currentPosition);
      return false
    }
  }
  return true
}

const nQueensRecursive = (solutions, previousQueensPositions, queensCount, rowIndex) => {
  // clone position 数组，否则存在引用关系
  const queensPositions = [...previousQueensPositions].map((queenPosition) => {
    return !queenPosition ? queenPosition : new QueenPosition(
      queenPosition.rowIndex,
      queenPosition.columnIndex,
    );

  });

  // 判断position是否已经满足题意要求
  if (rowIndex === queensCount) {
    // 说明 queensPositions 已经有了 queensCount 个，符合要求
    solutions.push(queensPositions)
    return 
  }
  
  // 遍历每一列
  for (let columnIndex = 0; columnIndex < queensCount; columnIndex++) {
    const currentPosition = new QueenPosition(rowIndex, columnIndex)
    // 判断当前点是否符合要求
    if (isSafe(queensPositions, currentPosition)) {
      // 加入到行中
      queensPositions[rowIndex] = currentPosition
      // 遍历下一列
      nQueensRecursive(solutions, queensPositions, queensCount, rowIndex + 1)
      // 遍历完后将这个数据移除，回到本行下一条数据
      queensPositions[rowIndex] = null
    }
  }
}

const nQueens = (queensCount) => {
  const queensPositions = Array(queensCount).fill(null)
  const solutions = []
  // 从第 0 行开始
  nQueensRecursive(solutions, queensPositions, queensCount, 0)
  return solutions
}

javascript

const solutions = nQueens(4)
solutions.forEach((queuePositions, index) => {
  console.log(`==== result ${index} ====`)
  queuePositions.forEach(position => {
    console.log(position.description)
  })
})

// ==== result 0 ====
// 0,1
// 1,3
// 2,0
// 3,2
// ==== result 1 ====
// 0,2
// 1,0
// 2,3
// 3,1

回溯法 ​

回溯法