问题描述

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/eight-queens-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

俺的解题思路

首先写出判别条件。在x1=x2或y1=y2时同行同列，x1+y1 = x2 + y2时右45度同对角线，x1-y2 = x2-y2时左45度同对角线。

setAble(QueenList) {
    for (let i = 0, l = QueenList.length; i < l; i++) {
      if (QueenList[i].x == this.x || QueenList[i].y == this.y) {
        return false;
      }
      if (
        QueenList[i].x + QueenList[i].y == this.x + this.y ||
        QueenList[i].x - QueenList[i].y == this.x - this.y
      ) {
        return false;
      }
    }
    return true;
  }

构造棋子类，将这个判别方法作为Queen的方法。

class Queen {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
  setAble(QueenList) {
    for (let i = 0, l = QueenList.length; i < l; i++) {
      if (QueenList[i].x == this.x || QueenList[i].y == this.y) {
        return false;
      }
      if (
        QueenList[i].x + QueenList[i].y == this.x + this.y ||
        QueenList[i].x - QueenList[i].y == this.x - this.y
      ) {
        return false;
      }
    }
    return true;
  }
  changeX(index) {
    this.x = index;
  }
  changeY(index) {
    this.y = index;
  }
}

接着就开始进行第一次的放棋子。如果行指针超出限制，回溯到上一列记录位置的下一个行位置，如果该位置行指针也超出限制，再做一次回溯。因为有皇后攻击限制，这样的回溯最多只会发生两次。一次计算后会获得n个限制下的一个解。

function solveOne(row, n) {
  let QueenList = [];
  let l = row;
  let i = 1;
  let temp;
  while (i <= n) {
    if (l > n) {
      temp = QueenList.pop();
      i--;
      l = temp.y + 1;
      if (l > n) {
        temp = QueenList.pop();
        i--;
        if (temp) {
          l = temp.y + 1;
        }else{
          return 0
        }
      }
    }
    let thisChess = new Queen(i, l);
    if (thisChess.setAble(QueenList)) {
      QueenList.push(thisChess);
      i++;
      l = 1;
      continue;
    }
    l++;
  }
  return QueenList;
}

进行一个循环，改变起始行位置，得到的结果会存在重复，需要再进行一个筛选。

var solveNQueens = function (n) {
  /* 构建棋盘 */
  // let table = new Array(n).fill(".");
  // for (let i = 0, l = table.length; i < l; i++) {
  //   table[i] = new Array(n).fill(".");
  // }
  let allSolves = [];
  for (let i = 0; i < n; i++) {
    allSolves.push(solveOne(i + 1, n));
  }
  console.log(allSolves, "八皇后");
};