JavaScript之八皇后问题(递归)

  八皇后问题,是一个古老而著名的问题,该问题最早由国际西洋棋棋手马克斯·贝瑟尔(Max Bezzel)于1848年提出。八皇后问题的具体描述为:在\(8\times8\)的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

  八皇后问题,是回溯算法的典型案例。本次分享讲使用递归法来寻找八皇后问题的所有解,并用JavaScript语言来写,同时学习JavaScript中OOP方面的知识。

  八皇后问题的完整代码如下:

<html>
<body> <script>
//create a class
function eightQueen(arr, cnt) {
//parameters
this.arr = arr;
this.cnt = cnt; //methods
this.search = function(r){
//if r == 8, then a solution is found
if(r==8){
document.write('<br>'+this.cnt+'<br>');
this.output(this.arr);
this.cnt++;
return null
}
for(var i=0;i<8;i++){
this.arr[r] = i;
flag = 1
for(var j=0;j<r;j++){
//check if this position is valid
if(this.arr[r] == this.arr[j] || r-j == Math.abs(this.arr[r]-this.arr[j])){
flag = 0;
break;
}
}
// if flag == 1, then the row numbered r is valid
if(flag) this.search(r+1); //search the next row
}
}
//output the valid solutions in format
this.output = function() {
for(var i=0; i<8;i++){
for(var j=0; j<8;j++){
pos = (j==arr[i]) ? '1 ' : '0 ';
document.write(pos);
}
document.write('<br>');
}
}
} //Initial array
var arr = [-1,-1,-1,-1,-1,-1,-1,-1]
//create a object
var eq = new eightQueen(arr,1);
//use object's method to find all solutions and print them
eq.search(0); </script> </body>
</html>

在上述JavaScript代码中,首先定义了一个类(Class):eightQueen,它的参数为:arr,cnt,其中arr为初始化数组,而cnt可以对方法计数。在eightQueen定义了方法search(),参数为r(第r行),当r等于8时,就找到了一个有效解,同时调用output()函数将这个有效解输出,当找到第r行的有效解后,再去寻找下一行的有效解。利用参数cnt可以帮助我们计数,这样我们就能找到所有有效解的数量。

  该代码在网页中运行的结果如下所示:

![八皇后问题的解(部分)](http://img.blog.csdn.net/20180116094618617?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvamNsaWFuOTE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)

可以看出,所有有效解的数量为92.
  当然,在HTML中可以用更加好的可视化方法来展示,欢迎有兴趣的同学多多尝试~~
  本次分享到此结束,欢迎大家交流~~

上一篇:VUE温习:style层次分析


下一篇:Android为ListView的Item设置不同的布局