vv13
博客订阅

八皇后问题

八皇后是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

解析

安全位置检测

大多数人可能跟我一样不会下国际象棋,为了得到符合要求的棋子,我们先根据规则写一个判断函数,用于判断两枚棋子是否属于安全位置:

function checkIfConflict(currentX, currentY, nextX, nextY) {
    // 是否处于同一纵行、行、左上到右下斜线、左下到右上斜线检测
    return (
      currentX === nextX ||
      currentY === nextY ||
      (nextX - currentX) === (nextY - currentY) ||
      (nextX + nextY) === (currentX + currentY))
}

数据结构

最能代表棋盘的应该属于二维数组了,那就先来写一个简单的二维数组初始化函数,其中可以用0代表空行,1代表棋子:

function initGrid(n) {
  const grid = [];
  for (let i = 0; i < n; i++) {
      grid[i] = []
      for (let j = 0; j < n; j++) {
          grid[i][j] = 0
      }
  }
  return grid
}

虽然二维数组可以代表棋盘结构,由题目可知,在每一行仅有一个棋子存在,因此我们可以用一维数组来表示符合要求的结果集,其中数组中的索引代表每一行,索引的值代表每一列,如[1, 3]代表第1行2列有棋子,第2行4列有棋子(索引从0开始)。

算法

每一行有8个棋子,一共有8行,,那么一共有多少种排列方式呢?答案在:Math.pow(8, 8)里。

现在我们来写一个函数将所有排列结果求出来:

{
  const results = []
  function qiongju(results, n, current) {
    if (current.length >= n) {
      results.push(current)
    } else {
      for (let i = 0; i < 8; i++) {
        qiongju(results, n, current + i)
      }
    }
  }
  qiongju(results, 8, '')
  console.log(results.length)
}

发现打印的结果与预先求出的条数一样,算法基本正确,如果用穷举法的话,现在我们需要做的就是在if (current.length) >= n里进行判断结果,将符合要求的结果进行过滤即可,这样做的效率会很低下,我们也会自然而然的想很多方法对结果集进行过滤,但在这种情况下,应该按照回溯法的思想去解决当前问题。

先整理一下当前的线索与思路:

  1. 判断是否在安全位置,可用checkIfConflict函数。
  2. 使用一维数组来表示符合要求的结果集,其中数组中的索引代表每一行,索引的值代表每一列。
  3. 通过递归,使用回溯法来进行

我们可通过以下步骤进行使用回溯法:

  1. 初始状态:结果集为空数组
  2. 路径:采用深度优先遍历,从第1行到最后行,再从最后行的第1列到最后列进行生成最终结果
  3. 条件:每生成n + 1行,需要判断与1 ~ n行的所有棋子相比是否都处于安全位置,若不安全,返回步骤2,若安全,进入步骤4
  4. 判断生成节点数与所要求的是否一致,若一致则将其添加到结果集,若不一致则返回步骤2

由以上表述,最终程序可写为:

function main(n) {
    const results = []
    eightQueen(results, n, [])
}

function checkIfConflict(currentX, currentY, nextX, nextY) {
    // 是否处于同一纵行、行、左上到右下斜线、左下到右上斜线检测
    return (
      currentX === nextX ||
      currentY === nextY ||
      (nextX - currentX) === (nextY - currentY) ||
      (nextX + nextY) === (currentX + currentY)
    )
}

function eightQueen(results, n, result) {
    if (result.length >= n) {
        results.push(result)
        return
    } else if (!result.length) {
      for (let i = 0; i < n; i++) {
        eightQueen(results, n, [i])
      }
    } else {
      const toX = result.length
      for (let toY = 0; toY < n; toY++) {
          let conflict = false
          for (let fromX = 0; fromX < toX; fromX++) {
              const fromY = result[fromX]
              if (checkIfConflict(fromX, fromY, toX, toY)) {
                  conflict = true
                  break
              }
          }
          if (!conflict) {
              eightQueen(results, n, result.concat([toY]))
          }
      }   
    }
}

main(8)

可视化

在此就不过于展开啦,为了结果直观,我们初始化一个二位数组,再将结果填进去,最终打印出来:

function consoleChess(n, arr) {
  const grid = [];
  for(let i = 0; i < n; i++) {
      grid[i] = []
      for (let j = 0; j < n; j++) {
          grid[i][j] = arr[i] === j ? 1 : 0
      }
      grid[i].join('')
  }
  console.log(grid.join('\n'))
}

// ...

function main(n) {
    const results = []
    eightQueen(results, n, [])
    results.slice(0, 2).forEach(data => consoleChess(data))
}

// Result
1,0,0,0,0,0,0,0
0,0,0,0,1,0,0,0
0,0,0,0,0,0,0,1
0,0,0,0,0,1,0,0
0,0,1,0,0,0,0,0
0,0,0,0,0,0,1,0
0,1,0,0,0,0,0,0
0,0,0,1,0,0,0,0

1,0,0,0,0,0,0,0
0,0,0,0,0,1,0,0
0,0,0,0,0,0,0,1
0,0,1,0,0,0,0,0
0,0,0,0,0,0,1,0
0,0,0,1,0,0,0,0
0,1,0,0,0,0,0,0
0,0,0,0,1,0,0,0