摘要：關(guān)于八皇后問(wèn)題的解法，總覺(jué)得是需要學(xué)習(xí)一下算法的，哪天要用到的時(shí)候發(fā)現(xiàn)真不會(huì)就尷尬了背景八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題如何能夠在的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后為了達(dá)到此目的，任兩個(gè)皇后都不能處

關(guān)于八皇后問(wèn)題的 JavaScript 解法，總覺(jué)得是需要學(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 ]

什么是 amb ？給它一個(gè)數(shù)據(jù)列表，它能返回滿足約束條件的成功情況的一種方式，沒(méi)有成功情況就會(huì)失敗，當(dāng)然，它可以返回所有的成功情況。筆者寫(xiě)了上面那么多的重點(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)潔有沒(méi)有！不過(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解法，整個(gè)程序都沒(méi)用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 ] ]

回溯算法是很常用的基本算法，認(rèn)真掌握是沒(méi)有錯(cuò)的，筆者也是一邊學(xué)習(xí)一邊寫(xiě)下本篇，學(xué)習(xí)內(nèi)容來(lái)源

八皇后問(wèn)題
五大常用算法之四：回溯法
回溯法——八皇后問(wèn)題
Amb() in JavaScript
八皇后問(wèn)題的 JavaScript 解法

文章轉(zhuǎn)載自筆者個(gè)人博客 Gaoxuefeng"s Blog