欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript解八皇后問(wèn)題的方法總結(jié)

 更新時(shí)間:2016年06月12日 17:32:52   作者:ggsoul  
在國(guó)際象棋的8*8棋盤上如何擺放8個(gè)皇后使任一皇后無(wú)法吃掉其他皇后的問(wèn)題便是最初的八皇后問(wèn)題,此后也被不斷擴(kuò)展而作為經(jīng)典的算法題目,這里我們就來(lái)看一下JavaScript解八皇后問(wèn)題的方法總結(jié)

關(guān)于八皇后問(wèn)題的 JavaScript 解法,總覺得是需要學(xué)習(xí)一下算法的,哪天要用到的時(shí)候發(fā)現(xiàn)真不會(huì)就尷尬了

背景
八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題:如何能夠在 8×8 的國(guó)際象棋棋盤上放置八個(gè)皇后,使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后?為了達(dá)到此目的,任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上

八皇后問(wèn)題可以推廣為更一般的n皇后擺放問(wèn)題:這時(shí)棋盤的大小變?yōu)?n×n ,而皇后個(gè)數(shù)也變成n 。當(dāng)且僅當(dāng)n = 1或n ≥ 4時(shí)問(wèn)題有解

盲目的枚舉算法
通過(guò)N重循環(huán),枚舉滿足約束條件的解(八重循環(huán)代碼好多,這里進(jìn)行四重循環(huán)),找到四個(gè)皇后的所有可能位置,然后再整個(gè)棋盤里判斷這四個(gè)皇后是否會(huì)直接吃掉彼此,程序思想比較簡(jiǎ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 ]

關(guān)于結(jié)果,在 4*4 的棋盤里,四個(gè)皇后都不可能是在一排, arr[0] 到 arr[3] 分別對(duì)應(yīng)四個(gè)皇后,數(shù)組的下標(biāo)與下標(biāo)對(duì)應(yīng)的值即皇后在棋盤中的位置

回溯法
『走不通,就回頭』,在適當(dāng)節(jié)點(diǎn)判斷是否符合,不符合就不再進(jìn)行這條支路上的探索

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; //擺兩個(gè)皇后產(chǎn)生沖突的情況
      for(arr[2] = 1; arr[2] <= 4; arr[2]++) {
        if(!check2(arr, 2)) continue; //擺三個(gè)皇后產(chǎn)生沖突的情況
        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 『未達(dá)到目標(biāo)』) { // k > 0 有路可走
  if(k > n) { // 搜索到葉子節(jié)點(diǎn)
    // 搜索到一個(gè)解,輸出
  } else {
    //a[k]第一個(gè)可能的值
    while(『a[k]在不滿足約束條件且在搜索空間內(nèi)』) {
      // a[k]下一個(gè)可能的值
    }
    if(『a[k]在搜索空間內(nèi)』) {
      // 標(biāo)示占用的資源
      // k = k + 1;
    } else {
      // 清理所占的狀態(tài)空間
      // k = k - 1;
    }
  }
}

具體代碼如下,最外層while下面包含兩部分,一部分是對(duì)當(dāng)前皇后可能值的遍歷,另一部分是決定是進(jìn)入下一層還是回溯上一層

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;
    }
    // 這個(gè)皇后滿足了約束條件,進(jìn)行下一步判斷

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

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

遞歸回溯法
遞歸調(diào)用大大減少了代碼量,也增加了程序的可讀性

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 ]

華而不實(shí)的amb
什么是 amb ?給它一個(gè)數(shù)據(jù)列表,它能返回滿足約束條件的成功情況的一種方式,沒有成功情況就會(huì)失敗,當(dāng)然,它可以返回所有的成功情況。筆者寫了上面那么多的重點(diǎn),就是為了在這里推薦這個(gè)amb算法,它適合處理簡(jiǎn)單的回溯場(chǎng)景,很有趣,讓我們來(lái)看看它是怎么工作的

首先來(lái)處理一個(gè)小問(wèn)題,尋找相鄰字符串:拿到幾組字符串?dāng)?shù)組,每個(gè)數(shù)組拿出一個(gè)字符串,前一個(gè)字符串的末位字符與后一個(gè)字符串的首位字符相同,滿足條件則輸出這組新取出來(lái)的字符串

