問題描述

設(shè)計(jì)一種算法川队，打印 N 皇后在 N × N 棋盤上的各種擺法漱挎，其中每個(gè)皇后都不同行系枪、不同列磕谅，也不在對角線上。這里的“對角線”指的是所有的對角線衬浑，不只是平分整個(gè)棋盤的那兩條對角線放刨。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/eight-queens-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)拓诸，非商業(yè)轉(zhuǎn)載請注明出處麻昼。

俺的解題思路

首先寫出判別條件。在x1=x2或y1=y2時(shí)同行同列倍谜，x1+y1 = x2 + y2時(shí)右45度同對角線，x1-y2 = x2-y2時(shí)左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;
  }

構(gòu)造棋子類季春，將這個(gè)判別方法作為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;
  }
}

接著就開始進(jìn)行第一次的放棋子。如果行指針超出限制宇攻，回溯到上一列記錄位置的下一個(gè)行位置，如果該位置行指針也超出限制逞刷，再做一次回溯夸浅。因?yàn)橛谢屎蠊粝拗疲@樣的回溯最多只會(huì)發(fā)生兩次词身。一次計(jì)算后會(huì)獲得n個(gè)限制下的一個(gè)解。

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;
}

進(jìn)行一個(gè)循環(huán)，改變起始行位置葫笼，得到的結(jié)果會(huì)存在重復(fù)拗馒，需要再進(jìn)行一個(gè)篩選。

var solveNQueens = function (n) {
  /* 構(gòu)建棋盤 */
  // 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, "八皇后");
};