js算法_八皇后问题的JavaScript解法

时间: 2018-12-29阅读: 1474标签: 算法

关于八皇后问题的 JavaScript 解法,总觉得是需要学习一下算法的,哪天要用到的时候发现真不会就尴尬了


背景

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上

八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为 n×n ,而皇后个数也变成n 。当且仅当n = 1或n ≥ 4时问题有解


盲目的枚举算法

通过N重循环,枚举满足约束条件的解(八重循环代码好多,这里进行四重循环),找到四个皇后的所有可能位置,然后再整个棋盘里判断这四个皇后是否会直接吃掉彼此,程序思想比较简单

function check1(arr, n) {
    for(var i = 0; i < n; i++) {
        for(var j = i + 1; j < n; j++) {
            if((arr[i] == arr[j]) || Math.abs(arr[i] - arr[j]) == j - i) {
                return false;
            }
        }
    }
    return true;
}
function queen1() {
    var arr = [];

    for(arr[0] = 1; arr[0] <= 4; arr[0]++) {
        for(arr[1] = 1; arr[1] <= 4; arr[1]++) {
            for(arr[2] = 1; arr[2] <= 4; arr[2]++) {
                for(arr[3] = 1; arr[3] <= 4; arr[3]++) {
                    if(!check1(arr, 4)) {
                        continue;
                    } else {
                        console.log(arr);
                    }
                }
            }
        }
    }
}

queen1();
//[ 2, 4, 1, 3 ]
//[ 3, 1, 4, 2 ]

关于结果,在 4*4 的棋盘里,四个皇后都不可能是在一排, arr[0] 到 arr[3] 分别对应四个皇后,数组的下标与下标对应的值即皇后在棋盘中的位置


回溯法

『走不通,就回头』,在适当节点判断是否符合,不符合就不再进行这条支路上的探索

function check2(arr, n) {
    for(var i = 0; i <= n - 1; i++) {
        if((Math.abs(arr[i] - arr[n]) == n - i) || (arr[i] == arr[n])) {
            return false;
        }
    }
    return true;
}

function queen2() {
    var arr = [];

    for(arr[0] = 1; arr[0] <= 4; arr[0]++) {
        for(arr[1] = 1; arr[1] <= 4; arr[1]++) {
            if(!check2(arr, 1)) continue; //摆两个皇后产生冲突的情况
            for(arr[2] = 1; arr[2] <= 4; arr[2]++) {
                if(!check2(arr, 2)) continue; //摆三个皇后产生冲突的情况
                for(arr[3] = 1; arr[3] <= 4; arr[3]++) {
                    if(!check2(arr, 3)) {
                        continue;
                    } else {
                        console.log(arr);
                    }
                }
            }
        }
    }
}

queen2();
//[ 2, 4, 1, 3 ]
//[ 3, 1, 4, 2 ]


非递归回溯法

算法框架

while(k > 0 『有路可走』 and 『未达到目标』) { // k > 0 有路可走
    if(k > n) { // 搜索到叶子节点
        // 搜索到一个解,输出
    } else {
        //a[k]第一个可能的值
        while(『a[k]在不满足约束条件且在搜索空间内』) {
            // a[k]下一个可能的值
        }
        if(『a[k]在搜索空间内』) {
            // 标示占用的资源
            // k = k + 1;
        } else {
            // 清理所占的状态空间
            // k = k - 1;
        }
    }
}

具体代码如下,最外层while下面包含两部分,一部分是对当前皇后可能值的遍历,另一部分是决定是进入下一层还是回溯上一层

function backdate(n) {
    var arr = [];

    var k = 1; // 第n的皇后
    arr[0] = 1;

    while(k > 0) {

        arr[k-1] = arr[k-1] + 1;
        while((arr[k-1] <= n) && (!check2(arr, k-1))) {
            arr[k-1] = arr[k-1] + 1;
        }
        // 这个皇后满足了约束条件,进行下一步判断

        if(arr[k-1] <= n) {
            if(k == n) { // 第n个皇后
                console.log(arr);
            } else {
                k = k + 1; // 下一个皇后
                arr[k-1] = 0;
            }
        } else {
            k = k - 1; // 回溯,上一个皇后
        }
    }
}

backdate(4);
//[ 2, 4, 1, 3 ]
//[ 3, 1, 4, 2 ]


递归回溯法

递归调用大大减少了代码量,也增加了程序的可读性

var arr = [], n = 4;
function backtrack(k) {
    if(k > n) {
        console.log(arr);
    } else {
        for(var i = 1;i <= n; i++) {
            arr[k-1] = i;
            if(check2(arr, k-1)) {
                backtrack(k + 1);
            }
        }
    }
}

