JavaScript解八皇后問題的方法總結

2019-11-20 09:43:30

字體：大中小

來源：轉載

供稿：網友

關于八皇后問題的 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 個解，但要想徒手找出一個解來也并不容易。下圖就是其中一個解：

2016612172955775.png (141×140)

八皇后問題有很多變種，不過再怎么也不會比下面這個變種版本更帥：請你設計一種方案，在一個無窮大的棋盤的每一行每一列里都放置一個皇后，使得所有皇后互相之間都不攻擊。具體地說，假設這個棋盤的左下角在原點處，從下到上有無窮多行，從左到右有無窮多列，你需要找出一個全體正整數的排列方式 a1, a2, a3, … ，使得當你把第一個皇后放在第一行的第 a1 列，把第二個皇后放在第二行的第 a2 列，等等，那么任意兩個皇后之間都不會互相攻擊。

2016612173034008.png (169×166)