Skip to content

Latest commit

 

History

History
161 lines (143 loc) · 5.17 KB

20180805_八皇后问题.md

File metadata and controls

161 lines (143 loc) · 5.17 KB
title date tags
八皇后问题
2018-08-05
Algorithm

八皇后是一个以国际象棋为背景的问题：如何能够在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