backtrack(1);
//[ 2, 4, 1, 3 ]
//[ 3, 1, 4, 2 ]


华而不实的amb

什么是 amb ?给它一个数据列表,它能返回满足约束条件的成功情况的一种方式,没有成功情况就会失败,当然,它可以返回所有的成功情况。笔者写了上面那么多的重点,就是为了在这里推荐这个amb算法,它适合处理简单的回溯场景,很有趣,让我们来看看它是怎么工作的

首先来处理一个小问题,寻找相邻字符串:拿到几组字符串数组,每个数组拿出一个字符串,前一个字符串的末位字符与后一个字符串的首位字符相同,满足条件则输出这组新取出来的字符串

ambRun(function(amb, fail) {

    // 约束条件方法
    function linked(s1, s2) {
        return s1.slice(-1) == s2.slice(0, 1);
    }

    // 注入数据列表
    var w1 = amb(["the", "that", "a"]);
    var w2 = amb(["frog", "elephant", "thing"]);
    var w3 = amb(["walked", "treaded", "grows"]);
    var w4 = amb(["slowly", "quickly"]);

    // 执行程序
    if (!(linked(w1, w2) && linked(w2, w3) && linked(w3, w4))) fail();

    console.log([w1, w2, w3, w4].join(' '));
    // "that thing grows slowly"
});

看起来超级简洁有没有!不过使用的前提是,你不在乎性能,它真的是很浪费时间!

下面是它的 JavaScript 实现,有兴趣可以研究研究它是怎么把回溯抽出来的

function ambRun(func) {
    var choices = [];
    var index;

    function amb(values) {
        if (values.length == 0) {
            fail();
        }
        if (index == choices.length) {
            choices.push({i: 0,
                count: values.length});
        }
        var choice = choices[index++];
        return values[choice.i];
    }

    function fail() { throw fail; }

    while (true) {
        try {
            index = 0;
            return func(amb, fail);
        } catch (e) {
            if (e != fail) {
                throw e;
            }
            var choice;

            while ((choice = choices.pop()) && ++choice.i == choice.count) {}
            if (choice == undefined) {
                return undefined;
            }
            choices.push(choice);
        }
    }
}

以及使用 amb 实现的八皇后问题的具体代码

ambRun(function(amb, fail){
    var N = 4;
    var arr = [];
    var turn = [];
    for(var n = 0; n < N; n++) {
        turn[turn.length] = n + 1;
    }
    while(n--) {
        arr[arr.length] = amb(turn);
    }
    for (var i = 0; i < N; ++i) {
        for (var j = i + 1; j < N; ++j) {
            var a = arr[i], b = arr[j];
            if (a == b || Math.abs(a - b) == j - i) fail();
        }
    }
    console.log(arr);
    fail();
});


八皇后问题的JavaScript解法

这是八皇后问题的JavaScript解法,整个程序都没用for循环,都是靠递归来实现的,充分运用了Array对象的map, reduce, filter, concat, slice方法

'use strict';
var queens = function (boarderSize) {
  // 用递归生成一个start到end的Array
  var interval = function (start, end) {
    if (start > end) { return []; }
    return interval(start, end - 1).concat(end);
  };
  // 检查一个组合是否有效
  var isValid = function (queenCol) {
    // 检查两个位置是否有冲突
    var isSafe = function (pointA, pointB) {
      var slope = (pointA.row - pointB.row) / (pointA.col - pointB.col);
      if ((0 === slope) || (1 === slope) || (-1 === slope)) { return false; }
      return true;
    };
    var len = queenCol.length;
    var pointToCompare = {
      row: queenCol[len - 1],
      col: len
    };
    // 先slice出除了最后一列的数组,然后依次测试每列的点和待测点是否有冲突,最后合并测试结果
    return queenCol
      .slice(0, len - 1)
      .map(function (row, index) {
        return isSafe({row: row, col: index + 1}, pointToCompare);
      })
      .reduce(function (a, b) {
        return a && b;
      });
  };
  // 递归地去一列一列生成符合规则的组合
  var queenCols = function (size) {
    if (1 === size) {
      return interval(1, boarderSize).map(function (i) { return [i]; });
    }
    // 先把之前所有符合规则的列组成的集合再扩展一列,然后用reduce降维,最后用isValid过滤掉不符合规则的组合
    return queenCols(size - 1)
      .map(function (queenCol) {
        return interval(1, boarderSize).map(function (row) {
          return queenCol.concat(row);
        });
      })
      .reduce(function (a, b) {
        return a.concat(b);
      })
      .filter(isValid);
  };
  // queens函数入口
  return queenCols(boarderSize);
};

