javascript求解N皇后问题封装

作者: _shen | 来源:发表于2018-03-21 19:45 被阅读26次

通过求解N皇后问题,介绍一种的javascript库的封装方法。

/**
 * N:皇后数量
 */
var Queen = function (N) {

  if (N <= 0) {
    console.log('N is invalid');
    return null;
  }

  // 确保每一次调用Queen都会生成一个新的对象
  return new Queen.fn.init(N);
}


/**
 * 原型构造
 */
Queen.fn = Queen.prototype = {
  constructor: Queen,
  init: function (N){
    var c = [];

    this.N = N;
    this.res = [];

    // 递归求解
    this.traverse(c, 0);

    // 为了支持链式操作
    return this;
  }
};

// init的原型对象指向Queen的原型,这样就通过init构造的对象就可以使用挂在Queen原型上的方法
Queen.fn.init.prototype = Queen.fn;

/**
 * 递归求解
 * 
 * c:临时存储放置情况数组
 * row:层的序号
 */
Queen.fn.traverse =function (c, row) {
  if (row === this.N) {
    // 最后一层递归完毕,能够执行到此处说明求解成功,保存求解结果
    this.res.push(c.slice(0));
  } else {
    // 循环每一列,进行检测
    for (let col = 0; col < this.N; col++) {
      // 对列进行标记
      c[row] = col;
      // 检查是否符合规则
      if (this.check(c, row)) {
        // 符合规则,继续递归下一层
        this.traverse(c, row + 1);
      }
    }
  }
}

/**
 * 检查放置是否合规
 *
 * c:临时存储放置情况数组
 * row:层的序号
 * 说明:
 *      c[row] === c[i]:说明本层放置的位置与上一层放置的位置在同一列上
 *      row + c[row] === i + c[i]:说明本层放置的位置与上一层放置的位置在同一斜线上,斜线为反斜线
 *      row - c[row] === i - c[i]:说明本层放置的位置与上一层放置的位置在同一斜线上,
 */
Queen.fn.check = function (c, row) {
  for (let i = 0; i < row; i++) {
    if (c[row] === c[i] || row + c[row] === i + c[i] || row - c[row] === i - c[i]) {
      return false;
    }
  }
  return true;
}


/**
 * 图形化显示指定序号的结果
 * 
 * index:结果序号
 */
Queen.fn.printByIndex = function (index) {
  if (index < 1 || index > this.N) return;
  index--;

  let arr = [];

  for (let i = 0; i < this.N; i++) {
    for (let j = 0; j < this.N; j++) {
      arr[j] = (j === this.res[index][i]) ? '*': '-';
    }
    console.log(arr.join(' '));
  }
}

使用

let q = Queen(10);

// 打印第一个结果
q.printByIndex(1);

温馨提示:N的值最高在10左右,不然你试试,小心累坏你的机器哦_

相关文章

  • javascript求解N皇后问题封装

    通过求解N皇后问题,介绍一种的javascript库的封装方法。 使用 温馨提示:N的值最高在10左右,不然你试试...

  • LeetCode N皇后和数独的递归思路分析

    分析基于 LeetCode #51 N皇后 和 LeetCode #37 数独求解。 1. 寻找递归变量 N皇后问...

  • (26)Go递归求解n皇后问题

    继上一篇后续《(25)Go递归求解二维平面类问题1》https://www.jianshu.com/p/94f34...

  • [JavaScript刷LeetCode]-n皇后问题

    n皇后问题,js解法如下: js解LeetCode github地址: https://github.com/Li...

  • 回溯之N皇后

    N皇后问题:在 n x n 的棋盘上放置 N 个皇后,使其不能相互攻击。 1. 问题分析 皇后相互攻击是指:在皇后...

  • 风云的ARTS打卡(第四周)

    第4周 Algorithm: N皇后问题 n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上,并且使皇后彼此之间...

  • 使用回溯算法求解N皇后问题

    N皇后问题描述 在一个N * N的国际象棋棋盘上需要放置N个皇后,放置时要保证这些皇后不能攻击彼此,也就是要保证在...

  • lintcode-N皇后问题

    n皇后问题是将n个皇后放置在n*n的棋盘上,皇后彼此之间不能相互攻击。 给定一个整数n,返回所有不同的n皇后问题的...

  • lintcode N皇后问题

    n皇后问题是将n个皇后放置在n*n的棋盘上,皇后彼此之间不能相互攻击。给定一个整数n,返回所有不同的n皇后问题的解...

  • LeetCode 52. N皇后 II(N-Queens II)

    52. N皇后 II N皇后 IIn 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之...

网友评论

    本文标题:javascript求解N皇后问题封装

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