摘要:關于八皇后問題的解法,總覺得是需要學習一下算法的,哪天要用到的時候發現真不會就尷尬了背景八皇后問題是一個以國際象棋為背景的問題如何能夠在的國際象棋棋盤上放置八個皇后,使得任何一個皇后都無法直接吃掉其他的皇后為了達到此目的,任兩個皇后都不能處
關于八皇后問題的 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 ] ]總結
回溯算法是很常用的基本算法,認真掌握是沒有錯的,筆者也是一邊學習一邊寫下本篇,學習內容來源
八皇后問題
五大常用算法之四:回溯法
回溯法——八皇后問題
Amb() in JavaScript
八皇后問題的 JavaScript 解法
文章轉載自筆者個人博客 Gaoxuefeng"s Blog
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/79447.html
摘要:回溯法解八皇后帶詳細注解若出現小于則說明問題無解第一次檢測到新的一行回溯時運行的程序塊為已經檢測過并為能放置皇后的位置回溯過程中,遇到能放皇后的位置,說明這個位置在后面的驗證沒有通過,需要重新處理回溯時發現上一行也到行末需要繼續回溯回溯 /** * 回溯法解八皇后, 帶詳細注解 */ function NQueens(order) { if (order < 4) { ...
摘要:八皇后問題是十九世紀著名的數學家高斯年提出。同時可以擴展為九皇后,十皇后問題。解決方案回溯與遞歸。這樣,編譯器或者解釋器就可以把尾遞歸做優化,使遞歸本身無論調用多少次,都只占用一個棧幀,不會出現棧溢出的情況。 八皇后問題是十九世紀著名的數學家高斯1850年提出 。以下為python語言的八皇后代碼,摘自《Python基礎教程》,代碼相對于其他語言,來得短小且一次性可以打印出92種結果。...
摘要:終止條件遞推公式遞歸的分類通過做大量的題,根據遞歸解決不同的問題,引申出來的幾種解決和思考的方式。我們通過層與層之間的計算關系用遞推公式表達出來做計算,經過層層的遞歸,最終得到結果值。 showImg(https://segmentfault.com/img/remote/1460000019222330); 前言 幾個月之前就想寫這樣一篇文章分享給大家,由于自己有心而力不足,沒有把真...
摘要:暴力法復雜度時間空間思路因為皇后問題中,同一列不可能有兩個皇后,所以我們可以用一個一維數組來表示二維棋盤上皇后的位置。一維數組中每一個值的下標代表著對應棋盤的列,每一個值則是那一列中皇后所在的行。 N-Queens I The n-queens puzzle is the problem of placing n queens on an n×n chessboard such th...
閱讀 2413·2021-08-18 10:21
閱讀 2519·2019-08-30 13:45
閱讀 2155·2019-08-30 13:16
閱讀 2100·2019-08-30 12:52
閱讀 1363·2019-08-30 11:20
閱讀 2622·2019-08-29 13:47
閱讀 1622·2019-08-29 11:22
閱讀 2760·2019-08-26 12:11