美文网首页
回溯算法之八皇后问题

回溯算法之八皇后问题

作者: 韩无仙 | 来源:发表于2021-06-07 16:44 被阅读0次

问题描述

设计一种算法,打印 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, "八皇后");
};

相关文章

  • 回溯算法之八皇后问题

    问题描述 设计一种算法,打印 N 皇后在 N × N 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线...

  • 回溯算法 八皇后问题

    参考小白带你学--回溯算法[https://zhuanlan.zhihu.com/p/54275352]LeetC...

  • 回溯算法--八皇后问题

    8x8 的棋盘,8 个棋子(皇后),每个棋子所在的行、列、对角线都不能有另一个棋子

  • 回溯算法:八皇后问题

    调用执行:

  • JS回溯算法--八皇后问题

    八皇后问题 在 8×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一...

  • 算法--策略-回溯八皇后问题

    回溯可以理解为, 通过选择不同的岔路口来通往目的地, 每一步都选择一条路出发, 能进则进, 不能则退回上一步, 换...

  • 八皇后问题,C#语言的实现

    八皇后问题问题描述:八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔...

  • 重写算法:八皇后问题

    八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。 问题的内容是在国际象棋棋盘上(8*8),放置八个皇后并...

  • 算法:八皇后问题

    八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。 问题的内容是在国际象棋棋盘上(8*8),放置八个皇后并...

  • 八皇后问题回溯法和迭代法

    数据结构系列文章: 常用的排序 二叉树的4种遍历 八皇后问题 八皇后问题,是一个古老而著名的问题,是回溯算法的典型...

网友评论

      本文标题:回溯算法之八皇后问题

      本文链接:https://www.haomeiwen.com/subject/emyleltx.html