ambRun(function(amb, fail) {

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

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

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

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

看起來(lái)超級(jí)簡(jiǎn)潔有沒有!不過(guò)使用的前提是,你不在乎性能,它真的是很浪費(fèi)時(shí)間!

下面是它的 javascript 實(shí)現(xiàn),有興趣可以研究研究它是怎么把回溯抽出來(lái)的

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 實(shí)現(xiàn)的八皇后問(wèn)題的具體代碼

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();
});

八皇后問(wèn)題的JavaScript解法
這是八皇后問(wèn)題的JavaScript解法,整個(gè)程序都沒用for循環(huán),都是靠遞歸來(lái)實(shí)現(xiàn)的,充分運(yùn)用了Array對(duì)象的map, reduce, filter, concat, slice方法

'use strict';
var queens = function (boarderSize) {
 // 用遞歸生成一個(gè)start到end的Array
 var interval = function (start, end) {
  if (start > end) { return []; }
  return interval(start, end - 1).concat(end);
 };
 // 檢查一個(gè)組合是否有效
 var isValid = function (queenCol) {
  // 檢查兩個(gè)位置是否有沖突
  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出除了最后一列的數(shù)組,然后依次測(cè)試每列的點(diǎn)和待測(cè)點(diǎn)是否有沖突,最后合并測(cè)試結(jié)果
  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;
   });
 };
 // 遞歸地去一列一列生成符合規(guī)則的組合
 var queenCols = function (size) {
  if (1 === size) {
   return interval(1, boarderSize).map(function (i) { return [i]; });
  }
  // 先把之前所有符合規(guī)則的列組成的集合再擴(kuò)展一列,然后用reduce降維,最后用isValid過(guò)濾掉不符合規(guī)則的組合
  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函數(shù)入口
 return queenCols(boarderSize);
};

console.log(queens(8));
// 輸出結(jié)果:
// [ [ 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皇后問(wèn)題
當(dāng) 1848 年國(guó)際象棋玩家 Max Bezzel 提出八皇后問(wèn)題(eight queens puzzle)時(shí),他恐怕怎么也想不到,100 多年以后,這個(gè)問(wèn)題竟然成為了編程學(xué)習(xí)中最重要的必修課之一。八皇后問(wèn)題聽上去非常簡(jiǎn)單:把八個(gè)皇后放在國(guó)際象棋棋盤上,使得這八個(gè)皇后互相之間不攻擊(國(guó)際象棋棋盤是一個(gè) 8×8 的方陣,皇后則可以朝橫豎斜八個(gè)方向中的任意一個(gè)方向走任意多步)。雖然這個(gè)問(wèn)題一共有 92 個(gè)解,但要想徒手找出一個(gè)解來(lái)也并不容易。下圖就是其中一個(gè)解:

2016612172955775.png (141×140)

八皇后問(wèn)題有很多變種,不過(guò)再怎么也不會(huì)比下面這個(gè)變種版本更帥:請(qǐng)你設(shè)計(jì)一種方案,在一個(gè)無(wú)窮大的棋盤的每一行每一列里都放置一個(gè)皇后,使得所有皇后互相之間都不攻擊。具體地說(shuō),假設(shè)這個(gè)棋盤的左下角在原點(diǎn)處,從下到上有無(wú)窮多行,從左到右有無(wú)窮多列,你需要找出一個(gè)全體正整數(shù)的排列方式 a1, a2, a3, … ,使得當(dāng)你把第一個(gè)皇后放在第一行的第 a1 列,把第二個(gè)皇后放在第二行的第 a2 列,等等,那么任意兩個(gè)皇后之間都不會(huì)互相攻擊。

2016612173034008.png (169×166)

下面給出一個(gè)非常簡(jiǎn)單巧妙的構(gòu)造。首先,我們給出五皇后問(wèn)題的一個(gè)解。并且非常重要的是,其中一個(gè)皇后占據(jù)了最左下角的那個(gè)格子。

2016612173051101.png (41×44)

接下來(lái),我們把五皇后的解擴(kuò)展到 25 皇后,而依據(jù)則是五皇后本身的布局:

2016612173109083.png (136×136)

