JavaScript解八皇后問題的方法總結(jié)
關(guān)于八皇后問題的 JavaScript 解法，總覺得是需要學(xué)習(xí)一下算法的，哪天要用到的時候發(fā)現(xiàn)真不會就尷尬了
背景
八皇后問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個皇后都不能處于同一條橫行、縱行或斜線上
八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變?yōu)?n×n ，而皇后個數(shù)也變成n 。當(dāng)且僅當(dāng)n = 1或n ≥ 4時問題有解
盲目的枚舉算法
通過N重循環(huán)，枚舉滿足約束條件的解（八重循環(huán)代碼好多，這里進(jìn)行四重循環(huá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 的棋盤里，四個皇后都不可能是在一排， arr[0] 到 arr[3] 分別對應(yīng)四個皇后，數(shù)組的下標(biāo)與下標(biāo)對應(yīng)的值即皇后在棋盤中的位置
回溯法
『走不通，就回頭』，在適當(dāng)節(jié)點判斷是否符合，不符合就不再進(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; //擺兩個皇后產(chǎn)生沖突的情況
for(arr[2] = 1; arr[2] <= 4; arr[2]++) {
if(!check2(arr, 2)) continue; //擺三個皇后產(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é)點
// 搜索到一個解，輸出
} else {
//a[k]第一個可能的值
while(『a[k]在不滿足約束條件且在搜索空間內(nèi)』) {
// a[k]下一個可能的值
}
if(『a[k]在搜索空間內(nèi)』) {
// 標(biāo)示占用的資源
// k = k + 1;
} else {
// 清理所占的狀態(tài)空間
// k = k - 1;
}
}
}
具體代碼如下，最外層while下面包含兩部分，一部分是對當(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;
}
// 這個皇后滿足了約束條件，進(jìn)行下一步判斷
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 ]
遞歸回溯法
遞歸調(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 ]
華而不實的amb
什么是 amb ？給它一個數(shù)據(jù)列表，它能返回滿足約束條件的成功情況的一種方式，沒有成功情況就會失敗，當(dāng)然，它可以返回所有的成功情況。筆者寫了上面那么多的重點，就是為了在這里推薦這個amb算法，它適合處理簡單的回溯場景，很有趣，讓我們來看看它是怎么工作的
首先來處理一個小問題，尋找相鄰字符串：拿到幾組字符串?dāng)?shù)組，每個數(shù)組拿出一個字符串，前一個字符串的末位字符與后一個字符串的首位字符相同，滿足條件則輸出這組新取出來的字符串
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"
});
看起來超級簡潔有沒有！不過使用的前提是，你不在乎性能，它真的是很浪費時間！
下面是它的 javascript 實現(xiàn)，有興趣可以研究研究它是怎么把回溯抽出來的
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 實現(xià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();
});
八皇后問題的JavaScript解法
這是八皇后問題的JavaScript解法，整個程序都沒用for循環(huán)，都是靠遞歸來實現(xiàn)的，充分運用了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出除了最后一列的數(shù)組，然后依次測試每列的點和待測點是否有沖突，最后合并測試結(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ī)則的組合
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皇后問題
當(dāng) 1848 年國際象棋玩家 Max Bezzel 提出八皇后問題（eight queens puzzle）時，他恐怕怎么也想不到，100 多年以后，這個問題竟然成為了編程學(xué)習(xí)中最重要的必修課之一。八皇后問題聽上去非常簡單：把八個皇后放在國際象棋棋盤上，使得這八個皇后互相之間不攻擊（國際象棋棋盤是一個 8×8 的方陣，皇后則可以朝橫豎斜八個方向中的任意一個方向走任意多步）。雖然這個問題一共有 92 個解，但要想徒手找出一個解來也并不容易。下圖就是其中一個解：
八皇后問題有很多變種，不過再怎么也不會比下面這個變種版本更帥：請你設(shè)計一種方案，在一個無窮大的棋盤的每一行每一列里都放置一個皇后，使得所有皇后互相之間都不攻擊。具體地說，假設(shè)這個棋盤的左下角在原點處，從下到上有無窮多行，從左到右有無窮多列，你需要找出一個全體正整數(shù)的排列方式 a1, a2, a3, … ，使得當(dāng)你把第一個皇后放在第一行的第 a1 列，把第二個皇后放在第二行的第 a2 列，等等，那么任意兩個皇后之間都不會互相攻擊。
下面給出一個非常簡單巧妙的構(gòu)造。首先，我們給出五皇后問題的一個解。并且非常重要的是，其中一個皇后占據(jù)了最左下角的那個格子。
接下來，我們把五皇后的解擴(kuò)展到 25 皇后，而依據(jù)則是五皇后本身的布局：
樣一來，同一組里的五個皇后顯然不會互相攻擊，不同組的皇后之間顯然也不會互相攻擊，這便是一個滿足要求的 25 皇后解了。注意到，在擴(kuò)展之后，之前已經(jīng)填好的部分并未改變。
再接下來怎么辦呢？沒錯，我們又把 25 皇后的解復(fù)制成五份，再次按照五皇后的布局來排列，從而擴(kuò)展到 125 皇后！
像這樣不斷地根據(jù)已填的部分，成倍地向外擴(kuò)展，便能生成一個無窮皇后問題的解。
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了微信小程序App生命周期的相關(guān)資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要為大家詳細(xì)介紹了js+html5實現(xiàn)頁面可刷新的倒計時效果，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-07-07
本篇文章主要介紹了webpack多入口文件頁面打包配置詳解，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-01-01
這篇文章主要介紹了有關(guān)JavaScript Promises異步問題詳解的相關(guān)資料,需要的朋友可以參考下2015-11-11
JS基于遞歸實現(xiàn)網(wǎng)頁版計算器的方法分析
這篇文章主要介紹了JS基于遞歸實現(xiàn)網(wǎng)頁版計算器的方法,結(jié)合實例形式分析了javascript采用遞歸算法實現(xiàn)網(wǎng)頁版計算器的步驟與相關(guān)操作技巧,需要的朋友可以參考下2017-12-12
圍住神經(jīng)貓游戲是一款基于html5、jquery、typescript等技術(shù)開發(fā)的游戲，非常好玩，感興趣的朋友快來圍觀吧，體驗一把，下面給大家分享使用html5如何制作圍住神經(jīng)貓游戲-附源碼下載，有需要的朋友可以參考下2015-08-08
javascript中的this應(yīng)用非常廣泛，對js中this總是似是而非的感覺，今天小編豁然開朗，然后再次給大家談?wù)搄s中的this關(guān)鍵，感興趣的朋友跟著小編一起看看吧2016-06-06
Javasript設(shè)計模式之鏈?zhǔn)秸{(diào)用詳解
這篇文章主要為大家詳細(xì)介紹了Javasript設(shè)計模式之鏈?zhǔn)秸{(diào)用的相關(guān)資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
今天小編就為大家分享一篇關(guān)于js數(shù)組去重的方法總結(jié)，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
JavaScript模擬可展開、拖動與關(guān)閉的聊天窗口實例
這篇文章主要介紹了JavaScript模擬可展開、拖動與關(guān)閉的聊天窗口,實例分析了javascript實現(xiàn)可拖動的div層相關(guān)技巧,非常具有實用價值,需要的朋友可以參考下2015-05-05