console.log(queens(8));
// 输出结果:
// [ [ 1, 5, 8, 6, 3, 7, 2, 4 ],
//   [ 1, 6, 8, 3, 7, 4, 2, 5 ],
//   ...
//   [ 8, 3, 1, 6, 2, 5, 7, 4 ],
//   [ 8, 4, 1, 3, 6, 2, 7, 5 ] ]


PS:延伸的N皇后问题
当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题(eight queens puzzle)时,他恐怕怎么也想不到,100 多年以后,这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单:把八个皇后放在国际象棋棋盘上,使得这八个皇后互相之间不攻击(国际象棋棋盘是一个 8×8 的方阵,皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步)。虽然这个问题一共有 92 个解,但要想徒手找出一个解来也并不容易。下图就是其中一个解:


八皇后问题有很多变种,不过再怎么也不会比下面这个变种版本更帅:请你设计一种方案,在一个无穷大的棋盘的每一行每一列里都放置一个皇后,使得所有皇后互相之间都不攻击。具体地说,假设这个棋盘的左下角在原点处,从下到上有无穷多行,从左到右有无穷多列,你需要找出一个全体正整数的排列方式 a1, a2, a3, … ,使得当你把第一个皇后放在第一行的第 a1 列,把第二个皇后放在第二行的第 a2 列,等等,那么任意两个皇后之间都不会互相攻击。


下面给出一个非常简单巧妙的构造。首先,我们给出五皇后问题的一个解。并且非常重要的是,其中一个皇后占据了最左下角的那个格子。


接下来,我们把五皇后的解扩展到 25 皇后,而依据则是五皇后本身的布局:


样一来,同一组里的五个皇后显然不会互相攻击,不同组的皇后之间显然也不会互相攻击,这便是一个满足要求的 25 皇后解了。注意到,在扩展之后,之前已经填好的部分并未改变。
再接下来怎么办呢?没错,我们又把 25 皇后的解复制成五份,再次按照五皇后的布局来排列,从而扩展到 125 皇后!


像这样不断地根据已填的部分,成倍地向外扩展,便能生成一个无穷皇后问题的解  


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: http://www.fly63.com/article/detial/1721

Js队列的实现与应用

队列与栈不同,它遵从先进先出(FIFO——First In First Out)原则,新添加的元素排在队列的尾部,元素只能从队列头部移除。

js实现1万的阶乘

但是这样就会存在问题,Js中最大的安全整数为2^53- 1,10000!结果溢出该范围,代码运行结果为Infinity,无法计算出正确的结果。那么如何才能计算大数据的阶乘呢?

JS数据结构与算法_集合&字典

集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是:集合中的成员是无序的;集合中不允许相同成员存在,计算机中的集合与数学中集合的概念相同,有一些概念我们必须知晓:

数据结构与算法之绪论

什么是数据结构?简单来说可以解释为:程序设计=数据结构+算法;主要是用来研究数据结构的关系,数据元素之间存在的一种或多种特定关系的集合;

用 Javascript 写排序算法

至于为什么选择用 Javascript,则是因为我觉得 Javascript 是最方便运行和调试的,只需要复制代码粘贴到浏览器的控制台就可以了,我为所有的算法附上了测试用例,通过引入 Mocha 就可以在浏览器中显示用例的通过情况

JavaScript 实现归并排序

在本文中,我们学习 Merge Sort 背后的逻辑,并用 JavaScript 实现。最后,在空间和时间复杂度方面将归并排序与其他算法进行比较。

JS中常用的排序方法

通过相邻数据元素的交换,逐步将待排序序列变为有序序列,如果前面的数据大于后面的数据,就将两值进行交换,将数据进行从小到大的排序,这样对数组的第0个数据到N-1个数据进行一次遍历后

原生js数值开根算法

理论上来讲,开根后的值为x,那么x^2=n,即可以将其转换为数学问题,令y=x^2-n,那么只需要求方程与x轴正方向的焦点就可以得出想要的结果,我们作x=a与方程交于(a^2-n),求得他的切线与x轴的交点

现在算法是新锐前端框架成功的重要因素

随着前端MVVM的流行,小型框架现在越来越难存活了!react, angular等打着大公司旗号的框架占了半壁江山,而avalon以其良好兼容性在国内份额不断上升。前端也与后端一样,遵循马太效应,强者愈强,弱者愈弱。最后只剩下两种框架

js二分查找算法

二分查找高效的前提是数据结构是有序的。就好比猜1~100之间的数,先猜50,如果太大了就猜25,如果太小了就猜75.每一次都猜最大值和最小值的中间点.

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!