JavaScript实现N皇后问题算法谜题解答

谜题

N皇后问题。将N个皇后放置在NxN的国际象棋棋盘上,其中没有任何两个皇后处于同一行、同一列或同一对角线上,以使得它们不能互相攻击。

策略

回溯法。

JavaScript解

以8皇后问题为例:

代码如下:

/**
 * Created by cshao on 12/28/14.
 */

function getNQueens(order) {
  if (order < 4) {
    console.log('N Queens problem apply for order bigger than 3');
    return;
  }

var nQueens = [];
  var backTracking = false;
  rowLoop:
  for (var row=0; row<order; row++) {
    if (nQueens[row] === undefined) {
      nQueens[row] = [];
    }

for (var col=0; col<order; col++) {
      if (nQueens[row][col] === 0) {
        continue;
      } else if (backTracking && nQueens[row][col] == 1) {
        if (col === order-1) {
          resetRow(nQueens, order, row);
          row = row - 2;
          continue rowLoop;
        }
        nQueens[row][col] = 0;
        backTracking = false;
        continue;
      }
     
      nQueens[row][col] = 1;
      if (isQueenValid(nQueens, row, col)) {
        continue rowLoop;
      } else if (col == order-1) {
        backTracking = true;
        resetRow(nQueens, order, row);
        row = row - 2;
        continue rowLoop;
      } else {
        nQueens[row][col] = 0;
        continue;
      };
    }
  }

return nQueens;
}

function resetRow(nQueens, order, row) {
  for (var col=0; col<order; col++) {
    nQueens[row][col] = undefined;
  }
}

function isQueenValid(nQueens, row, col) {
  for (var i=0; i<col; i++) {
    if (nQueens[row][i] == 1) {
      return false;
    }
  }
  for (var j=1; j<row+1; j++) {
    if (nQueens[row-j][col]==1 || (nQueens[row-j][col-j]!=undefined && nQueens[row-j][col-j]==1) || (nQueens[row-j][col+j]!=undefined && nQueens[row-j][col+j]==1)) {
      return false;
    }
  }
  return true;
}

function printQueens(queens) {
  for (var row=0; row<queens.length; row++) {
    var rowText = '';
    for (var col=0; col<queens.length; col++) {
      if (queens[row][col]===undefined) {
        queens[row][col] = 0;
      }
      rowText = rowText + queens[row][col] + '  ';
    }
    console.log(rowText);
  }
}

var queens = getNQueens(8);
printQueens(queens);

结果

代码如下:

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

(0)

相关推荐

  • JavaScript解八皇后问题的方法总结

    关于八皇后问题的 JavaScript 解法,总觉得是需要学习一下算法的,哪天要用到的时候发现真不会就尴尬了 背景 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上 八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为 n×n ,而皇后个数也变成n .当且仅当n = 1或n ≥ 4时问题有解 盲目的枚举算法 通过N重循环,枚举满足约束条件的解(

  • javascript递归回溯法解八皇后问题

    下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了. function NQueens(order) { if (order < 4) { console.log('N Queens problem apply for order bigger than 3 ! '); return; } var nQueens = []; var backTracking = false; rowLoop: for (var row=0; row<order; row++) { //若出现ro

  • JavaScript实现N皇后问题算法谜题解答

    谜题 N皇后问题.将N个皇后放置在NxN的国际象棋棋盘上,其中没有任何两个皇后处于同一行.同一列或同一对角线上,以使得它们不能互相攻击. 策略 回溯法. JavaScript解 以8皇后问题为例: 复制代码 代码如下: /**  * Created by cshao on 12/28/14.  */ function getNQueens(order) {   if (order < 4) {     console.log('N Queens problem apply for order b

  • JavaScript实现穷举排列(permutation)算法谜题解答

    谜题 穷举一个数组中各个元素的排列 策略 减而治之.递归 JavaScript解 复制代码 代码如下: /**  * Created by cshao on 12/23/14.  */ function getPermutation(arr) {   if (arr.length == 1) {     return [arr];   } var permutation = [];   for (var i=0; i<arr.length; i++) {     var firstEle = a

  • JavaScript实现三阶幻方算法谜题解答

    谜题 三阶幻方.试将1~9这9个不同整数填入一个3×3的表格,使得每行.每列以及每条对角线上的数字之和相同. 策略 穷举搜索.列出所有的整数填充方案,然后进行过滤. JavaScript解 复制代码 代码如下: /**  * Created by cshao on 12/28/14.  */ function getPermutation(arr) {   if (arr.length == 1) {     return [arr];   } var permutation = [];   f

  • JavaScript实现树的遍历算法示例【广度优先与深度优先】

    本文实例讲述了JavaScript实现树的遍历算法.分享给大家供大家参考,具体如下: <script type="text/javascript"> var t = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]; //下面这段深度优先搜索方法出自Aimingoo的[JavaScript语言精髓与编程实践] var deepView = function(aTree,iNode) { (iNode in aTree)

  • Javascript中的常见排序算法

    具体代码及比较如下所示: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">

  • 基于JavaScript实现的折半查找算法示例

    本文实例讲述了基于JavaScript实现的折半查找算法.分享给大家供大家参考,具体如下: 折半查找也叫做二分查找,是针对有序表的一种查找方式,其思想如下: 将数组的第一个位置设为下边界: 将数组的最后一个位置设为上边界: 如果下边界等于或小于上边界,则做如下操作: 将中点设置为上边界加下边界之和除以二:    如果中点的元素小于查询的值,则将下边界设置为中点元素所在下标加1:    如果中点的元素大于查询的值,则将上边界设置为中点元素所在下标减1:    否则中点元素即为要查找的元素,可以进行

  • 基于JavaScript实现的顺序查找算法示例

    本文实例讲述了基于JavaScript实现的顺序查找算法.分享给大家供大家参考,具体如下: 对于查找数据来说,最简单的方法就是从列表的第一个元素开始对列表元素逐个进行判断,直到找到了想要的结果.这个方法叫做顺序查找,有时候也被叫做线性查找.它属于暴力查找技巧的一种. 顺序查找实现起来非常简单,代码如下: function generalSearch(arr,data){//普通的顺序查找,就是遍历一遍看是否找到 for(var i=0;i<arr.length;i++){ if(arr[i]==

  • JavaScript实现的选择排序算法实例分析

    本文实例讲述了JavaScript实现的选择排序算法.分享给大家供大家参考,具体如下: 简单选择排序是人们最熟悉的比较方式,其算法思想为:从数组的开头开始,将第一个元素和其他元素进行比较.检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续.这个过程会一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序. 代码如下: <!DOCTYPE html> <html> <head> <meta charset="utf-

  • javascript中数组的常用算法深入分析

    前言 Array是Javascript构成的一个重要的部分,它可以用来存储字符串.对象.函数.Number,它是非常强大的.因此深入了解Array是前端必修的功课.本文将给大家详细介绍了javascript中数组的常用算法,下面话不多说了,来一起看看详细的介绍吧 一.不改变原数组,返回新数组(字符串) 1.concat()   连接两个或者多个数组,两边的原始数组都不会变化,返回的是被连接数组的一个副本. 2.join()  把数组中所有的元素放入到一个字符串中,返回字符串 var a = [1

  • JavaScript笛卡尔积超简单实现算法示例

    本文实例讲述了JavaScript笛卡尔积超简单实现算法.分享给大家供大家参考,具体如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> &

随机推荐