樣一來(lái),同一組里的五個(gè)皇后顯然不會(huì)互相攻擊,不同組的皇后之間顯然也不會(huì)互相攻擊,這便是一個(gè)滿足要求的 25 皇后解了。注意到,在擴(kuò)展之后,之前已經(jīng)填好的部分并未改變。
再接下來(lái)怎么辦呢?沒錯(cuò),我們又把 25 皇后的解復(fù)制成五份,再次按照五皇后的布局來(lái)排列,從而擴(kuò)展到 125 皇后!

2016612173138061.png (500×500)

像這樣不斷地根據(jù)已填的部分,成倍地向外擴(kuò)展,便能生成一個(gè)無(wú)窮皇后問(wèn)題的解。

相關(guān)文章

  • 微信小程序App生命周期詳解

    微信小程序App生命周期詳解

    這篇文章主要為大家詳細(xì)介紹了微信小程序App生命周期的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • js+html5實(shí)現(xiàn)頁(yè)面可刷新的倒計(jì)時(shí)效果

    js+html5實(shí)現(xiàn)頁(yè)面可刷新的倒計(jì)時(shí)效果

    這篇文章主要為大家詳細(xì)介紹了js+html5實(shí)現(xiàn)頁(yè)面可刷新的倒計(jì)時(shí)效果,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-07-07
  • webpack多入口文件頁(yè)面打包配置詳解

    webpack多入口文件頁(yè)面打包配置詳解

    本篇文章主要介紹了webpack多入口文件頁(yè)面打包配置詳解,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2018-01-01
  • 有關(guān)Promises異步問(wèn)題詳解

    有關(guān)Promises異步問(wèn)題詳解

    這篇文章主要介紹了有關(guān)JavaScript Promises異步問(wèn)題詳解的相關(guān)資料,需要的朋友可以參考下
    2015-11-11
  • JS基于遞歸實(shí)現(xiàn)網(wǎng)頁(yè)版計(jì)算器的方法分析

    JS基于遞歸實(shí)現(xiàn)網(wǎng)頁(yè)版計(jì)算器的方法分析

    這篇文章主要介紹了JS基于遞歸實(shí)現(xiàn)網(wǎng)頁(yè)版計(jì)算器的方法,結(jié)合實(shí)例形式分析了javascript采用遞歸算法實(shí)現(xiàn)網(wǎng)頁(yè)版計(jì)算器的步驟與相關(guān)操作技巧,需要的朋友可以參考下
    2017-12-12
  • 純HTML5制作圍住神經(jīng)貓游戲-附源碼下載

    純HTML5制作圍住神經(jīng)貓游戲-附源碼下載

    圍住神經(jīng)貓游戲是一款基于html5、jquery、typescript等技術(shù)開發(fā)的游戲,非常好玩,感興趣的朋友快來(lái)圍觀吧,體驗(yàn)一把,下面給大家分享使用html5如何制作圍住神經(jīng)貓游戲-附源碼下載,有需要的朋友可以參考下
    2015-08-08
  • 再次談?wù)揓avascript中的this

    再次談?wù)揓avascript中的this

    javascript中的this應(yīng)用非常廣泛,對(duì)js中this總是似是而非的感覺,今天小編豁然開朗,然后再次給大家談?wù)搄s中的this關(guān)鍵,感興趣的朋友跟著小編一起看看吧
    2016-06-06
  • Javasript設(shè)計(jì)模式之鏈?zhǔn)秸{(diào)用詳解

    Javasript設(shè)計(jì)模式之鏈?zhǔn)秸{(diào)用詳解

    這篇文章主要為大家詳細(xì)介紹了Javasript設(shè)計(jì)模式之鏈?zhǔn)秸{(diào)用的相關(guān)資料,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-04-04
  • js數(shù)組去重的方法總結(jié)

    js數(shù)組去重的方法總結(jié)

    今天小編就為大家分享一篇關(guān)于js數(shù)組去重的方法總結(jié),小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2019-01-01
  • JavaScript模擬可展開、拖動(dòng)與關(guān)閉的聊天窗口實(shí)例

    JavaScript模擬可展開、拖動(dòng)與關(guān)閉的聊天窗口實(shí)例

    這篇文章主要介紹了JavaScript模擬可展開、拖動(dòng)與關(guān)閉的聊天窗口,實(shí)例分析了javascript實(shí)現(xiàn)可拖動(dòng)的div層相關(guān)技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下
    2015-05-05

最新評(píng)論