關於八皇后問題的 JavaScript 解法,我一直覺得該好好學一下演算法——真到要用時才發現不會就尷尬了。
問題背景
八皇后源自國際象棋:如何在 8×8 棋盤上放置八個皇后,使任兩皇后都不在同一橫行、縱行或斜線上,也就是誰都吃不到誰。
推廣後即為 n 皇后問題,棋盤變為 n×n、皇后數為 n。當且僅當 n = 1 或 n ≥ 4 時才有解。
用多重迴圈枚舉所有組合,再對每組檢查是否衝突。八皇后需要八層迴圈(這裡用四皇后示範),思路簡單但效率最差。
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 『未達到目標』) { 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; // 第 k 個皇后 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) { 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 接受一組候選值並回傳其中一個,若後續約束不成立就「失敗」回溯換下一個值,也能列舉全部成功組合。它特別適合處理簡單的回溯場景。
先看一個小問題:從幾組字串中各取一個,要求前一個的末字等於後一個的首字。
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(); });
這份實作完全沒用 for 迴圈,全靠遞歸與 Array 的 map、reduce、filter、concat、slice 完成:
'use strict'; var queens = function (boarderSize) { // 用遞歸生成 start 到 end 的陣列 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 }; 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]; }); } 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); }; return queenCols(boarderSize); }; console.log(queens(8)); // [ [ 1, 5, 8, 6, 3, 7, 2, 4 ], ... [ 8, 4, 1, 3, 6, 2, 7, 5 ] ]
延伸:無窮棋盤上的皇后
1848 年國際象棋玩家 Max Bezzel 提出八皇后問題時,大概想不到百餘年後它會成為程式設計的必修課之一。八皇后共有 92 組解,但徒手找一組並不容易。下圖是其中一組:

更有趣的變種是:在一個無窮大的棋盤上,每一列每一行都放一個皇后,且互不攻擊。也就是要找出正整數的排列 a1, a2, a3, …,使第一個皇后放在第一行第 a1 欄、第二個放在第二行第 a2 欄,依此類推。

構造方式非常巧妙。先給出五皇后的其中一組解,關鍵是其中一個皇后正好佔據最左下角:

接著依據這五皇后的布局,把五皇后解擴展成 25 皇后:

這樣一來,同一組內的五個皇后顯然互不攻擊,不同組之間因為沿用大層次的五皇后布局,也不會互相攻擊,於是我們得到了一組 25 皇后解。特別值得注意的是,擴展過程中原本已填好的部分完全沒有改動。
再下一步?把 25 皇后的解複製五份,再次依五皇后的布局排列,就擴展成 125 皇后。

如此不斷「依已填部分成倍向外擴展」,就能構造出無窮皇后問題的解。這種自我相似的遞歸構造,正是它優美之處。